We introduce an extension of the n-ary description logic DLR to deal with attribute-labelled tuples (generalising the positional notation), with arbitrary projections of relations (inclusion dependencies), generic functional dependencies and with global and local objectification (reifying relations or their projections). We show how a simple syntactic condition on the appearance of projections and functional dependencies in a knowledge base makes the language decidable without increasing the computational complexity of the basic DLR language.
We introduce in this paper the language DLR which extends the n-ary description logics DLR [Calvanese et al., 1998; Baader et al., 2003] and DLRifd [Calvanese et al., 2001] as follows: – the semantics is based on attribute-labelled tuples: an element of a tuple is identified by an attribute and not by its position in the tuple, e.g., the relation Person has attributes firstname, lastname, age, height with instance: x firstname: Enrico, lastname: Franconi, age: 53, height: 1.90y; – renaming of attributes is possible, e.g., to recover the positional semantics: firstname,lastname,age,height í 1,2,3,4; – it can express projections of relations, and therefore inclusion dependencies, e.g.,
Drfirstname,lastnamesStudent Drfirstname,lastnamesPerson; – it can express multiple-attribute cardinalities, and therefore functional dependencies and multiple-attribute keys, e.g., the functional dependency from firstname, lastname to age in Person can be written as: Drfirstname,lastnamesPerson
D¤1rfirstname,lastnamespDrfirstname,lastname,agesPersonq; – it can express global and local objectification (also known as reification): a tuple may be identified by a unique global identifier, or by an identifier which is unique only within the interpretation of a relation, e.g., to identify the name of a person we can write Name Ä Drfirstname,lastnamesPerson.
We show how a simple syntactic condition on the appearance of projections in the knowledge base makes the language decidable without increasing the computational C Ñ R Ñ ' Ñ # Ñ
J | K | CN | RN | R1zR2 | R1 [ R2 | R1 \ R2 | Ui:C R | D¼qrU1; : : : ; UksR
C | C1 [ C2 | C1 \ C2 | D¼qrUisR | Å R | Ä RN C1 C2 | R1 R2 U1 í U2 complexity of the basic DLR language. We call DLR this fragment of DLR . DLR is able to correctly express the UML fragment as introduced in [Berardi et al., 2005; Artale et al., 2007] and the ORM fragment as introduced in [Franconi and Mosca, 2013]. 2
Syntax of the Description Logic DLR We first define the syntax of the language DLR . A signature in DLR is a triple L pC; R; U ; q consisting of a finite set C of concept names (denoted by CN ), a finite set R of relation names (denoted by RN ) disjoint from C, and a finite set U of attributes (denoted by U ), and 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 defined in Figure 1, where q is a positive integer and 2 ¤ k ARITYpRq. We extend the signature function to arbitrary relations as specified in Figure 2. We define the ARITY of a relation R as the number of the attributes in its signature, namely | pRq|.
A DLR TBox T is a finite set of formulas, i.e., concept inclusion axioms of the form C1 C2 and relation inclusion axioms of the form R1 R2.
A renaming schema induces an equivalence relation pí; U q over the attributes U , providing a partition of U into equivalence classes each one representing the 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, namely schemas such that each equivalence class rU s< in the induced equivalence relation never contains two attributes from the same relation signature. In the following we use the shortcut U1 : : : Un í U11 : : : U n1 to group many renaming axioms, with the obvious meaning that Ui í Ui1, for all i 1; : : : ; n.
A DLR knowledge base KB pT ; <q is composed by a TBox T and a renaming schema <.
The renaming schema reconciles the attribute and the positional perspectives on
relations
To show the expressive power of the language, let us consider the following example with tree relation names R1; R2 and R3 with the following signature: To state that tU1; U2u is the multi-attribute key of R1 we add the axiom:
DrU1; U2sR1 D¤1rU1; U2sR1 where DrU1; : : : ; UksR stands for D¥1rU1; : : : ; UksR. To express that there is a functional dependency from the attributes tV3; V4u to the attribute tV5u of R2 we add the axiom:
DrV3; V4sR2 D¤1rV3; V4spDrV3; V4; V5sR2q (1) The following axioms express that R2 is a sub-relation of R1 and that a projection of R3 is a sub-relation of a projection of R1, together with the corresponding axioms for the renaming schema to explicitly specify the correspondences between the attributes of the two inclusion dependencies:
R2 R1 DrW1; W2; W3sR3 DrU3; U4; U5sR1
V1V2V3V4V5 í U1U2U3U4U5
W1W2W3 í U3U4U5 3
The semantics makes use of the notion of labelled tuples over a domain set : a U labelled tuple over 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 JI
KI p CqI pC1 [ C2qI pC1 \ C2qI pD¼qrUisRqI
pÅ RqI pÄ RN qI pR1zR2qI pR1 [ R2qI pR1 \ R2qI p Ui:C RqI pD¼qrU1; : : : ; UksRqI
H JI zCI C1I X C2I C1I Y C2I td P td P td P | tt P RI | tr pUiqs | d {ptq ^ t P RI u | d `RN ptq ^ t P RN I u
du ¼ qu R1I zR2I R1I X R2I tt P R1I Y R2I | p pR1qq p pR2qqu tt P RI | tr pUiqs P CI u tx pU1q : d1; : : : ; pUkq : dky P T pt pU1q; : : : ; pUkquq | tt P RI | tr pU1qs d1; : : : ; tr pUkqs dku ¼ qu xU1 : d1; : : : ; Un : dny stands for the U -labelled tuple t over (tuple, for short) such that trUis di, for 1 ¤ 1 ¤ n. We write trU1; : : : ; Uks to denote the projection of the tuple t over the attributes U1; : : : ; Uk, namely the function t restricted to be undefined for the labels not in U1; : : : ; Uk. The set of all U -labelled tuples over is denoted by T pU q.
A DLR interpretation, I p ; I ; ; {; `RN1 ; `RN2 ; : : :q, consists of a nonempty domain , an interpretation function I , a renaming function , a global objectification function {, and a family of local objectification functions `RNi , one for each named relation RNi P R.
The renaming function for attributes is a total function : U Ñ U representing a canonical renaming for all attributes. We consider, as a shortcut, the notation ptU1; : : : ; Ukuq t pU1q; : : : ; pUkqu.
The global objectification function is an injective function, { : T pU q Ñ , associating a unique global identifier to each possible tuple.
The local objectification functions, `RNi : T pU q Ñ , are distinct for each relation name in the signature, and as the global objectification function they are injective: they associate an identifier – which is unique only within the interpretation of a relation name – to each possible tuple.
The interpretation function I assigns 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 the renaming function:
RN I T pt pU q | U P pRN quq:
The interpretation function I is unambiguously extended over concept and relation expressions as specified in the inductive definition of Fig. 3.
An interpretation I satisfies a concept inclusion axiom C1 C2 if C1I C2I , it satisfies a relation inclusion axiom R1 R2 if R1I R2I , and it satisfies a renaming schema < if the renaming function renames the attributes in a consistent way with respect to <, namely if pV q:
An interpretation is a model for a knowledge base pT ; <q if it satisfies all the formulas in the TBox T and it satisfies the renaming schema <. We define KB satisfiability as the problem of deciding the existence of a model of a given knowledge base, concept satisfiability (resp. relation satisfiability) as the problem of deciding whether there is a model of the knowledge base that assigns a non-empty extension to a given concept (resp. relation), and entailment as the problem to check whether a given knowledge base logically implies a formula, that is, whenever all the models of the knowledge base are also models of the formula.
For example, from the knowledge base KB introduced in the previous Section the following logical implication holds:
KB |ù DrV1; V2sR2 D¤1rV1; V2sR2 i.e., the attributes V1; V2 are a key for the relation R2.
Proposition 1. The problems of KB satisfiability, concept and relation satisfiability, and entailment are mutually reducible in DLR .
DLR can express complex inclusion and functional dependencies, for which it is well known that reasoning is undecidable [Mitchell, 1983; Chandra and Vardi, 1985]. DLR also includes the DLR extension DLRifd together with unary functional dependencies [Calvanese et al., 2001], which also has been proved to be undecidable. 4
The DLR
fragment of DLR Given a DLR knowledge base pT ; <q, we define the projection signature as the set T including the signatures pRN q of the relations RN P R, the singletons associated with each attribute name U P U , and the relation signatures as they appear explicitly in projection constructs in the relation inclusion axioms of the knowledge base, together with their implicit occurrences due to the renaming schema: 3. tU1; : : : ; Uku P T if D¼qrV1; : : : ; VksR P T and tUi; Viu rUis< for 1 ¤ i ¤ k.
We call projection signature graph the directed acyclic graph p; T q with the attribute singletons tU u being the sinks. The DLR fragment of DLR allows only for knowledge bases with a projection signature graph being a multitree, namely the set of nodes reachable from any node of the projection signature graph should form a tree.
U1( V1
UV11; UV22(
U2( V2 ! UV33 )
W1 ! U3
V3 ; UV44 ; UV55 ) W1 W2 W3 ! U3
V3 ; UV44 ) W1 W2 ! UV55 )
W3 ! UV44 )
W2 tW4u
Given a relation name RN , the subgraph of the projection signature graph dominated by RN is a tree where the leaves are all the attributes in pRN q and the root is pRN q. We call TtU1;:::;Uku the tree formed by the nodes in the projection signature graph dominated by the set of attributes tU1; : : : ; Uku. Given two relation signatures (i.e., two sets of attributes) 1; 2 U , by PATHT p 1; 2q we denote the path in p; T q between 1 and 2, if it exists. Note that PATHT p 1; 2q H both when a path does not exist and when 1 2, and PATHT is functional in DLR due to the multitree restriction on projection signatures. The notation CHILDT p 1; 2q means that 2 is a child of 1 in p; T q.
In addition to the above multitree condition, the DLR fragment of DLR allows for knowledge bases with projection constructs D¼qrU1; : : : ; UksR (resp. D¼qrU sR) with a cardinality q ¡ 1 only if the length of the path PATHT ptU1; : : : ; Uku; pRqq (resp. PATHT ptU u; pRqq) is 1. This allows to map cardinalities in DLR into cardinalities in ALCQI.
Figure 4 shows that the projection signature graph of the knowledge base introduced in Section 2 is indeed a multitree. Note that in the figure we have collapsed equivalent attributes in a unique equivalence class, according to the renaming schema.
DLR restricts DLR only in the way multiple projections of relations appear in the knowledge base. It is easy to see that DLR is included in DLR , since the projection signature graph of any DLR knowledge base has maximum depth equal to 1. DLRifd [Calvanese et al., 2001] together with (unary) functional dependencies is also included in DLR , with the proviso that projections of relations in the knowledge base form a multitree projection signature graph. Since (unary) functional dependencies are expressed via the inclusions of projections of relations (see, e.g., the functional dependency (1) in the previous example), by constraining the projection signature graph to be a multitree, the possibility to build combinations of functional dependencies as the ones in [Calvanese et al., 2001] leading to undecidability is ruled out. Also note that DLR is able to correctly express the UML fragment as introduced in [Berardi et al., 2005; Artale et al., 2007] and the ORM fragment as introduced in [Franconi and Mosca, 2013]. QtU1;U2u
QtU3;U4;U5u QtU3;U4;U5u QtW4u AtRU11;U2u; AtRU21;U2u AtRU13;U4;U5u; AtRU23;U4;U5u; AtRU33;U4;U5u
QtU1u QtU2u QtU3;U4u QtU5u
QtU3u QtU4u
We show that reasoning in DLR is EXPTIME-complete by providing a mapping from DLR knowledge bases to ALCQI knowledge bases; the reverse mapping from ALCQI knowledge bases to DLR knowledge bases is well known. The proof is based on the fact that reasoning with ALCQI knowledge bases is EXPTIME-complete [Baader et al., 2003]. We adapt and extend the mapping presented for DLR in [Calvanese et al., 1998].
In the following we use the shortcut pS1 : : : Snq for Sn : : : S1 , the shortcut D¼1S1 : : : Sn. C for D¼1S1. : : : . D¼1Sn. C and the shortcut @S1 : : : Sn. C for @S1. : : : . @Sn. C. Note that these shortcuts for the role chain constructor “ ” are not correct in general, but they are correct in the context of the specific ALCQI knowledge bases used in this paper.
Let KB pT ; <q be a DLR knowledge base. We first rewrite the knowledge base as follows: for each equivalence class rU s< a single canonical representative of the class is chosen, and the KB is consistently rewritten by substituting each attribute with its canonical representative. After this rewriting, the renaming schema does not play any role in the mapping.
The mapping function : maps each concept name CN in the DLR knowledge base to an ALCQI concept name CN , each relation name RN in the DLR knowledge base to an ALCQI concept name ARN (its global reification), and each attribute name U in the DLR knowledge base to an ALCQI role name, as detailed below. l For each relation name RN the mapping introduces a concept name ARN and a role name QRN (to capture the local reification), and a concept name ARiN for each projected signature i in the projection signature graph dominated by pRN q, i P T pRNq (to capture global reifications of the projections of RN ). Note that ARpNRNq coincides with ARN . Furthermore, the mapping introduces a role name Q i for each projected signature i in the projection signature, i P T , such that there exists j P T with CHILDT p j ; iq, i.e., we exclude the case where i is one of the roots of the multitree induced by the projection signature. C1: [ C:
2 C1: \ C:
2 D¼q PATHT p pRq; tUiuq: R:
l ARN R1: [ R1: [ R2: R1: \ R2:
R2:
. R: p Ui:C Rq: pD¼qrU1; : : : ; UksRq:
R: [ @PATHT p pRq; tUiuq:. C: D¼q PATHT p pRq; tU1; : : : ; Ukuq: . R:
The mapping : applies also to a path. Let ; 1 P T be two generic sets of attributes such that the function PATHT p ; 1q ; 1; : : : ; n; 1, then, a path is mapped as follows:
PATHT p ; 1q:
Q 1 : : : Q n
Q 1 :
Intuitively, the mapping reifies each node in the projection signature graph: the target ALCQI signature of the example of the previous section is partially presented in Fig. 5, together with the projection signature graph. Each node is labelled with the corresponding (global) reification concept (ARji ), for each relation name Ri and each projected signature j in the projection signature graph dominated by pRiq, while the edges are labelled by the roles (Q i ) needed for the reification.
The mapping : is extended to concept and relation expressions as in Figure 6, with the proviso that whenever PATHT p 1; 2q returns an empty path then the translation for the corresponding expression becomes the bottom concept. Note that in DLR the cardinalities on a path are restricted to the case q 1 whenever a path is of length greater than 1, so we still remain within the ALCQI description logic when the mapping applies to cardinalities. So, if we need to express a cardinality constraint D¼qrUisR,] with q ¡ 1, then Ui should not be mentioned in any other projection of the relation R in such a way that |PATHT p pRq; tUiuq| 1.
In order to explain the need for the path function in the mapping, notice that a relation is reified according to the decomposition dictated by projection signature graph it dominates. Thus, to access an attribute Uj of a relation Ri it is necessary to follow the path through the projections that use that attribute. This path is a role chain from the signature of the relation (the root) to the attribute as returned by the PATHT p pRiq; Uiq function. For example, considering Fig. 5, in order to access the attribute U4 of the relation R3 in the expression p U4:C R3q, the path PATHT p pR3q; tU4uq: is equal to the role chain QtU3;U4;U5u QtU3;U4u QtU4u, so that p U4:C R3q: QtU3;U4u QtU4u. C: AR3 [@QtU3;U4;U5u where relpRN q lobjpRN q Similar considerations can be done when mapping cardinalities over relation projections.
The mapping pKBq of a DLR knowledge base KB with a signature pC; R; U ; q is defined as the following ALCQI TBox: pKBq
¤
RNPR dsj Y
¤ C1C2PKB
relpRN q Y C1: C2: Y
¤ RNPR
¤ R1R2PKB lobjpRN q Y
R1: R: 2 dsj
ARiN1
ARjN2 | RN1; RN2 P R; i; j P T ; | i| ¥ 2; | j | ¥ 2; i j ( ¤
¤ iPT pRNq CHILDT p i; jq
ARiN DQ j . ARjN ; D¥2Q j . J K( tARN DQRN . AlRN ; D¥2QRN . J K; ARN DQRN . ARN ; D¥2QRN . J Ku:
l
Intuitively, dsj ensures that relations with different signatures are disjoint, thus, e.g., enforcing the union compatibility. The axioms in rel introduce classical reification axioms for each relation and its relevant projections. The axioms in lobj make sure that each local objectification differs form the global one.
Clearly, the size of pKBq is polynomial in the size of KB (under the same coding
of the numerical parameters), and thus we are able to state the main result of this paper
As a direct consequence of the above theorem and the fact that DLR is a sublanguage of DLR , we have that Corollary 3. Reasoning in DLR
is an EXPTIME-complete problem. 6
We thank Alessandro Mosca for working with us on all the preliminary work necessary to understand how to get these technical results.