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

Files in This Item:
File Description SizeFormat 
Floris Geerts.pdf15.07 MBAdobe PDFView/Open
Show full item record

Page view(s)

checked on May 20, 2022


checked on May 20, 2022

Google ScholarTM


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