Indexing Constraint Databases by Using a Dual Representation
Elisa Bertino, Barbara Catania, Boris Chidlovskii
Constraint databases have been proposed as a powerful framework to model spatial and temporal data. In a
constraint relational database, a spatial object is represented as a quantifier free conjunction of linear
polynomial constraints. The use of constraint databases should be supported by access data structures that
make effective use of secondary storage and reduce query processing time. Such structures should be able
to store both finite and infinite objects and perform both containment (ALL) and intersection (EXIST) queries.
As standard indexing techniques have certain limitations at providing such features, we employ the concept of
geometric duality for designing new indexing techniques. In this paper, we present two approximation
techniques for the dual representation of spatial objects, based on the B^+-tree. The approximation techniques
do not distinguish both finite and infinite objects and process both ALL and EXIST selections in a uniform way.
We show the practical applicability of the proposed technique by an experimental comparison to R^+-trees.
Proc. IEEE Int.Conf. Data Engineering, March 1999, Sydney, Australia
camera.ps.gz (62.62 kB)