Title
Degrees of monotonicity of spatial transformations
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Subject
Computer. Automation
Source (journal)
Database programming languages
Volume/pages
1369(1998) , p. 60-77
ISSN
0302-9743
ISI
000082725500005
Carrier
E
Target language
English (eng)
Affiliation
University of Antwerp
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000082725500005&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000082725500005&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle