Definability with a predicate for a semi-linear set. (English) Zbl 1045.03032

The paper concerns the first-order linear constraint language \(\text{FO}+\text{LIN}\) and the first-order polynomial constraint query language \(\text{FO}+ \text{POLY}\). The sentences of these languages generate semilinear and semi-algebraic sets, respectively. The authors focus on the expressive power of \(\text{FO}+ \text{LIN}\) with an extra predicate symbol ranging over the semilinear sets. They consider five collections of semilinear sets in the Euclidean plane: Co-Linear (all points in each set are collinear), Is.Line (each set is a line), Cont.Line (each set contains a line), Lin.Reach (each set contains a given line segment), and Lin.Meet (each set contains two lines which intersect in a given point).
In Section 2, a brief review of basic notions is presented including some elementary undefinability results. Section 3 contains the notions from non-standard analysis needed as a tool for proving further undefinability results. Section 4 concerns the definability or undefinability of queries related to Lin.Reach in \(\text{FO}+ \text{LIN}\). In Section 5 universal and existential second-order extensions of \(\text{FO}+ \text{LIN}\) are introduced.
These languages are between \(\text{FO}+ \text{LIN}\) and \(\text{FO}+ \text{POLY}\). The definability problem for queries related to Cont.Line in \(\text{FO}+ \text{LIN}\) is solved in Section 6. Section 7 analyses the \(\text{FO}+ \text{LIN}\)-definability problem for the property that any two points are connected by a polygonal path with at most \(n\) segments for various \(n\). Section 8 discusses extensions of results to higher dimensions.
The results contribute to the foundations of spatial databases in which spatial information is modelled by constraint sets.


03B70 Logic in computer science
68P15 Database theory
Full Text: DOI


[1] Computer science logic, CSL 2000 1862 pp 217– (2000)
[2] Structures in Logic and Computer Science 1261 (1997)
[3] DOI: 10.1145/273865.273870 · Zbl 0902.68047
[4] Proceedings of the second international workshop on principles and practice of constraint programming 874 pp 181– (1995)
[5] Constraint databases and their applications, Second international workshop on constraint database systems, CDB ’97 1191 pp 105– (1997)
[6] Model Theory (1990)
[7] Constraint databases (2000) · Zbl 0935.00022
[8] Proceedings of the Sixth International Conference on Database Theory 1186 pp 432– (1997)
[9] DOI: 10.1006/jcss.1995.1051 · Zbl 05478519
[10] The Theory of Models pp 407– (1965)
[11] DOI: 10.1002/malq.19990450411 · Zbl 0937.03048
[12] Constraint databases and applications, ESPRIT CONTESSA workshop 1034 pp 22– (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.