Geometric and algorithmic aspects of topological queries to spatial databases

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.