Document Server@UHasselt >
Research publications >
Please use this identifier to cite or link to this item:
|Title: ||Degrees of Monotonicity of Spatial Transformations|
|Authors: ||KUIJPERS, Bart|
|Issue Date: ||1997|
|Citation: ||Database Programming Languages. p. 60-77.|
|Series/Report: ||Lecture Notes in Computer Science, 1369|
|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.|
|Type: ||Proceedings Paper|
|Appears in Collections: ||Research publications|
Files in This Item:
|N/A||172.35 kB||Adobe PDF|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.