Linear Approximation of Semi-algebraic Spatial Databases Using Transitive Closure Logic, in Arbitrary Dimension

Abstract

We consider n-dimensional semi-algebraic spatial databases. We compute in first-order logic extended with a transitive closure operator, a linear spatial database which characterizes the semi-algebraic spatial database up to a homeomorphism. In this way, we generalize our earlier results to semi-algebraic spatial databases in arbitrary dimensions, our earlier results being true for only two dimensions. Consequently, we can prove that first-order logic with a transitive closure operator extended with stop conditions, can express all Boolean topological queries on semi-algebraic spatial databases of arbitrary dimension.