Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/8779| Title: | Logic-based query languages for the linear constraint database model | Authors: | VANDEURZEN, Luc | Advisors: | GYSSENS, Marc | Issue Date: | 1999 | Publisher: | UHasselt Diepenbeek | 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. | Document URI: | http://hdl.handle.net/1942/8779 | Category: | T1 | Type: | Theses and Dissertations |
| Appears in Collections: | PhD theses Research publications |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| VandeurzenLuc.pdf | 976.57 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.