DocumentCode :
3291114
Title :
First-order queries on finite structures over the reals
Author :
Paredaens, Jan ; Van den Bussche, Jan ; Van Gucht, Dirk
Author_Institution :
Antwerp Univ., Belgium
fYear :
1995
fDate :
26-29 Jun 1995
Firstpage :
79
Lastpage :
87
Abstract :
We investigate properties of finite relational structures over the reals expressed by first-order sentences whose predicates are the relations of the structure plus arbitrary polynomial inequalities, and whose quantifiers can range over the whole set of reals. In constraint programming terminology, this corresponds to Boolean real polynomial constraint queries on finite structures. The fact that quantifiers range over all reals seems crucial; however, we observe that each sentence in the first-order theory of the reals can be evaluated by letting each quantifier range over only a finite set of real numbers without changing its truth value. Inspired by this observation, we then show that when all polynomials used are linear, each query can be expressed uniformly on all finite structures by a sentence of which the quantifiers range only over the finite domain of the structure. In other words, linear constraint programming on finite structures can be reduced to ordinary query evaluation as usual in finite model theory and databases. Moreover, if only “generic” queries are taken into consideration, we show that this can be reduced even further by proving that such queries can be expressed by sentences using as polynomial inequalities only those of the simple form z<y
Keywords :
Boolean functions; constraint handling; polynomials; query processing; Boolean real polynomial constraint queries; arbitrary polynomial inequalities; constraint programming terminology; databases; finite relational structures; finite structures; first-order queries; first-order sentences; first-order theory; ordinary query evaluation; polynomial inequalities; polynomials; predicates; Computer science; Constraint theory; Electronic mail; Linear programming; Logic programming; Polynomials; Query processing; Relational databases; Virtual colonoscopy;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science, 1995. LICS '95. Proceedings., Tenth Annual IEEE Symposium on
Conference_Location :
San Diego, CA
ISSN :
1043-6871
Print_ISBN :
0-8186-7050-9
Type :
conf
DOI :
10.1109/LICS.1995.523246
Filename :
523246
Link To Document :
بازگشت