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. | Document URI: | http://hdl.handle.net/1942/8869 | Category: | T1 | Type: | Theses and Dissertations |
Appears in Collections: | PhD theses Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Floris Geerts.pdf | 15.07 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.