Open AccessLinear constraint query languages expressive power and complexity
Author(s) -
Stéphane Grumbach,
Jianwen Su,
Christophe Tollu
Publication year - 1995
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
ISBN - 3-540-60178-3
DOI - 10.1007/3-540-60178-3_96
Subject(s) - expressive power , computer science , cardinality (data modeling) , theoretical computer science , upper and lower bounds , query language , graph , constraint (computer aided design) , set (abstract data type) , time complexity , discrete mathematics , algorithm , mathematics , programming language , database , mathematical analysis , geometry
We give an AC0 upper bound on the complexity of first-oder queries over (infinite) databases defined by restricted linear constraints. This result enables us to deduce the non-expressibility of various usual queries, such as the parity of the cardinality of a set or the connectivity of a graph in first-order logic with linear constraints.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom