Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/645

Title: Degrees of Monotonicity of Spatial Transformations
Authors: KUIJPERS, Bart
Issue Date: 1997
Publisher: Springer-Verlag
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.
URI: http://hdl.handle.net/1942/645
DOI: 10.1007/3-540-64823-2_5
ISBN: 978-3-540-64823-9
Type: Proceedings Paper
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A172.35 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.