Degrees of Monotonicity of Spatial Transformations

Abstract

We consider spatial databases that can be defined in terms of polynomial inequalities, and we are interested in monotonic transformations of spatial databases. We investigate a hierarchy of monotonicity classes of spatial transformations that is determined by the number of degrees of freedom of the transformations. The result of a monotonic transformation with k degrees of freedom on a spatial database is completely determined by its result on subsets of cardinality at most k of the spatial database. The result of a transformation in the largest class of the hierarchy on a spatial database is determined by its result on arbitrary large subsets of the database. The latter is the class of all the monotonic spatial transformations. We give a sound and complete language for the monotonic spatial transformations that can be expressed in the relational calculus augmented with polynomial inequalities and that belong to a class with a finite number of degrees of freedom. In particular, we show that these transformations are finite unions of transformations that can be written in a particular conjunctive form. We also address the problem of finding sound and complete languages for monotonic transformations that are expressible in the calculus and have an infinite number of degrees of freedom. We show that Lyndon’s theorem, which is known to fail in finite model theory, also fails in this setting: monotonic spatial transformations expressible in the calculus do not correspond to the transformations expressible by a positive formula. We show that it is undecidable whether a query expressed in the relational calculus augmented with polynomial inequalities is a monotonic spatial transformation of a certain degree. On the other hand, various interesting properties (e.g., equivalence, genericity), which are undecidable for general spatial transformations expressible in the calculus, become decidable for monotonic spatial transformations of finite degree.