We introduce DLR , an extension of the n-ary propositionally closed description logic DLR to deal with attribute-labelled tuples (generalising the positional notation), projections of relations, and global and local objectification of relations, able to express inclusion, functional, key, and external uniqueness dependencies. The logic is equipped with both TBox and ABox axioms forming a DLR knowledge base (KB). We show how a simple syntactic restriction on the appearance of projections sharing common attributes in the KB makes reasoning in the language decidable with the same computational complexity as DLR. The obtained DLR n-ary description logic is able to encode more thoroughly conceptual data models such as EER, UML, and ORM.
We introduce the new description logic (DL) DLR extending the n-ary DL DLR [Calvanese et al., 2008], in order to capture more database oriented constraints. While DLR is an expressive logic, it lacks a number of expressive means that can be added without increasing the complexity of reasoning—when used in a carefully controlled way. The added expressivity is motivated by the increasingly use of DLs as an abstract conceptual layer over relational databases, both to reason over such conceptual models during the database design phase, and to answer ontology-mediated queries over databases.
A DLR TBox can express axioms involving (i) propositional combinations of concepts and (compatible) n-ary relations, (ii) concepts as unary projections of n-ary relations, and (iii) relations with a component selected to be of a certain type. For example, if Pilot and RacingCar are concepts and DrivesCar, DrivesMotobike, DrivesVehicle are binary relations, we can write the following axioms: DLR
extends DLR in the following way.
– While DLR instances of n-ary relations are n-tuples of objects—whose
components are identified by their position in the tuple—instances of relations in DLR
are attribute-labelled tuples, i.e., tuples where each component is identified by an
attribute and not by its position in the tuple
Employeepfirstname; lastname; dept; deptAddrq ; and an instance of Employee could be the tuple:
xfirstname : John; lastname : Doe; dept : Purchase; deptAddr : Londony : – Attributes can be renamed, also with the goal to recover the positional perspectives on relations: firstname; lastname; dept; deptAddr Õ 1; 2; 3; 4 : – Relation projections allow to form new relations by projecting a given relation on some of its attributes. For example, if Person is a relation with signature Person pname; surnameq, it could be related to Employee as follows:
Drfirstname; lastnamesEmployee Person firstname; lastname Õ name; surname : – The objectification of a relation (also known as reification) is a concept whose instances are unique identifiers of the tuples instantiating the relation. Those identifiers could be unique only within an objectified relation (local objectification), or they could be uniquely identifying tuples independently on the relation they are instance of (global objectification). For example, the concept EmployeeC could be the global objectification of the relation Employee, assuming that there is a global one-to-one correspondence between pairs of values of the attributes firstname, lastname and EmployeeC instances:
EmployeeC Å Drfirstname; lastnamesEmployee : As an example of local objectification, let us consider the two (ternary) relations OwnsCar pname; surname; carq and DrivesCar pname; surname; carq, and assume that anybody driving a car also owns it; that is, DrivesCar OwnsCar. The locally objectified events of driving a car and owning a car, defined by the axioms CarDrivingEvent Ä DrivesCar and CarOwningEvent Ä OwnsCar, model the fact that a driving event by a person of a car is not necessarily the owning event by the same person and the same car. Indeed, they should be disjoint: CarDrivingEvent [ CarOwningEvent K should hold.
It turns out that DLR is an expressive description logic able to assert relevant constraints in the context of relational databases. In Section 3 we consider inclusion dependencies, functional and key dependencies, external uniqueness and identification axioms. For example, DLR can express the fact that the attributes firstname, lastname play the role of a multi-attribute key for the relation Employee:
Drfirstname; lastnamesEmployeeD¤1rfirstname; lastnamesEmployee ; and that the attribute deptAddr functionally depends on the attribute dept within the relation Employee:
DrdeptsEmployee D¤1rdepts pDrdept; deptAddrsEmployeeq :
While DLR turns out to be undecidable, in this paper we show how a simple syntactic condition on the appearance of projections sharing common attributes in the knowledge base makes the language decidable. The result of this restriction is a new language called DLR . We prove that DLR , while preserving most of the DLR expressivity, has a reasoning problem whose complexity does not increase w.r.t. the computational complexity of the basic DLR language. We also present in Section 5 the implementation of an API for the reasoning services in DLR . 2
A DLR signature is a tuple L pC; R; O; U ; q where C, R, O and U are finite, mutually disjoint sets of concept names, relation names, individual names, and attributes, respectively, and is a relation signature function, associating a set of attributes to each relation name pRN q tU1; : : : ; Unu U with n ¥ 2.
The syntax of concepts C, relations R, formulas ', and attribute renaming axioms # is given in Figure 1, where CN P C, RN P R, U P U , o P O, q is a positive integer and 2 ¤ k ARITYpRq. The arity of a relation R is the number of the attributes in its signature; i.e., ARITYpRq | pRq|, where we extend the signature function to arbitrary relations C Ñ R Ñ ' Ñ # Ñ
J | K | CN | C | C1 [ C2 | C1 \ C2 | D¼qrUisR | Å R | Ä RN RN | R1zR2 | R1 [ R2 | R1 \ R2 | Ui:C R | D¼qrU1; : : : ; UksR C1 C2 | R1 R2 | CN poq | RN pU1:o1; : : : ; Un:onq | o1 o2 | o1 o2 U1 Õ U2 as specified in Figure 2. Notice that, while global objectification (Å R) can be applied to arbitrary relations, local ones (Ä RN ) can be applied just to relation names. We use the shortcut DrU1; : : : ; UksR for D¥1rU1; : : : ; UksR for k ¥ 1.
A DLR TBox T is a finite set of concept inclusion axioms of the form C1 C2 and relation inclusion axioms of the form R1 R2. We use X1 X2 as a shortcut for X1 X2 and X2 X1. A DLR ABox A is a finite set of concept instance axioms of the form CN poq, relation instance axioms of the form RN pU1:o1; : : : ; Un:onq, and same/distinct individual axioms of the form o1 o2 and o1 o2, with oi P O. Restricting ABox axioms to concept and relation names only does not affect the expressivity of DLR due to the availability of TBox axioms.
A set of renaming axioms forms a renaming schema, inducing an equivalence relation pÕ; U q over the attributes U , providing a partition of U into equivalence classes each one representing alternative ways to name attributes. We write rU s< to denote the equivalence class of the attribute U w.r.t. the equivalence relation pÕ; U q. We allow only well founded renaming schemas, i.e., there is no equivalence class containing two attributes from the same relation signature. We use the shortcut U1 : : : Un Õ U11 : : : U n1 to group many renaming axioms with the meaning that Ui Õ Ui1 for all i 1; : : : ; n.
The renaming schema reconciles the named attribute and the positional perspectives on relations. They are crucial when expressing both inclusion axioms and set operators ([; \; z) between relations, which make sense only over union compatible relations. Two relations R1; R2 are union compatible if their signatures are equal up to the attribute renaming induced by the renaming schema <; that is, pR1q tU1; : : : ; Unu and pR2q tV1; : : : ; Vnu have the same arity n and rUis< rVis< for each 1 ¤ i ¤ n. Notice that through the renaming schema relations can use just local attribute names that can then be renamed when composing relations. Also note that it is obviously possible for the same attribute to appear in the signature of different relations.
A DLR knowledge base (KB) KB pT ; A; <q is composed by a TBox T , an ABox A, and a renaming schema <.
Example 1. Consider the relation names R1; R2 where pR1q tW1; W2; W3; W4u, pR2q tV1; V2; V3; V4; V5u, and the renaming axiom W1W2W3 Õ V3V4V5. The TBox Texa consists of the axioms:
DrW1; W2sR1 D¤1rW1; W2sR1
DrV3; V4sR2 D¤1rV3; V4spDrV3; V4; V5sR2q (1) Intuitively, the axiom (1) expresses that W1; W2 form a multi-attribute key for R1; (2) introduces a functional dependency in the relation R2 where the attribute V5 is functionally dependent from attributes V3; V4, and (3) states an inclusion between two projections of the relation names R1; R2 based on the renaming schema axiom.
The semantics of DLR is based on labelled tuples over a domain : a U -labelled tuple over (or tuple for short) is a function t : U Ñ . For U P U , we write trU s to refer to the domain element d P labelled by U , if the function t is defined for U — that is, if the attribute U is a label of the tuple t. Given d1; : : : ; dn P , the expression xU1 : d1; : : : ; Un : dny stands for the tuple t such that trUis di, for 1 ¤ 1 ¤ n. The projection of the tuple t over the attributes U1; : : : ; Uk (i.e., the function t restricted to be undefined for the labels not in U1; : : : ; Uk) is denoted by trU1; : : : ; Uks. The relation signature function can be applied also to labelled tuples to obtain the set of labels on which the tuple is defined. T pU q denotes the set of all U -labelled tuples over .
A DLR interpretation is a tuple I p ; I ; ; {; Lq consisting of a nonempty domain , an interpretation function I , a renaming function , a global objectification function {, and a family L containing one local objectification function `RNi for each named relation RNi P R.
The renaming function is a total function : U Ñ U representing a canonical renaming for all attributes. We use ptU1; : : : ; Ukuq to denote t pU1q; : : : ; pUkqu. The global objectification function is an injective function, { : T pU q Ñ , associating a unique global identifier to each tuple. The local objectification functions, `RNi : T pU q Ñ , are associated to each relation name in the signature, and as the global objectification function they are injective: they associate an identifier—which is guaranteed to be unique only within the interpretation of a relation name—to each tuple. The interpretation function I assigns a domain element to each individual oI P , a set of domain elements to each concept name CN I , and a set of U -labelled tuples over to each relation name conforming with its signature and to the renaming function RN I T pt pU q | U P pRN quq. Note that the unique name assumption is not enforced. The interpretation function I is unambiguously extended over concept and relation expressions as specified in Figure 3.
The interpretation I satisfies the concept inclusion axiom C1 C2 if C1I C2I , and the relation inclusion axiom R1 R2 if R1I R2I . It satisfies the concept instance axiom CN poq if oI P CN I, the relation instance axiom RN pU1:o1; : : : ; Un:onq if x pU1q : o1I ; : : : ; pUnq : oIny P RN I , and the axioms o1 o2 and o1 o2 if o1I o2I , and o1I o2I , respectively. I satisfies a renaming schema < if for every U; V P U , (i) pU q P rU s<, and (ii) if V P rU s<, then pU q pV q. I is a model of the KB pT ; A; <q if it satisfies the axioms in the TBox T , in the ABox A, and the renaming schema <.
KB satisfiability refers to the problem of deciding the existence of a model of a given KB; concept satisfiability (resp. relation satisfiability) is the problem of deciding whether there is a model of the KB with a non-empty interpretation of a given concept (resp. relation). A KB entails (or logically implies) an axiom if all models of the KB are also models of the axiom. For instance, the TBox in Example 1 entails that axiom (2) is redundant since V3; V4 are a key for R2: Texa |ù DrV3; V4sR2 D¤1rV3; V4sR2 : 3
DLR is an expressive description logic able to assert relevant constraints in the context of relational databases, such as inclusion dependencies (inclusion axioms among arbitrary projections of relations), equijoins, functional dependency axioms, key axioms, external uniqueness axioms, identification axioms, and path functional dependencies.
An equijoin among two relations with disjoint signatures is the set of all combinations of tuples in the relations that are equal on their selected attribute names. Let R1; R2 be relations with pR1q tU; U1; : : : ; Un1 u and pR2q tV; V1; : : : ; Vn2 u; their equijoin over U and V is the relation R R1 ' R2 that uses the signature U V pRq pR1q Y pR2qztV u, and is expressed by the DLR axioms:
DrU; U1; : : : ; Un1 sR U:pDrUsR1[DrV sR2qR1 DrV; V1; : : : ; Vn2 sR V :pDrUsR1[DrV sR2qR2
U Õ V :
A functional dependency axiom pR : U1 : : : Uj Ñ U q
Uh 1 Uh R : U11; : : : ; Un11 ; : : : ; U1h; : : : ; Unhh Ñ U 1
DrU1; : : : ; Uj sR D¤1rU1; : : : ; Uj spDrU1; : : : ; Uj ; U sRq: A special case of functional dependencies are key axioms pR : U1 : : : Uj Ñ Rq, which state that the values of the key attributes U1 : : : Uj of a relation R uniquely identify tuples in R. A key axiom can be expressed in DLR , assuming that tU1 : : : Uj u pRq, with the axiom:
DrU1; : : : ; Uj sR D¤1rU1; : : : ; Uj sR : The external uniqueness axiom prU 1sR1 Ó : : : Ó rU hsRhq states that the join R of the relations R1; : : : ; Rh via the attributes U 1; : : : ; U h has the joined attribute functionally dependent on all the others [Halpin and Morgan, 2008]. This can be expressed in DLR with the axioms:
R '
R1U1 U2 where pRiq
tU i; U1i; : : : ; Uni i u; 1 ¤ i ¤ h, and R a new relation name with signature pRq tU 1; U11; : : : ; Un11 ; : : : ; U1h; : : : ; Unhh u.
Identification axioms as defined in DLRifd [Calvanese et al., 2001] (an extension of DLR with functional dependencies and identification axioms) are a variant of external uniqueness axioms, constraining only the elements of a concept C; they can be expressed in DLR with the axiom:
rU 1s U1:C R1 Ó : : : Ó rU hs Uh:C Rh : Path functional dependencies—as defined in the DL family CF D [Toman and Weddell, 2009]—can be expressed in DLR as identification axioms involving joined sequences of functional binary relations. DLR also captures tree-based identification constraint (tid) introduced in [Calvanese et al., 2014] to capture fds in DL-LiteRDFS,tid.
The rich set of constructors in DLR allows us to extend the known mappings in description logics of popular conceptual data models. The EER mapping as introduced in [Artale et al., 2007] can be extended to deal with multi-attribute keys (by using identification axioms) and named roles in relations; the ORM mapping as introduced in [Franconi et al., 2012; Sportelli and Franconi, 2016] can be extended to deal with arbitrary subset and exclusive relation constructs (by using inclusions among global objectifications of projections of relations), arbitrary internal and external uniqueness constraints, arbitrary frequency constraints (by using projections), local objectification, named roles in relations, and fact type readings (by using renaming axioms); the UML mapping as introduced in [Berardi et al., 2005] can be fixed to deal properly with association classes (by using local objectification) and named roles in associations. 4
The DLR
fragment of DLR Since a DLR KB can express inclusions and functional dependencies, the reasoning is undecidable [Chandra and Vardi, 1985]. In this section we present DLR , a decidable syntactic fragment of DLR limiting the co-occurence of relation projections in a KB.
Given a DLR knowledge base pT ; A; <q, the projection signature is the set T containing the signatures pRN q of the relations RN P R, the singleton sets associated with each attribute name U P U , and the relation signatures that appear explicitly in projection constructs in some axiom from T , together with their implicit occurrences due to the renaming schema. Formally, T is the smallest set where (i) pRN qPT for all RN P R; (ii) tU u P T for all U P U ; and (iii) tU1; : : : ; Uku P T for all D¼qrV1; : : : ; VksR appearing as sub-formulas in T and tUi; Viu rUis< for 1¤i¤k.
The projection signature graph is the directed acyclic graph p; T q whose sinks are the attribute singletons tU u. Given a set of attributes tU1; : : : ; Uku U , the projection signature graph dominated by , denoted as T , is the sub-graph of p; T q containing all the nodes reachable from . Given two sets of attributes 1; 2 U , PATHT p 1; 2q denotes the set of paths in p; T q between 1 and 2. Notice that
H both when a path does not exist and when 1 2. The notation PATHT p 1; 2q CHILDT p 1; 2q means that 2 is a child of 1 in p; T q. We now introduce DLR . Definition 1. A DLR knowledge base is a DLR following syntactic conditions: knowledge base that satisfies the 1. the projection signature graph p; T q is a multitree: i.e., for every node P T , the graph T is a tree; and 2. for every projection construct D¼qrU1; : : : ; UksR appearing in T , if q ¡ 1 then the length of the path PATHT p pRq; tU1; : : : ; Ukuq is 1.
tV1; V2; V3; V4; V5u tW4u " W1 *
V3 " W1; W2; W3 *
V3; V4; V5 " W1; W2 *
V3; V4 " W2 *
V4 tV1u " W3 *
V5
tV2u
The conditions in DLR restrict DLR in the way that multiple projections of relations may appear in a KB: intuitively, there can not be projections of a relation sharing a common attribute. Moreover, observe that in DLR PATHT is necessarily functional, due to the multitree restriction. Figure 4 shows that the projection signature graph of the knowledge base from Example 1 is indeed a multitree. Note that in the figure we have collapsed equivalent attributes in a unique equivalence class, according to the renaming schema. Furthermore, since all its projection constructs have q 1, this knowledge base belongs to DLR .
DLR is included in DLR , since the projection signature graph of any DLR
knowledge base is always a degenerate multitree with maximum depth equal to 1.
Not all the database constraints as introduced in Section 3 can be directly expressed
in DLR . While functional dependency and key axioms can be expressed directly
in DLR , equijoins, external uniqueness axioms, and identification axioms introduce
projections of a relation which share common attributes, thus violating the multitree
restriction. However, in DLR it is still possible to reason over both external
uniqueness and identification axioms by encoding them into a set of saturated ABoxes
The main result of this work is that reasoning in DLR is an EXPTIME-complete problem. The lower bound comes by observing that DLR is a sublanguage of DLR , the upper bound is proved by providing a mapping from DLR KBs to ALCQI KBs. 5
We have implemented the framework discussed in this paper. DLRtoOWL is a Java library fully implementing DLR reasoning services. The library is based on the tool ANTLR4 to parse serialised input, and on OWLAPI4 for the OWL2 encoding. The system includes JFact, the Java version of the popular Fact++ reasoner. DLRtoOWL provides a Java DLR API package to allow developers to create, manipulate, serialise, and reason with DLR knowledge bases in their Java-based application, extending in a compatible way the standard OWL API with the DLR TELL and ASK services. During the development of this new library we strongly focused on performance. Since the OWL encoding is only possible if we have already built the ALCQI projection signature multitree, in principle the program should perform two parsing rounds: one to create the multitree and the other one to generate the OWL mapping. We faced this issue using dynamic programming: during the first (and only) parsing round we store in a data structure each axiom that we want to translate in OWL and, after building the multitree, by the dynamic programming technique we build on-the-fly a Java class which generates the required axioms.