Document Server@UHasselt >
Research >
Research publications >

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.
URI: http://hdl.handle.net/1942/8779
Type: Theses and Dissertations
Appears in Collections: PhD theses
Research publications

Files in This Item:

Description SizeFormat
N/A976.57 kBAdobe PDF

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