Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/8869

Title: Geometric and algorithmic aspects of topological queries to spatial databases
Authors: Geerts, Floris
Advisors: Van den Bussche, Jan
Issue Date: 2001
Publisher: UHasselt Diepenbeek
Abstract: Excerpt from the introduction: Overview The following chapters are organized as follows. Chapter 2 provides the necessary background on constraint databases and query languages. It gives the definition of topological queries and introduces transitive closure logics. Chapter 3 shows that FO+LIN+TCS is computationally complete on Z-linear constraint databases, and that FO+Po1v+TCS is computationally complete on polynomial constraint databases with respect to Boolean topological queries. Chapter 4 looks at the geometric properties of polynomial constraint databases and shows that many of these properties are expressible by first-order means. More specifically, we define the local cone structure of polynomial constraint databases for boxes, and proof that this is a first-order expressible property. We conclude this chapter by defining the uniform cone radius decomposition and the notion of a box collection, which we will use in Chapter 5. In that chapter, we construct a special box collection and show how it can be used to construct a linearization of a polynomial constraint database. We then show that this construction is expressible in FO+Po1v+TC. As a consequence, we show that the connectivity query is expressible in FO+Po1v+TC. After a minor adaptation of the linearization, we show how it can be used to approximate the volume of a polynomial constraint database. Finally, Chapter 6 deals with the online maintenance of the topological invariant.
URI: http://hdl.handle.net/1942/8869
Category: T1
Type: Theses and Dissertations
Appears in Collections: PhD theses
Research publications

Files in This Item:

Description SizeFormat
N/A15.07 MBAdobe PDF

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