Publication
Title
Degrees of monotonicity of spatial transformations
Author
Abstract
We consider spatial databases that can be defined in terms of polynomial inequalities, and we are interested in monotonic transformataions 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 Ic 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.
Language
English
Source (journal)
Lecture notes in computer science. - Berlin, 1973, currens
Publication
Berlin : 1998
ISSN
0302-9743 [print]
1611-3349 [online]
Volume/pages
1369(1998), p. 60-77
ISI
000082725500005
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 29.02.2012
Last edited 20.07.2017
To cite this reference