Logic-based query languages for the linear constraint database model

Abstract

In this work, we concentrate on the linear constraint database model. The main contributions of this research dissertation can be summarized as follows: 1. We provide a list of queries of which we show that they can be expressed in FO + linear, i.e., the relational calculus extended with linear constraints, and a tool which can be used to prove non-expressibility of a query in FO + linear. We show that the type of the coefficients of the linear constraints used in the linear constraint database model does influence certain results. We also prove that it is undecidable whether a linear query expressible in FO + poly, i.e., the relational calculus extended with polynomial constraints, can be expressed in FO + linear. 2. We propose a technique to decompose semi-linear sets (figures representable with linear constraints) into convex cells which is expressible in FO + poly. As a side-effect, we obtain algorithms, implementable in FO + poly, to compute a finite representation of an arbitrary semi-linear set and to recompute a semilinear set from its finite representation. 3. We show that it is decidable whether a geometric figure definable with polynomial constraints is semi-linear. 4. We present two sound extensions of FO + linear for linear queries expressible in FO + poly. One extension can be seen as a bridge between GDT-based query languages and FO + linear, while the other extension results in a query language of which the expressive power can be characterized in terms of the ruler and compass constructions in the two-dimensional plane. We also show that there exist query languages which are complete for the linear queries expressible in FO + poly.