Decomposing Spatial Databases and Applications

Topological invariants of spatial databases (i.e., finite structures that capture the topological properties of the database) have recently received increasing attention mainly in the framework of query languages. Actually, topological invariants can act as a basic structure to tackle relevant problems in the field. It turns out that the main concern in these problems is the manipulation of topological invariants by means of efficient algorithms. To this aim, we introduce the notion of "boundary decomposition" of a topological invariant, and give a polynomial time algorithm to compute such a decomposition. As a relevant application, we use the boundary decomposition as the basis for devising a polynomial time algorithm for testing the topological equivalence of two $2$-dimensional spatial databases. Other applications of the boundary decomposition are mentioned in the paper.