Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/3231
Title: | First-order queries on finite structures over the reals | Authors: | Paredaens, J VAN DEN BUSSCHE, Jan Van Gucht, D |
Issue Date: | 1998 | Publisher: | SIAM PUBLICATIONS | Source: | SIAM JOURNAL ON COMPUTING, 27(6). p. 1747-1763 | 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 chi < y. | Notes: | Univ Instelling Antwerp, Dept Math & Comp Sci, B-2610 Wilrijk, Belgium. Limburgs Univ Ctr, Dept WNI, B-3590 Diepenbeek, Belgium. Indiana Univ, Dept Comp Sci, Bloomington, IN 47405 USA.Paredaens, J, Univ Instelling Antwerp, Dept Math & Comp Sci, Univ Pl 1, B-2610 Wilrijk, Belgium. | Keywords: | first-order logic; linear arithmetic; relational databases; constraint programming | Document URI: | http://hdl.handle.net/1942/3231 | DOI: | 10.1137/S009753979629766 | ISI #: | 000074012100011 | Type: | Journal Contribution | Validations: | ecoom 1999 |
Appears in Collections: | Research publications |
Show full item record
SCOPUSTM
Citations
16
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
18
checked on Apr 22, 2024
Page view(s)
76
checked on Oct 30, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.