One of the commonly requested features for OWL is some form of key support, generally phrased as allowing inverse-functional datatype properties. For a variety of technical reasons, these were not included in OWL DL (though they were available in OWL Full). OWL 2-a revision to OWL which is under development by the W3C-introduces a form of key representation, so-called “Easy Keys”, which avoids much of the implementational pain of general inverse-functional datatype properties, “dumbs down” nicely to weaker languages (like RDFS), and can be specified (or even implemented) in terms of DL-safe rules. The Easy Key approach also allows for a form of compound key. In this paper we explicate the design and rationale of Easy Keys, sketch a decision procedure for them, and compare them with alternative possibilities, including general inverse-functional datatype properties.
Identification constraints, keys or inverse-functional datatype properties, are all
ways of expressing, by means of a description, that two or more individuals
are necessarily identical. These constraints differ in their expressive power and
their “behavior”, e.g., whether their violation leads to an error, an
inconsistency, or the “quiet” identification of the individuals in question. Regardless of
these details, identification constraints are of vital importance to many
applications. Declaring, for example, the datatype property hasSSN as inverse-functional
would mean that any two individuals sharing the hasSSN same value are inferred
to be identical. For OWL, key reasoning in general can be unfeasibly difficult
[
SubClassOf: hasParent some Person, hasSSN some int[> 41, < 43] 3 Individual: Mary
Types: Person, inv(hasParent) only owl:Nothing 4 Individual: Sheevah – Axiom 1 expresses a strict single-child policy of the country in question. (This might seem a bit artificial, but for the explanations below we need a property that naturally creates long chains and can be inverse-functional.) – Axiom 2 states that the datatype property hasSSN (which stands for “social security number”) is a key for the class Person, and that every person has a parent and an SSN that is an integer between 41 and 43. In particular, each instance of Person sits in an infinite hasParent chain, possibly looping. – Axioms 3 and 4 say that Mary and Sheevah are instances of Person, and Mary is childless—i.e., sits at the beginning of such an infinite chain.
Suppose now that the key constraint in Axiom 2 is interpreted by stating that hasSSN is inverse-functional if restricted to Person: (R1) For all individuals x, y of type Person, if x and y agree on their hasSSN value, then x = y. Under this reading, O has no models: Axiom 3 says that Mary is a Person. According to Axiom 2, she has a parent x who is a Person. Axiom 2 then implies that both have SSN 42. Since SSN is a key for Person, Mary and x coincide. Hence, Mary is her own parent, which contradicts the last part of Axiom 3.
An analogous contradiction would occur if we replaced the range of hasSSN with “int[> 0, < 1, 000, 000]”. Then, in order to show unsatisfiability of O, we would need to create 1, 000, 000 ancestors of Mary’s before we could reason that two of them collapse and that this would induce a cycle in the hasParent chain and therefore contradict Axiom 1.
Hence, if interpreted as a general inverse-functional datatype property, a key
constraint can require very large, yet finite, interpretations and makes reasoning
computationally difficult. We believe that this expressivity is not required by
applications and is too difficult for users to make effective use of. Instead of
tackling the general problem of reasoning with keys in OWL, we propose a
restricted version of keys—EasyKeys—which meets important use cases and is
practical to implement. This is achieved by incorporating DL-safety [
The missing entailment is already problematic, but—even worse—it can be restored by adding a completely unrelated fact, see Section 4.1. Therefore, we need to relax DL-safety and obtain: (R3) For all named individuals x, y of type Person, if x and y agree on their hasSSN-values, then x = y. The omission of the second occurrence of “named” in this condition restricts the models of O to those where Mary and Sheevah coincide. Hence, O is still consistent, but now entails Mary = Sheevah. This reading seems the most natural for O, and we claim that the relaxation of DL-safety does not lead to computational difficulties. We will base EasyKeys’ semantics on reading (R3) and discuss this choice in more detail in Section 4. Since we are designing a feature of OWL 2, we want EasyKeys to fit in with other Semantic Web languages such as the various OWL 2 Profiles1 and even RDF(S) (perhaps extended with Datalog like rules). We started with the following desiderata in mind when designing EasyKeys: (D1) Be useful enough to be worth specifying. (D2) Have a low impact on implementations, at least in common cases. (D3) Be easy to specify clearly and standardize.
In our experience (and in the experience of users we interviewed), applications
merely require that key constraints are checked on explicit data, see (R2) and
(R3). This alone is a big and effective reduction in expressivity since it allows us
to use a variant of DL-safe SWRL rules [
In this paper, we will discuss the intuitions for EasyKeys and their desired properties. We will define a suitable notion of key constraints and explain how to extend standard tableau algorithms to incorporate them. Finally, we will discuss design alternatives for OWL based keys.
Related Work. In the literature, key constraints and, more general,
functional dependencies have been added to description logics of different
expressivity, largely being interpreted according to reading (R1). This was unproblematic
in the absence of datatypes, where complexity of reasoning was hardly affected
[
2 In fact, this result was proven for ALC extended by a very simple datatype D that has an efficiently decidable satisfiability problem.
Keys in general have (or may have) the following properties. (P1) If two individuals x and y have the same key values, then x = y. (P2) Integrity constraint: missing key values raise an error. Individuals which may have a key must have a key. This is easily seen in the case of relational database rows. (P3) Functionality constraint: entities have only one key. This can be interpreted weakly (in any model, a given entity has at most one key) or strictly (each entity has a known key, the same one in every model).
Property (P1) is essential—it states the definition of a key. Property (P2) is
not expressible directly in first-order logic (being non-monotonic), thus in
neither OWL nor OWL plus DL-safe rules. There are proposals for adding
nonmonotonic features to a language like OWL (e.g., [
Property (P3) in its weak sense (in any model, a given entity has at most one key) can be expressed in OWL as a maxCardinality 1 statement, and this also works in the known-individual/value case. However, the strict sense (each entity has a known key, the same one in every model) is not expressible in first-order logic. Of course, while we may impose functionality on keys (at least of a certain type), we do not need to build that into EasyKeys. For example, it is easy to imagine that certain classes of entities may have multiple keys, even of the same sort: email addresses may be keys for people in many datasets and people can have multiple email addresses. We can even more easily imagine that entities may have keys of diverse sorts, e.g., a book may have an ISBN and a Library of Congress catalog number.
Property (P1) can be expressed as a DL-safe rule according to (R2) if we assume the necessary DL-safety restrictions. For example, DL-safe Rule (1) expresses that hasSSN is a key property.
hasSSN(x, k), hasSSN(y, k) → hasSSN(x, k), hasSSN(y, k), Person(x), Person(y) → hasSSN(x, s), age(x, a), hasSSN(y, s), age(y, a) → x = y x = y x = y (1) (2) (3) Key properties can also be restricted to certain classes, e.g., DL-safe Rule (2) expresses that hasSSN is a key property for the class Person. We can also capture compound keys, where several properties together act as a key. For example, we can express that having the same social security number and being the same age (we might reuse the SSN every year/generation) implies being the same individual via DL-safe Rule (3).
Thus, in principle, if OWL 2 had a suitable rule language, then users could directly encode their key constraints as rules. Between the OWLED taskforce on DL-safe SWRL rules3 and the Rule Interchange Format working group4 of the W3C (not to mention the increasing number of DL-safe rule implementations), it is pretty clear that some sort of more or less standard rule extension to OWL 2 will emerge in the next year. However, even if we had in hand a standard, widely deployed rule language, requiring users to use rules to express key constraints is a suboptimal choice for several reasons: 1. Such rules are not intention-revealing: they do not clearly signal that their purpose is to express a key constraint. Having some sort of key-specific constructor would make the intention of the expression clear to users. It would make a similar difference if, say, the source code of a computer program contained case distinctions expressed by switch statements as opposed to nested if statements. It is equally common in natural, programming and formal language to use defined constructs rather than their full definition. If this were not the case, how could we search an ontology (or program) for occurrences of transitivity statements or key constraints (or case distinctions)? 2. Using rules for key constraints requires a fair bit of sophistication and care in their formulation. One must keep track of the variables, their relations, and which sorts of atoms go where. Compare this with the transitivity operator: one could express transitive properties as a (general) SWRL rule, but at the price of having to coin three variables and understand how to set up the rule. Though the latter may seem trivial, it is not: writing out transitivity statements as rules is error-prone and obfuscating. 3. It may be possible, as in the transitivity case, to provide special support in reasoners for keys. This would be, however, more difficult to implement if first one needed to analyze the rule base for “key like” rules.
These considerations led us to conclude that it was worth introducing special syntax for keys with the restricted, DL-safe rule-esque semantics into OWL 2. 3
In this section, we will define key constraints that meet the above intuitions, and explain how to obtain a tableau algorithm that incorporates all features of OWL and key constraints. This will be achieved by combining existing tableau algorithms for SROIQ—the designated OWL 2 description logic—with existing tableau algorithms for DLs with datatypes and key constraints.
We aim at making this theoretical part as accessible to users and
implementors as possible without being imprecise. Therefore we will only introduce those
details that are absolutely necessary, and refer the reader to the literature for
the missing parts. Readers who are primarily interested in modeling issues can
safely skip to Section 4. For a formal introduction into OWL, SROIQ, and DLs
with datatypes see [
3.1
Datatypes in OWL 2 are restrictions of concrete domains [
Decision procedures for description logics with datatypes usually invoke
datatype reasoners. These decide whether a conjunction c of predicates from D over
some set of variables is satisfiable. To ensure the existence of an algorithm for
this satisfiability check, D has to be admissible [
In the presence of key constraints, standard decision procedures use a
variation of this datatype reasoner: in case c is satisfiable, the reasoner chooses a
solution s of c and outputs the set of variables that take on the same values
in s. To ensure the existence of such an algorithm, D has to be key-admissible
[
A key constraint is a statement of the form
C hasKey (p1, . . . , pn, d1, . . . , dm),
(4)
^
i=1,...,n
where p1, . . . , pn are simple object properties, d1, . . . , dm are datatype properties,
and C is a class description. The requirement of pi being simple is necessary in
order to ensure decidability [
∀xy ∃z1 . . . znv1 . . . vm . α → x = y (5) 2. An interpretation I is an e-model of O and (4) if I is a model of O and satisfies the following property, where HU is a predicate holding of all elements of the Herbrand universe, i.e., HU holds of all individuals named in O. ∀xyh∃z1 . . . znv1 . . . vm α ∧ HU(x) ∧ HU(y) ∧ h
HU(zi)i
→ x = yi (6) ^ i=1,...,m
^ Had we included conjuncts HU(vi) for each datatype variable vi, this statement could have been captured by a DL-safe rule and would correspond to reading (R2). Without these additional conjuncts, (6) corresponds to (R3).
We will discuss in Section 4 why we forgo the “missing” portion of DL-safety. We call key constraints with semantics (5) general key constraints and those with semantics (6) EasyKey constraints. The former are a generalization of inversefunctional datatype properties (IFDTPs), whose problematic behavior w.r.t. reasoning they inherit, see Section 4.3. EasyKey constraints, on the contrary, are orthogonal to IFDTPs, and we will see next why the can be viewed as being computationally harmless.
In the following, we distinguish between abstract individuals/variables (instances of classes) and concrete ones (representing datatype values). 3.3
It suffices to restrict our attention to class satisfiability because all other standard
DL reasoning problems can be reduced to this problem [
We will not fully develop the algorithm here because the necessary technical
details would repeat large parts of the algorithms in [
We expect the reader to be familiar with tableau algorithms as in [
Before we show how to reason in the presence of EasyKey constraints, let us
recall reasoning with non-inverse-functional datatype properties from [
∃-rule: if ∃g1, . . . , gn.P ∈ L(x), x is not blocked, and
there are no gi-successors xi with P (x1, . . . , xn) ∈ DC(x) then add a gi-successor of x for each 1 6 i 6 n, for yi the gi-successor of x, add P (y1, . . . , yn) to DC(x), and update ∼ ∀-rule: if ∀g1, . . . , gn.P ∈ L(x), x is not blocked, and
there are gi-successors yi of x with P (y1, . . . , yn) 6∈ DC(x) then add P (y1, . . . , yn) to DC(x), and update ∼
For instance, if the abstract node x contains the label ∃height, weight.>
expressing that the weight of the individual associated with node x is greater
than its height, then the datatype ∃-rule will create weight- and
height-successors y and z and add the constraint y > z to DC(x). When detecting clashes,
DC(x) is tested for satisfiability by a datatype reasoner (DTR), whose negative
answer is a clash for x. (This requires D to be admissible.) It suffices to invoke
the DTR once after all completion rules have been exhaustively applied [
EasyKey constraints, as opposed to inverse-functional datatype properties,
do not impair tableau termination because they only affect named individuals.
The general extension of standard tableau algorithms to key constraints can be
taken from [
As above, datatype constraints are collected and checked for satisfiability. But since key constraints may cause abstract nodes labelled by named individuals to merge, a separate construction and treatment of each DC(x) does not suffice. Instead, for all abstract nodes x labelled with named individuals, all constraints from labels in L(x) have to be put into a global set DC of constraints.
The DTR that runs on DC has to answer more than “yes” if DC is satisfiable. In addition, it has to nondeterministically output conditions under which DC is satisfied, namely an equivalence relation ∼ on the set of variables occurring in DC such that DC∼ ∪ {y 6= z | y 6∼ z} is satisfiable. Here DC∼ denotes DC where each occurrence of a variable y is replaced by some fixed representative of y’s equivalence class. The existence of such a DTR is ensured by the keyadmissibility of D.
After a positive answer of the DTR, abstract nodes are merged according
to ∼. As a consequence, concrete nodes might have to be merged as well—
but they might have incoming edges labelled with datatype properties that are
involved in key constraints. Therefore, DC needs to be updated, and the process
of running the DTR plus merging has to be iterated. Since, in each iterative step,
the “new” relation ∼ is a superset of the “old” one, this procedure terminates.
This is explained in more detail in [
Furthermore, the size of DC is polynomial in the size of the ontology: for each abstract node x labelled with a named individual, x will only contribute as many constraints to DC as it has outgoing edges. The number of the latter is bounded by the sum of the numbers that occur in any number restriction in x’s labels. Hence x contributes at most m · n constraints, where m is the maximal number that occurs in number restrictions in x’s labels, and n is the count of these restrictions. Since m, n, and the number of named individuals are bounded by the size of the ontology, we obtain a cubic upper bound for the size of DC. 4
Why are these keys easy? The reason is the usage of HU in the above definition (6) of the semantics: key constraints only act on abstract individuals explicitly present in our ontology, but not on those abstract individuals whose existence is only implied. And key constraints “act” by inferring new equalities.
In (6), the predicate HU is applied to all abstract variables, but not to concrete ones. This is so because, for the former, it is (a) necessary for decidability (DL-safety), and (b) it is easy to determine for which elements HU holds—but it would be more problematic for datatype values and is not needed for decidability.
For this subtlety in the usage of HU, EasyKeys cannot be captured by
DL-safe rules, according to the definition of the latter in [
The easiest keys would be according to the interpretation (R2) from Section 1. This special case of DL-safe rules would mean to handle the abstract and concrete variables in precisely the same way. One could then preprocess the ontology, looking for explicit concrete values, and treat them as the only substitution candidates for the variables. This case would even simplify the operation of the datatype reasoner DTR (see Section 3.3): for each generated or named abstract individual, only the set DC(x) needs to be evaluated independently, while, for EasyKeys, the datatype constraints for the named abstract individuals are collected in the global set DC and evaluated.
Unfortunately, easiest keys lead to some rather counterintuitive cases. Recall the example ontology O from Figure 1 and the explanation why O does not entail Mary = Sheevah under (R2). Let us now add the following assertion to O: 5 Individual: Demeter
Types: hasAge value 42 This is a completely unrelated fact—it does not say anything about Demeter’s type or hasSSN-value. But since now 42 is explicit in O, O entails Sheevah =
hasKey hasSSN 2 Individual: Mary
Types: Person, hasSSN integer[> 41, < 43] 3 Individual: Sheevah
Types: Person Mary. A similar anomaly can be observed for O0 from Figure 3. This ontology does not entail Sheevah = Mary, but it will if we replace Axiom 2 by 2’. 2’ Individual: Mary
Types: Person, hasSSN value 42 Such anomalies are the primary reason for adopting slightly less easy keys. They cause quite some implementation challenge since large, but finite, enumerations of key values, e.g., integer[> 0, < 1000], can yield nontrivial interactions. 4.2
There is a sense in which EasyKeys’ extra expressivity covers currently somewhat improbable corner cases. However, the consequences of not covering those cases well seem quite negative: intuitively and wildly irrelevant assertions can induce key-based identification. Furthermore, the underspecification of userdefined datatypes in OWL 1 might have been a reason why this sort of case has not emerged. OWL 2 has much more robustly specified datatype support, so we can anticipate that ontology developers will be writing more and more complex data constraints. It is exactly when users go beyond what is easy to understand that helpful semantics with good reasoning support becomes essential.
However, there are two cases where EasyKeys and the easiest keys coincide, namely (1) when data values drawn from finite datatypes are not used as keys (e.g., if the range restriction in Axiom 2 of O in Figure 1 is replaced with “[> 0]”) or (2) when all values of key properties are given explicitly. If the modeler takes care to satisfy at least one of these properties, a much simpler “look and merge” algorithm can be employed. Thus, EasyKeys have good pay-as-you-go behavior, in principle, and we expect that implementations will take advantage of that. The restriction is also fairly easy to understand and syntactically enforce. 4.3
If you restrict yourself to single key properties (i.e., no composite keys), then our EasyKeys yield a subset of the entailments you can get with inverse-functional datatype properties (IFDTPs). There are two main problems with IFDTPs: 1. While decidable, they are very hard to reason with. In fact, we are not aware of any implementations or any implementor who relishes the challenge. We have discussed in Section 3.3 that, without IFDTPs, datatype reasoning can be confined to a single individual (asserted or generated) at a time. That is, you gather all the data constraints applicable to the individual x and pass them to the datatype reasoner DTR. If the DTR finds them consistent and x is generated, you mark x as checked and can (largely) forget about it. With IFDTPs, you lose this locality—all (named and generated) individuals with datatype properties may need to be checked at any time. Since, in OWL, not all of the potential key values may be explicit, this involves maintaining a large constraint system DC that is constantly updated. Because generated individuals have to be checked as well, termination of the algorithm will be difficult to guarantee. 2. It is not clear that modelers would know what to do with such a powerful feature, or even if they would want such power in most cases. Clearly, they want keys, but it is not at all clear that they want IFDTPs.
So, in essence, we would have a lot of implementation work (and research!) for a not obvious gain. It is much easier to deliver robust, reasonably scalable support for EasyKeys which, for most users, is a dominating consideration.
What do we miss with EasyKeys? Basically, we miss the ability to entail subsumptions through key constraints (at least, directly through key constraints; if we have nominals, for example, we can force subsumptions in specific cases). This is essentially the difference between full SWRL rules and DL-safe SWRL rules. The major use case we could think of for this is aligning database schemas. If you could reduce database schemas to OWL classes (including the key constraints as IFDTPs), then your reasoner could show whether the two schemas were equivalent or disjoint. If one had keys that were integers over 1000, and the other had keys that were integers from 100 to 9999, we would get an inconsistency.
To our minds, this is a very specialized application which, in fact, has never occurred. If it does, one can always appeal to IFDTPs in OWL Full as an extension. Indeed, one nice feature of EasyKeys is that they do not interfere with general IFDTP support: on the one hand, they can be seen as a special case, on the other, they can live side by side in an ontology just as DL-safe rules may live side by side with corresponding transitivity axioms. 5
In this paper we have presented a design for helpful, yet principled, key support for OWL like languages. Our basic proposal has been accepted by the OWL WG as part of the forthcoming OWL 2, and we expect it shall make it into the next public working drafts. We have also discussed, in some detail, various considerations that went into the design of EasyKeys and the tradeoffs we made from the implementational and modeling perspectives. We have also presented a direct algorithm for EasyKeys plus some indications on how optimized implementations may be built. Our investigation into EasyKeys has also led us to a new account of data property atom support in DL-safe rules.
For future work, we plan to finish our running implementation of EasyKeys and to study, more precisely, the pay-as-you-go behavior, particularly as one scales up the data. We also plan to study their use in applications to determine whether we in fact made the right tradeoffs.