This paper introduces a formalization of a set of spatial semantic integrity constraints on an extended-relational database model. The formalization extends traditional notions of functional and inclusion dependencies by adding interaction with spatial attributes. This enables to specify implicit and explicit topological conditions between geometries and impose constraints on thematic attributes that depend on the geometries. We study the consistency problem for this set of integrity constraints, which rises issues about topological consistency and realizability of spatial constraints. We show that the consistency problem is not tractable and provide some conditions under which it is.
Spatial databases systems enhance traditional databases with models and query languages that support spatially referenced data and provide spatial indexing and efficient algorithms for spatial query processing [8]. The use of spatially referenced data is an essential component of such diverse applications as Geographic Information Systems (GIS), Computer-Aided Design (CAD), multimedia information systems, data warehousing, mobile computing, location-based services, and NASA's Earth Observing System (EOS).
Fundamental to spatial databases are the spatial data models or geometric models that represent objects in a space. Examples of such models are the spaghetti [18], topological [9,18], and polynomial models [14]. Most of the current spatial database management systems (SDBMSs) implement extensions to relational databases, so called object-relational or extended-relational databases, by defining spatial data types that represent the geometry of objects in the Euclidean space (e.g. Postgres+Posgis, Oracle Spatial SQL, and MySql Spatial).
In the context of database consistency, spatial databases offer new challenges due, particularly, to the complex nature of spatial attributes, the derivation of implicit relations from spatial attributes, and the combination of spatial and non-spatial attributes (called thematic attributes). SDBMSs enforce integrity constraints used for preventing structural inconsistency of spatial attributes (i.e. domain constraints in the relational context). For example, they enforce that regions must be represented by closed and simple polylines [2]. The other important type of spatial integrity constraints, which are not implemented in SDBMs, are the spatial semantic integrity constraints (also known as topo-semantic integrity constraints) that relate geometries with semantic conditions. For example, a semantic constraint can enforce that a city's administrative region must be contained within its corresponding city limits [17]. These constraints are less formalized and are highly dependent on the application.
In this work we define a constraint language to specify spatial semantic constraints. This language extends functional and inclusion dependency constraints to combine spatial and thematic attributes.
Example 1. Consider a spatial database that stores information of land parcels and buildings using the schema R = {Landparcel (id ,owner ,area,g), Building(id , use,g)}. In predicate Landparcel , the thematic attributes are id , owner , and area (in m 2 ), and the only spatial attribute is g that stores the geometry of each land parcel. Similarly for Building, which has id and use as thematic attributes and g as spatial attribute. Figure 1 shows an instance of this schema. In it, dark rectangles represent buildings and white rectangles represent land parcels.
In this database, we need traditional constraints to enforce that attribute id is unique in both predicates. But, there are other relations that cannot be captured by traditional functional dependencies or inclusion dependencies. For example, we need spatial constraints to ensure that land parcels do not overlap, that each building is inside a land parcel, and that the value in attribute area corresponds to the area of the spatial attribute g in predicate landparcel . 2
Some studies have addressed the specification of spatial integrity constraints [1,10,12]; however, they treat spatial data in isolation from other integrity constraints, this is, without considering the interaction with the thematic attributes.
Other studies have analyzed topological [6,12] and realizability [7] problems.
The topological problem analyzes the consistency of topological relations as expressed by inference tables. The realizability problem, on the other hand, analyzes whether or not there is a set of geometries that realizes a set of topological relations. These problems differ from the database consistency problem, or simply consistency problem, in which the goal is to determine if there is a non-empty database instance that satisfies a set of integrity constraints. In the consistency problem the number of geometries in a database instance that must satisfy a set of constraints is unknown. For topological and realizability problems, instead, there exists a pre-defined number of geometries that must satisfy a set of constraints expressed by the possible topological relations between them. To the best of our knowledge, the consistency problem of spatial integrity constraints has not been studied so far. This is why in this paper we formalize a set of spatial semantic integrity constraints that: (i) generalizes traditional functional and inclusion dependencies, (ii) enables to specify topological relations between spatial objects, (iii) enables to relate both spatial and thematic attributes, and (iv) are expressive enough to capture constraints found in practice. Furthermore, we reason about these constraints and determine whether or not the set of integrity constraints is consistent, i.e., if there is a non-empty database instance that satisfies the set of constraints. We show that this problem is not tractable and provide some conditions under which it is.
The organization of this paper is as follows. In Section 2 we present the data model used to represent spatial databases. Then, in Section 3 we present the set of spatial semantic constraints for which we will study the consistency problem in Section 4. Finally, in Section 5 we briefly discuss related work and give conclusions.
Current models of spatial data are typically seen as extensions of the relational data model (object-relational models), with the definition of abstract data types to specify spatial or geometric attributes. We now introduce a general spatiarelational data model that includes spatia-relational predicates (that can be purely relational) and also spatial ICs. It uses some of the definitions introduced in [15] and is independent of the geometric data model underlying the representation of spatial data types.
A spatia-relational database schema is of the form Σ = (U, A, S, R, T , O), where: (a) U is the possibly infinite database domain of atomic thematic values that includes R. (b) A = {A 1 , . . . , A n } where each A i is a thematic attribute which takes values in R. (c) S = {S 1 , . . . , S n } where each S i takes admissible values in P(R 2 ), the power set of R 2 . (d) R is a finite set of spatia-relational predicates each of them with a finite and ordered set of attributes belonging to A or S. We sometimes use R(A 1 , . . . , A n ) to represent the predicate with its set of attributes. (e) T is a fixed set of binary topological predicates. (f) O is a fixed set of geometric operators that take spatial and thematic arguments and return a geometry or a value in U.
A database instance D of a spatia-relational schema Σ is a finite collection of ground atoms (or spatial database tuples) of the form
where Ad is the class of closed regions in the topological space formed by point sets of the Euclidean space. These regions represent real objects that have geographic extent, this is, they are not empty.
The elements of T are binary topological relations with a fixed semantics. There are eight basic binary relations: Overlaps (O), Equal (EQ ), CoveredBy (CB ), Inside (IS ), Covers (CV ), Includes (IC ), Touches (TO), and Disjoint (D ) [16,5] 1 . In addition to the basic topological relations, SQL languages consider some derived relations that can be logically defined in terms of the other basic predicates: Intersects (IT ), Within (W ), and Contains (C) [13]. A lattice showing how these relations are grouped to derive new relations is shown in Figure 2. The eight basic relations are shown in boxes containing prototypical cases and the relations included in current SQL are represented with thick borders. For example, Contains is obtained by grouping Equal, CoveredBy and Includes, this is,
Observe that relation IDisjoint (IDC) (internally disjoint) was added even though it is neither basic nor used in SQL. Nonetheless, it is added because it is useful to represent situations found in practice. In what follows we assume that T contains all the relations shown in Figure 2. Given a database instance, additional spatial information is usually computed from the explicit geometric data by means of the spatial operators in O. Some relevant operators are: Area, Union, Intersection and Difference (cf. [13] for the complete set of spatial predicates defined within the Open GIS Consortium).
In this section we present a set of spatial semantic integrity constraints that generalizes classic integrity constraints and that are capable of dealing with spatial data.
To simplify the presentation we will use the following notation: (i) variables x, y, z, x 1 , x ′ , . . . represent values in U or geometries, (ii) variables g, g 1 , g ′ , . . . represent geometries, and (iii) variables u, v, w, u 1 , u ′ , . . . represent values in U. (iv) symbols x, ū, x1 , . . . denote a possibly empty sequence of distinct variables or, with a slight abuse of notation, a set of variables. Definition 1. A spatial semantic integrity constraint (SSIC) is one of the following: Functional Dependency (FD):
∀ūx(P (ū, x) → ∃ȳR(ū, ȳ)) Topological Dependency (TD):
where ȳ1 ∩ ȳ2 = ∅ and for every i, variable v i ∈ ȳ1 and variable w i ∈ ȳ2 .
∀ūxg
where ⊙ ∈ {>, =, =} and terms t 1 and t 2 are constructed from variables in x and operators in O.
2
FDs and INDs correspond to the traditional constraints since there are no joins nor references between geometrical attributes. Indeed, spatial attributes are not used in keys nor in referenced attributes since that would have a high computational cost associated in terms of space and time. Also, from a practical point of view, geometries by themselves do not identify spatial objects, so they need some kind of thematic key. TDs enforce topological relations between spatial attributes and RDs enforce inclusion dependencies where the spatial attributes of the referenced table should have some particular spatial properties. Finally, comparison constraints can be used to compare values within a tuple in P . Note that none of the constraints considers joins on geometric attributes. Since all the topological relations in T have their converse (or inverse) relation in T , there is no need to have an RD with T (g 2 , g 1 ) in replacement of T (g 2 , g 1 ). Indeed the constraint ∀xg 1 (P (x, g 1 ) → ∃g 2 R(x, g 2 ) ∧ CoveredBy(g 2 , g 1 ) can be replaced by ∀xg 1 (P (x, g 1 ) → ∃g 2 R(x, g 2 ) ∧ Covers(g 1 , g 2 ). Example 2. (example 1 cont.) The following SSICs can be defined:
∀ (Building(u, v, g) → ∃xyzg ′ (Landparcel(x, y, z, g ′ ) ∧ Within(g, g ′ )))
Functional dependencies (1-2) together with topological dependency (3) ensure that id is a key of table Landparcel. In the same way, constraints (4-5) enforce that id is a key of Building. The topological dependencies ( 6) and ( 7) ensure that land parcels and buildings, respectively, are either adjacent or disjoint. Finally, the comparison constraint (9) forces attribute area to contain the area of the spatial attribute g. 2
Before checking if a database satisfies a set of spatial semantic constraints, we need to make sure that the constraints themselves are not in conflict. Thus, we first need to check if the integrity constraints are consistent.
The consistency problem for a database schema Σ and a set of ICs IC , consists on determining whether there exists a non-empty database instance D over Σ that satisfies IC . This is, checking if there exists a nontrivial database that satisfies the constraints.
This consistency problem is related but different from the topological and realizability problems [6,7]. A set of topological relations defined over a set of objects is said to be topologically consistent if there are no contradictions among the relations. For example three objects A, B and C and the relations Covers(A, B), Covers(B, C), Disjoint(A, C) are topologically inconsistent since the first two relations imply that A and C cannot be disjoint. There are some cases in which even if the topological relations are not inconsistent, the geometries may not be realizable due to reasons of planarity, this is, there are no geometries in R 2 that satisfy those relations. The problem of determining if those geometries exist is the realizability problem.
Those problems differ from our consistency problem for two reasons. First, since we do not know in which tables we have tuples nor how many tuples there are, it is unknown the number of objects there are in the spatial database. Second, we do not know the topological relations that will be imposed since that will depend on the values not only in the spatial attributes but in the thematic attributes. Even though the problems differ from the consistency problem, some settings of the topological and realizability problem can be reduced to the consistency problem.
The following example illustrates the case when the topological relations imposed by spatial integrity constraints contradict topological consistency. Example 3. (example 2 cont.) Consider the set of integrity constraints imposed in example 2. The database administrator could have, by mistake, written constraints ( 6) and ( 7) as follows:
The first constraint will also be checked when u = u ′ and therefore it requires that a land parcel should be disjoint of or adjacent to itself. This, of course, is not possible. The second constraint enforces the same for Building. Since none of the predicates can contain tuples, the set of ICs is inconsistent.
2
The following example shows a situation in which, even though the topological relations are consistent, it is not possible to find geometries in R 2 that satisfy them, this is, the geometries are not realizable.
Fig. 3. The non-planar graph K5
Example 4. A graph is said to be non-planar if it is not possible to draw it in the plane without edge intersection. A well known example of non-planar graph is K 5 , the complete graph with five nodes (see Figure 3). In this graph, even though all the topological relations are satisfied, it is not realizable in the plane. We can map the topological relations on K 5 as a set of spatial integrity constraints IC 5 defined over a schema S 5 in such a way that the set of constraints is consistent iff K 5 can be drawn in the plane. Let S 5 contain five and ten spatia-relational predicates of the form X i (id, g i ) and Y j (id, g j ) respectively, which represent the nodes and edges of K 5 , respectively, and where id is a thematic attribute, and g i and g j are spatial attributes. Now, let IC 5 contain:
1. For all Z ∈ {X 1 , . . . , X 5 , Y 1 , . . . , Y 10 } ∀ug 1 g 2 (Z(u, g 1 ) ∧ Z(u, g 2 ) → Equal(g 1 , g 2 )) 2. For all X i ∈ {X 1 , . . . , X 5 } and Y j ∈ {Y 1 , . . . , Y 10 }, where X i and Y j are incident in K 5 :
The INDs enforce that if there is a tuple in any predicate, there will be at least one tuple in all the rest. Since a database is consistent if there is at least one tuple in the database, this constraints will ensure that there is at least one tuple in every predicates. The TDs enforce the topological relations between the different nodes and edges. It is easy to see that IC 5 is consistent iff K 5 is planar. Since K 5 is not planar, there is no non-trivial database that satisfies IC 5 . This situation is interesting since the topological relations enforced by the TDs are not contradictory, but it is not possible to find tuples with objects in two dimensions that satisfy them.
2
The constraints we have defined are able to express most of the constraints commonly needed in spatial databases. However, this expressiveness comes with a cost: the consistency problem for SSICs is not tractable.
Proposition 1. The consistency problem for SSIC is np-hard. 2
Proof. Hardness can be proven by reduction of the explicit low level conjunctive realizability problem [7] which is np-complete. This problem consists in determining if there exists a planar model that satisfies a conjunctive topological expression like
More formally it consists on determining if for a set of objects O there exists a planar model for the topological expression ψ
for every A, B ∈ O such that A = B there exists • ∈{intersects,disjoint} such that (A • B) ∈ ψ. The problem is said to be "explicit" since for every pair of objects there always exists a relationship which is unique.
We need to construct a set of constraints IC ψ defined over a schema Σ ψ such that IC ψ is consistent iff there exists a planar model of ψ for objects in O. Let Σ ψ = (R, A, S, R, T , O) where A = {id}, S = {g} and R = {P A (id, g)|A ∈ O}, T = {Intersects, Disjoint} and O = ∅. Let IC ψ contain:
1. For every P A ∈ R, a topological dependency: ∀ug 1 g 2 (P A (u, g 1 ) ∧ P A (u, g 2 ) → Equal(g 1 , g 2 )) 2. For every A, B ∈ O where A = B, the spatial referential dependency: ∀ug 1 (P A (u, g 1 ) → ∃g 2 (P B (u, g 2 ) ∧ T (g 1 , g 2 )))
where
each relation represents one of the objects in ψ, the TDs enforce that for each relation and value u in the first attribute there is a unique geometry, and RDs enforce that all the objects sharing the same value in attribute id satisfy the topological constraints given in ψ.
First let us show that if IC ψ is consistent, then there is a planar model for ψ. If IC ψ is consistent, there exists a database D defined over Σ ψ that satisfies the constraints and that has at least one tuple in one of the relations. Then, from constraints in (2), it follows that every relation will have at least one tuple. Furthermore, for every predicate P A there exists a constant c and a geometry g A such that (c, g A ) ∈ P A . Since this geometries will also satisfy the topological constraints, if we assign to each object A i geometry g Ai , we have found a planar model for ψ. Now, let us prove that if there is planar model of ψ, IC ψ is consistent. For every object A ∈ O, let g A be the geometry of A in the planar model of ψ. Now, choose a constant c ∈ U and let D be such that (c, g A ) ∈ P A for every A ∈ O. Clearly D satisfies IC ψ and IC ψ is consistent.
2
It is an open problem to determine if the realizability problem used in the reduction is in np since in some cases the objects need to be of exponential size.
A natural question is if we can find a set of constraints which are less expressive than SSIC, but that is still useful and tractable. We now explore the use of constraints that do not consider geometric operators O nor built-ins B. Definition 2. A basic spatial integrity constraints (BSIC) is one of the following: Functional Dependency (FD):
Even though these constraints are much simpler, the consistency problem is still np-hard. This follows directly from the proof in the general case since only TD 0 s and RD 0 s are used.
Corollary 1. The consistency problem for BSIC constraints is np-hard. 2
However, these constraints have better properties in some cases. For example consistency of a set of FDs and TD 0 s can be checked in polynomial time.
Proposition 2. Consistency of a set of FDs and TD 0 s can be checked in polynomial time.
Proof. First, observe that if a set IC of FDs and TD 0 s is consistent, then there will exist a database with only one tuple in one predicate that satisfies the constraints. Thus, a possible algorithm consists on checking in each predicate P if a tuple with fresh constants in each attribute satisfies the FDs and TD 0 s defined over it. If this is true in any of the predicates, then the set IC is consistent. Otherwise, it is not. 2
A more general an interesting result is that if there are no cycles through INDs and RD 0 s, consistency can be checked in polynomial time.
Definition 3. Given a schema S and a set of BSIC IC , let the dependency graph G of IC be a digraph where the nodes corresponds to predicates in S with an edge from predicate P to R if there is an IND ∀ūx(P (ū, x) → ∃ȳR(ū, ȳ)) or a RD 0 ∀ūxg 1 (P (ū, x, g 1 ) → ∃ȳg 2 R(ū, ȳ, g 2 ) ∧ T (g 1 , g 2 )) in IC . A set of BSICs is said to be acyclic if its dependency graph is acyclic. 2 Proposition 3. Consistency of an acyclic set of BSICs can be checked in polynomial time.
Proof. If a set IC of acyclic BSICs is consistent, then there will exist a database with only one tuple in a leaf predicate that satisfies the constraints. Thus, IC is consistent iff one of the leafs satisfies its FDs and the TD 0 . Since consistency of FDs and the TD 0 can be done in polynomial time, consistency of IC can be checked in polynomial time. 2
In the spatial domain, some related studies address the specification of topological constraints (domain constraints) [1] and spatial semantic constraints [12,10].
There have been also studies concerning models for checking topological consistency at multiple representations and for data integration [4,19,6,11]. In all these studies, however, the consistency problem has not been addressed, and spatial integrity constraints have been treated without considering the interaction with thematic attributes in a database model. The specification of constraints involving topological relations and alphanumeric attributes was studied at the conceptual level in [3]. This study, however, does not address the association of the constraints at the conceptual level with already existing semantic constraints at the logical level. Unlike previous works, we have presented a formalization of integrity constraints that combine thematic with spatial attributes in a database model and that extends classical notions of functional and inclusion dependency. We have analyzed the consistency problem and found that it is not tractable in general. However, we have identified an interesting case for which the problem can be solved in polynomial time.
We plan to extend our results by analyzing other interesting cases in which the problem is tractable and to develop heuristics for those cases that it is not. In this direction, we would like to study the complexity of the consistency problem if we remove the requirement of realizability and only require topological consistency. This can be easily achieved by assuming that the spatial attributes take values in R 3 instead of R 2 . Since the topological consistency problem is tractable in most settings, this can be a good approximation of the consistency problem.
Acknowledgements. This work is funded by Bicentenario Program PSD 57. Andrea Rodríguez is also funded by Fondecyt 1080138, and Loreto Bravo by Fondecyt 11080260, Conicyt -Chile.