Please use this identifier to cite or link to this item:
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:
Category: T1
Type: Theses and Dissertations
Appears in Collections:PhD theses
Research publications

Files in This Item:
File Description SizeFormat 
VandeurzenLuc.pdf976.57 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on May 21, 2022


checked on May 21, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.