Identification Constraints and Functional Dependencies in Description Logics

1 Introduction

In the last years, Description Logics (DLs) have been successfully applied to data management [Borgida, 1995; Kirk et al., 1995; Calvanese et al., 1998b; 1999]. One of the basic ideas behind applying DLs to data management is that database schemas can be expressed as DL knowledge bases, so that DL reasoning techniques can be used in several ways to reason about the schema. In [Calvanese et al., 1998a; 1998b], a very expressive DL with n-ary relations, called DLR, is introduced, and it is shown how database schemas can be captured by this logic. Also, suitable mechanisms for expressing queries over DLR schemas have been added, and techniques for reasoning over queries have been designed. Notably, the investigation on DLR has led to the design of new DL systems effectively implementing powerful reasoning techniques [Horrocks et al., 1999].

Although the above mentioned work has been the crucial step for applying DL technology to data management, there is one important aspect of database schemas that DLs, including DLR, do not capture yet, namely the notion of identification constraints and functional dependencies. Identification constraints (also called keys) are used to state that a certain set of properties uniquely identifies the instances of a concept. A functional dependency on a relation is used to impose that a combination of a given set of attributes functionally determines another attribute of the relation. It is easy to see that functional dependencies can be used to model keys of a relation, i.e., attributes that are sufficient to identify tuples of the relation. Both types of constraints are commonly used in database design and data management.

The question addressed in this paper is as follows: can we add identification constraints and non-unary functional dependencies to DLR and still have EXPTIME associated reasoning techniques? Somewhat surprisingly, we answer positively to the question, by illustrating an approach that allows us to incorporate both types of constraints in DLR. In particular, we adapt the DLR reasoning algorithm in such a way that reasoning on a DLR schema with both types of constraints and with ABoxes, can be done with the same worstcase computational complexity as for the case of plain DLR. Also, the proposed technique can be incorporated into present DL systems, such as the one described in [Horrocks et al., 1999]. We also show that adding to DLR unary functional dependencies leads to undecidability of reasoning. Observe, however, that the presence of such functional dependencies is typically considered as an indication of bad schema design in databases.

Both identification constraints and functional dependencies have been extensively investigated in the database literature (see [Abiteboul et al., 1995], Chapters 8, 9). However, database models lack the kinds of constraints expressible in expressive DLs, and therefore none of the results developed in the context of databases can be used to solve our problem.

In the last years, there have been some attempts to add identification constraints to DLs. In [Calvanese et al., 1995], these constraints are modeled by means of special primitive concepts in an expressive DL, and it is shown that this mechanism allows some inference on keys to be carried on. The limitation of this approach is that several interesting semantic properties of keys are not represented in the knowledge base. In [Borgida and Weddell, 1997; Khizder et al., 2001], a general mechanism is proposed for modeling path functional dependencies, and a sound and complete inference system for reasoning on such constraints is presented. Path functional dependencies are sufficiently expressive to model both identification constraints and functional dependencies. However, the DLs considered are limited in expressiveness. In particular, union, negation, number restrictions, general inclusion axioms, inverse roles and n-ary relations are not part of the considered language, and therefore useful properties of database schemas cannot be represented. The proposal presented in this paper fully captures the semantics of both identification constraints and functional dependencies in an expressive DL with all the above features.

The paper is organized as follows. In Section 2, we recall the DL DLR. In Section 3, we illustrate the mechanism for specifying identification constraints and functional dependencies in DLR knowledge bases. In Section 4, we discuss the modeling power of the resulting logic, called DLRifd . In Section 5, we describe how we can extend the DLR reasoning technique in order to take the new types of constraints into account, and in Section 6 we show that minor extensions of DLRifd leads to undecidability of reasoning. Finally, Section 7 concludes the paper.

2 Description Logic DLR

We focus on the Description Logic DLR, which is able to capture a great variety of data models with many forms of constraints [Calvanese et al., 1998a; 1999]. The basic elements of DLR are concepts (unary relations), and n-ary relations.

We assume to deal with a finite set of atomic relations (having arity between 2 and nmax) and atomic concepts, denoted by P and A, respectively. We use R to denote arbitrary relations and C to denote arbitrary concepts, respectively built according to the following syntax:

where n denotes the arity of the relations P, R, R1, and R2, i denotes a component of a relation, i.e., an integer between 1 and n, and k denotes a non-negative integer. Observe that we consider only concepts and relations that are well-typed, which means that: (i) only relations of the same arity n are combined to form expressions of type R1 ⊓R2 (which inherit the arity n); (ii) i ≤ n whenever i denotes a component of a relation of arity n.

We introduce the following abbreviations: ⊥ for ¬⊤1; C1⊔C2 for ¬(¬C1⊓¬C2); C1 ⇒C2 for ¬C1⊔C2; (≥ k [i]R) for ¬(≤ k-1 [i]R); ∃[i]R for (≥ 1 [i]R); ∀[i]R for ¬∃[i]¬R. Moreover, we abbreviate (i/n :C) with (i :C) when n is clear from the context.

A DLR TBox is constituted by a finite set of inclusion assertions, where each assertion has one of the forms:

with R1 and R2 of the same arity.

The semantics of DLR is specified as follows. An interpretation I is constituted by an interpretation domain ∆I , and an interpretation function ·I that assigns to each concept C a subset C I of ∆I and to each relation R of arity n a subset RI of (∆I )n such that the conditions in Figure 1 are satisfied. In the figure, t[i] denotes the i-th component of tuple t. Observe that, the "¬" constructor on relations is

Figure 1: Semantic rules for DLR (P, R, R1, and R2 have arity n, and ♯σ denotes the cardinality of the set σ)

used to express difference of relations, and not the complement [Calvanese et al., 1998a]. An interpretation I satisfies an assertion C1 ⊑ C2 (resp., R1 ⊑ R2) if C I 1 ⊆ C I 2 (resp., RI 1 ⊆ RI 2 ).

We introduce a generalized form of DLR ABox. We consider an alphabet of new symbols, called Skolem constants (sk-constants). Intuitively, an sk-constant denotes an individual in an interpretation, in such a way that different skconstants may denote the same individual.

A generalized DLR ABox (or simply ABox in the following) is constituted by a finite set of assertions, called ABox assertions, of the following types:

where R is a relation of arity n, and x, y, x1, . . . , xn are skconstants.

The notion of interpretation is extended so as to assign to each sk-constant x an individual xI ∈ ∆I . An interpretation I satisfies

• C(x) if xI ∈ C I ;
• R(x1, . . . , xn) if (xI1 , . . . , xIn ) ∈ RI ;
• x ̸= y if xI ̸= yI ;
• x = y if xI = yI .

If T is a DLR TBox, and A is a DLR ABox of the above form, then K = T ∪ A is called a DLR knowledge base. An interpretation is a model of K if it satisfies every assertion in K. A knowledge base K is satisfiable if it has a model. An assertion α (either an inclusion, or an ABox assertion) is logically implied by K if all models of K satisfy α.

Logical implication and knowledge base satisfiability are mutually reducible to each other. For one direction, K is unsatisfiable iff K |= ⊤1 ⊑ ⊥. For the converse direction, it is possible to show that K |= C1 ⊑ C2 iff K ∪ {⊤1 ⊑ ∃[1](P ⊓ (2 : C1 ⊓ ¬C2))} is unsatisfiable, where P is a new binary relation. Similarly, K |= R1 ⊑ R2 iff K ∪ {⊤1 ⊑ ∃[1](P ⊓ (2 : ∃[1](C1 ⊓ ¬C2)))} is unsatisfiable, where again P is a new binary relation. Finally, K |= C(α) iff K ∪ {¬C(α)} is unsatisfiable.

It follows from the results in [Calvanese et al., 1998a], that checking a DLR knowledge base for satisfiability is EXPTIME-complete.

3 Identification and Functional Dependency Assertions

We extend DLR with identification constraints and functional dependencies. The resulting DL, called DLRifd, allows one to express these constraints through new kinds of assertions in the TBox.

An identification assertion on a concept has the form:

where C is a concept, each Rj is a relation, and each ij denotes one component of Rj. Intuitively, such an assertion states that two instances of C cannot agree on the participation to R1, . . . , Rh via components i1, . . . , ih, respectively.

A functional dependency assertion on a relation has the form:

where R is a relation, h ≥ 2, and i1, . . . , ih, j denote components of R. The assertion imposes that two tuples of R that agree on the components i1, . . . , ih, agree also on the component j.

We assign semantics to these assertions by defining when an interpretation satisfies them. Specifically:

• An interpretation I satisfies the assertion (id C [i1]R1, . . . , [ih]Rh) if, for all a, b ∈ C I and for all t1, s1 ∈ RI 1 , . . . , th, sh ∈ RIh , we have that:

• An interpretation I satisfies the assertion (fd R i1, . . . , ih → j) if, for all t, s ∈ RI , we have that:

A DLRifd knowledge base is a set K = T ∪ A ∪ F of assertions, where T ∪ A is a DLR knowledge base and F is a set of identification and functional dependency assertions.

Note that unary functional dependencies (i.e., functional dependencies with h = 1) are ruled out in DLRifd . We will come to this in Section 6. Note also that the right hand side of a functional dependency contains a single element. However, this is not a limitation, because any functional dependency with more than one element in the right hand side can always be split into several dependencies of the above form. Also, to verify whether a functional dependency with more than one element in the right hand side is logically implied by a DLRifd knowledge base, it suffices to verify whether each of the functional dependencies in which it can be split, is logically implied by the knowledge base.

4 Modeling in DLRifd

DLRifd captures database schemas expressed in several data models . For example, Entity-Relationship schemas can be represented already in DLR, by modeling each entity as a concept, and each relationship as a relation [Calvanese et al.,

1998b; 1999]. Attributes of entities are modeled by means of binary relations, and single-valued or mandatory attributes are expressible through the use of number restrictions. Attributes of relationships can be modeled in several ways, for instance through special (n + 1)-ary relations, where n is the arity of the relationship. Also, integrity constraints such as is-a, cardinality, existence, and typing constraints are expressible by means of inclusion assertions. Finally, unary keys (keys constituted by a single attribute) can be modeled through number restrictions. Non-unary keys cannot be represented in DLR, while they are obviously expressible in DLRifd .

Example 1 Suppose that Person and University are concepts, EnrolledIn is a binary relation between Person and University, and StudentCode is an (optional) attribute (modeled as a binary relation) of Person associating to each student (a person who is enrolled in a university) a code that is unique in the context of the university in which she is enrolled. Such a situation can be represented by the following DLRifd TBox:

EnrolledIn ⊑ (1 : Person) ⊓ (2 : University) StudentCode ⊑ (1 : Person) ⊓ (2 : String) Person ⊑ (≤ 1 [1]StudentCode) (id Person [1]StudentCode, [1]EnrolledIn)

Note that, the notion of student is modeled by the concept Person ⊓ ∃[1]EnrolledIn and, in the conceptual modeling terminology, this concept is a weak entity, i.e., part of its identifier is external through the relationship EnrolledIn.

We additionally want to model the notion of exam in our application. An exam is a relationship involving a student, a course, a professor, and a grade. In an exam, the combination of student and course functionally determines both the professor, and the grade. This can be represented by adding the following assertions to the TBox:

Exam ⊑ (1 :(Person ⊓ ∃[1]EnrolledIn)) ⊓ (2 : Course) ⊓ (3 : Person) ⊓ (4 : Grade) (fd Exam 1, 2 → 3) (fd Exam 1, 2 → 4)

Observe that generally, in conceptual data models, if an attribute (or a relationship) L is part of a key for an entity E, then in the database schema it must be the case that E has a single and mandatory participation in L, i.e., each instance of E has exactly one associated value for L [Abiteboul et al., 1995]. This is not required in DLRifd (but can be asserted when needed), where one can define an attribute as part of a key of an entity, even if the attribute is multi-valued or optional.

We have mentioned that unary functional dependencies are not allowed in DLRifd. However, this limitation does not prevent one from defining unary keys for relations. Indeed, the fact that component i is a key for the relation R can already be expressed in DLR by means of the assertion:

The above observation also implies that functional dependencies in the context of binary relations, which are by definition unary, are expressible in DLRifd. Indeed, such functional dependencies correspond to key constraints, which are expressible as specified above. For example, the functional dependency 1 → 2 in the context of the binary relation R can be expressed by specifying that component 1 is a key for R. Thus, the only functional dependencies that are not admitted in DLRifd are unary functional dependencies in the context of non-binary relations. This is because they lead to undecidability of reasoning, as shown in Section 6. Note also, that the presence of such functional dependencies is considered as an indication of bad design in the framework of the relational data model (see [Abiteboul et al., 1995], Chapter 11). In fact, a unary functional dependency in the context of an n-ary relation (with n > 2) represents a hidden relationship between the arguments of the relation, which may cause several modeling problems.

The possibility of defining identification constraints substantially enriches the modeling power of DLs. In particular, it is possible to show that, even if only binary relations are allowed in a DL, then the use of identification constraints permits simulating the presence of n-ary relations in such a logic. For example, a relation with arity 3 can be modeled by means of a concept and 3 binary relations. Number restrictions are used to state that every instance of the concept participates in exactly one instance of the binary relation, and a suitable identification assertion states that the combination of the three binary relations form a key for the concept. Obviously, DLRifd further increases the modeling power by allowing the explicit use of n-ary relations, and the possibility of imposing functional dependencies in the context of relations.

5 Reasoning on DLRifd

First of all we observe that, when reasoning in DLRifd , identification assertions of the form (id C [i]R), where R is a binary relation, are equivalent to DLR assertions ⊤ ⊑ (≤ 1 [j](R ⊓ (i :C))), where j =2 if i=1, and j =1 if i=2. Hence, in the following, without loss of generality, we will not consider such identification assertions.

Next we show that we can reduce logical implication in DLRifd to knowledge base satisfiability. As already observed in Section 2, logical implication of inclusion and ABox assertions can be reduced to knowledge base satisfiability. We show that the same can be done also for identification and functional dependency assertions.

Given an identification assertion

we define the ABox Aκ constituted by the following assertions:

• C(x), C(y), and x ̸= y, where x and y are new skconstants;
• Rj(tj) and Rj(sj), with j ∈ {1, . . . , h}, where tj and sj are tuples of new sk-constants with tj[ij] = x, sj[ij] = y, and tj[i] = sj[i] for i ̸= ij.

Similarly, for a functional dependency assertion

we define Aκ constituted by the following assertions:

• R(t), R(s), and t[j] ̸= s[j], where t and s are tuples of new sk-constants with t[ij ] = s[ij ], for j ∈ {1, . . . , h}.

From the semantics of identification and functional dependency assertions it is immediate to see that Aκ provides a concrete counterexample to κ. Hence it follows that, given a DLRifd knowledge base K, K |= κ if and only if K ∪ Aκ is unsatisfiable.

Theorem 2 Logical implication in DLRifd can be reduced to knowledge base satisfiability.

We now present a reasoning procedure for knowledge base satisfiability in DLRifd .

DLRifd TBoxes (which in fact are DLR TBoxes since they do not include identification and functional dependency assertions) have the tree-model property [Calvanese et al., 1998a], which is true for most DLs. In particular, if a DLR TBox admits a model, it also admits a model which has the structure of a tree, where nodes are either objects or (reified) tuples, and edges connect tuples to their components. Observe that in such models identification and functional dependency assertions (which in DLRifd are non-unary) are trivially satisfied, since there cannot be two tuples agreeing on more than one component. As an immediate consequence we have that, given a DLRifd TBox T and a set of identification and functional dependency assertions F, T ∪F is satisfiable iff T is so. This implies that, in absence of an ABox, logical implication of inclusion assertions can be verified without considering identification and functional dependency assertions at all.

When we add an ABox, then we may still restrict the attention to models that have the structure of a tree, except for a cluster of objects representing the sk-constants in the ABox (see again [Calvanese et al., 1998a] 1 ). We call such models clustered tree models. On such models, identification and functional dependency assertions are always satisfied, except possibly for the cluster of sk-constants. Hence we can concentrate on verifying such assertions on the objects and tuples appearing in the ABox only.

Given a DLRifd knowledge base K, we define a saturation of K as an ABox As constructed as follows:

• for each sk-constant x occurring in K, and for each identification assertion (id C [i1]R1, . . . , [ih]Rh) in K, As contains either C(x) or ¬C(x);
• for each tuple t of sk-constants occurring in an assertion R(t) of K,
• for each identification assertion (id C [i1]R1, . . . , [ih]Rh) in K, for each Rj (j ∈ {1, . . . , h}) having the arity of R, As contains either Rj(t) or ¬Rj(t),
• for each functional dependency assertion (fd R′ i1, . . . , ih → j) in K, such that R′ has the arity of R, As contains either R′ (t) or ¬R′ (t);

1 In fact, [Calvanese et al., 1998a] makes use of inclusion assertions involving nominals, i.e., concepts having a single instance. It is immediate to verify that such inclusion assertions correspond to the kind of generalized ABoxes we adopt here.

• for each pair of sk-constants x and y occurring in K, As contains either x = y or x ̸= y.

Note that the size of a saturation is polynomial in the size of K. Note also that there are many (actually, an exponential number) of different saturations of K, one for each possible set of choices in the items above.

On a saturation one can immediately verify whether an identification or functional dependency assertion of K is violated. Indeed, for all sk-constants and tuples of sk-constants appearing in the saturation, membership or non-membership in the relevant relations and concepts appearing in the assertions that could be violated is explicitly asserted (after substituting each sk-constant with a representative of its equivalence class according to the equalities). Hence, it suffices to verify whether the semantic condition of the assertion is violated, considering relations and concepts appearing in the assertion as primitives. Once such a check on the identification and functional dependencies is done, it remains to verify whether As is consistent with the other assertions of K.

Theorem 3 A DLRifd knowledge base K = T ∪ A ∪ F is satisfiable if and only if there exists a saturation As of K that does not violate the identification and functional dependency assertions in K and such that the DLR knowledge base T ∪ A∪As is satisfiable.

Proof (sketch). "⇐" Assume that there exists a saturation As that does not violate the identification and functional dependency assertions in K and such that T ∪A∪As is satisfiable. Then there exists a clustered tree model of T ∪A∪As, and such interpretation is also a model of K.

"⇒" Assume that K is satisfiable. Then from a model I of K one can directly construct a saturation for which I satisfies all assertions.

The above result provides us with an upper bound for reasoning in DLRifd , matching the lower bound holding already for DLR.

Theorem 4 Satisfiability and logical implication in DLRifd are EXPTIME-complete.

Proof (sketch). By Theorem 2, logical implication in DLRifd reduces to knowledge base satisfiability in DLRifd . By Theorem 3, satisfiability of a DLRifd knowledge base K = T ∪ A ∪ F reduces to solving a (possibly exponential) number of tests, where each test involves one saturation As and consists in directly verifying all identification and functional dependency assertions in As (a polynomial step) and checking the satisfiability of the DLR knowledge base T ∪A∪As (an exponential step).

6 Unary functional dependencies in DLRifd

One might wonder whether the method described in the previous works also for unary functional dependencies. Actually, this is not the case since unary functional dependencies are not trivially satisfied in tree structured interpretations. For example, it may happen that two tuples of a relation R agree on say component 1 and not component 2, and therefore violate the functional dependency (fd R 1 → 2).

. . .

. . .

. . .

. . .

. . .

Indeed, we show that if we allow for unary functional dependencies, then reasoning in DLRifd becomes undecidable. To do so we exhibit a reduction from the unconstrained quadrant tiling problem [van Emde Boas, 1997], which consists in deciding whether the first quadrant of the integer grid can be tiled using a finite set of square tile types in such a way that adjacent tiles respect adjacency conditions. Tiling problems are well suited to show undecidability of variants of description and dynamic logics [van Emde Boas, 1997; Baader and Sattler, 1999]. The crux of the undecidability proof consists in enforcing that the tiles lie on an integer grid. Once the grid structure is enforced, it is typically easy to impose the adjacency conditions on the tiles. In our case we exploit unary functional dependencies to construct the grid.

Formally, a tiling system is a triple T = (D, H, V) where D is a finite set of elements representing tile types and H and V are two binary relations over D. The unconstrained quadrant tiling problem consists in verifying the existence of a tiling consistent with T, i.e., a mapping τ from IN× IN to D such that (τ(i, j), τ(i + 1, j)) ∈ H and (τ(i, j), τ(i, j + 1)) ∈ V, for i, j ∈ IN. Such a problem is undecidable, more precisely Π00 -complete [Berger, 1966; van Emde Boas, 1997].

From a tiling system T = (D,H, V) we construct a DLRifd knowledge base KT as follows. The basic idea is to enforce the grid structure shown in Figure 2, where squares represent tuples of arity 4 and circles represent objects. Each object depicted using a bold circle and labeled i, j represents the node (i, j) of the grid. Numbers labeling arrows represent components of tuples. A pair of letters X, Y inside a tuple represents the fact that the tuple is an instance of the relations X and Y . In particular we use four relations of arity 4: A, B, C, and D. The gray box in the figure represents how a tile would be placed in such a grid.

We enforce the grid structure by means of the following assertions in KT :

We enforce the adjacency conditions on the tiles of the first quadrant by using one concept for each tile type in D and introducing in KT the following assertions: for each Di ∈ D

Finally, to represent the origin of the tiling we use the concept C0 = (∃[1]⊤4) ⊓ ⊔Di∈D Di Then the tiling problem associated to T admits a solution if and only if KT ̸|= C0 ⊑ ⊥. Indeed, from a tiling consistent with T one obtains immediately a model of KT with an object satisfying C0. Conversely, from a model I of KT with C I 0 ̸= ∅, we can construct a tiling consistent with T. The first set of assertions impose that a portion of I has exactly the structure depicted in Figure 2 (observe that not the whole model necessarily has a grid structure, but only a portion corresponding to the first quadrant). The second set of assertions impose on such a portion only that instances of concepts representing tile types respect the adjacency conditions. As a consequence of such a reduction we obtain the following result.

Theorem 5 Knowledge base satisfiability (and thus logical implication) in DLRifd extended with unary functional dependencies is undecidable.

The reduction above can be easily modified to show that, if we allow for nominals [Tobies, 2000], then even n-ary functional dependencies lead to undecidability. For example, we may use one nominal o and relations of arity 5 instead of 4. Then we can force the fifth component of all tuples to be the object o by means of the assertion ⊤5 ⊑ (5 : o) and we can enforce the grid structure as above, by adding component 5 to the antecedent of the functional dependencies above (thus getting binary functional dependencies). Observe that, since all tuples agree on component 5, such binary functional dependencies are actually mimicking the unary dependencies in the previous reduction.

7 Conclusions

DLRifd extends DLR by fully capturing identification constraints on concepts and functional dependencies on relations. We have shown that reasoning in the presence of such constraints remains EXPTIME decidable. We have also shown that adding to DLR just unary functional dependencies on non-binary relations, usually considered an indication of bad design in data modeling, leads to undecidability.

The approach presented in this paper can be extended in several ways. For example, our technique can be directly applied to reasoning in DLRreg extended with identification and functional dependency constraints. Moreover, we are working on the following extensions: (i) using chaining in specifying identification constraints, in the spirit of [Borgida and Weddell, 1997]; (ii) introducing a notion of functional dependency between properties of concepts; (iii) query containment and query answering using views in the presence of identification constraints and functional dependencies.