=Paper=
{{Paper
|id=Vol-1577/paper_6
|storemode=property
|title=Extending DLR with Labelled Tuples, Projections, Functional Dependencies and Objectification
|pdfUrl=https://ceur-ws.org/Vol-1577/paper_6.pdf
|volume=Vol-1577
|authors=Alessandro Artale,Enrico Franconi
|dblpUrl=https://dblp.org/rec/conf/dlog/ArtaleF16
}}
==Extending DLR with Labelled Tuples, Projections, Functional Dependencies and Objectification==
<pdf width="1500px">https://ceur-ws.org/Vol-1577/paper_6.pdf</pdf>
<pre>
     Extending DLR with Labelled Tuples, Projections,
        Functional Dependencies and Objectification

                            Alessandro Artale and Enrico Franconi

                KRDB Research Centre, Free University of Bozen-Bolzano, Italy
                       {artale,franconi}@inf.unibz.it



         Abstract. 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 dependen-
         cies and with global and local objectification (reifying relations or their projec-
         tions). We show how a simple syntactic condition on the appearance of projec-
         tions and functional dependencies in a knowledge base makes the language de-
         cidable without increasing the computational complexity of the basic DLR lan-
         guage.


1     Introduction
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 identi-
      fied 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 dependen-
      cies and multiple-attribute keys, e.g., the functional dependency from firstname,
      lastname to age in Person can be written as:
      Drfirstname,lastnamesPerson Ď
            Dď1 rfirstname,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
            J | K | CN | C | C1 [ C2 | C1 \ C2 | Dijq rUi sR |
                                                                      Å         Ä
    C   Ñ                                                                  R |    RN
    R   Ñ   RN | R1 zR2 | R1 [ R2 | R1 \ R2 | σUi :C R | Dijq rU1 , . . . , Uk sR
    ϕ   Ñ   C1 Ď C2 | R1 Ď R2
    ϑ   Ñ   U1 í U2


                                     Fig. 1. Syntax of DLR` .

                         τ pR1 zR2 q “ τ pR1 q                if τ pR1 q “ τ pR2 q
                     τ pR1 [ R2 q “ τ pR1 q                   if τ pR1 q “ τ pR2 q
                     τ pR1 \ R2 q “ τ pR1 q                   if τ pR1 q “ τ pR2 q
                        τ pσUi :C Rq “ τ pRq                  if Ui P τ pRq
                 ijq
             τ pD rU1 , . . . , Uk sRq “ tU1 , . . . , Uk u   if tU1 , . . . , Uk u Ă τ pRq
                                 τ pRq “ H                    otherwise


                            Fig. 2. The signature of DLR` relations.


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 , . . . , Un u Ď 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í, Uq over the attributes U, pro-
viding 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 at-
tribute U w.r.t. the equivalence relation pí, Uq. We allow only well founded renaming
schemas, namely schemas such that each equivalence class rU s< in the induced equiv-
alence relation never contains two attributes from the same relation signature. In the
following we use the shortcut U1 . . . Un í U11 . . . Un1 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 re-
lations (see also the similar perspectives in relational databases [Abiteboul et al., 1995]).
They are crucial when expressing both inclusion axioms and operators ([, \, z)
between relations, which make sense only over union compatible relations. Two re-
lations R1 , R2 are union compatible if their signatures are equal up to the attribute
renaming induced by the renaming schema <, namely, τ pR1 q “ tU1 , . . . , Un u and
τ pR2 q “ tV1 , . . . , Vn u have the same arity n and rUi s< “ rVi s< for each 1 ď i ď n.
Notice that, thanks to the renaming schema, relations can use just local attribute names
that can then be renamed when composing relations. Also note that it is obviously pos-
sible for the same attribute to appear in the signature of different 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:

                              τ pR1 q “ tU1 , U2 , U3 , U4 , U5 u
                              τ pR2 q “ tV1 , V2 , V3 , V4 , V5 u
                              τ pR3 q “ tW1 , W2 , W3 , W4 u

To state that tU1 , U2 u is the multi-attribute key of R1 we add the axiom:

                              DrU1 , U2 sR1 Ď Dď1 rU1 , U2 sR1

where DrU1 , . . . , Uk sR stands for Dě1 rU1 , . . . , Uk sR. To express that there is a func-
tional dependency from the attributes tV3 , V4 u to the attribute tV5 u of R2 we add the
axiom:

                      DrV3 , V4 sR2 Ď Dď1 rV3 , V4 spDrV3 , V4 , V5 sR2 q                  (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 , W3 sR3 Ď DrU3 , U4 , U5 sR1
                                V1 V2 V3 V4 V5 í U1 U2 U3 U4 U5
                                   W1 W2 W3 í U3 U4 U5


3   Semantics
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 “ H
                p CqI “ JI zC I
           pC1 [ C2 qI “ C1I X C2I
           pC1 \ C2 qI “ C1I Y C2I
                                   ˇ                        ˇ
          pDijq rUi sRqI “ td P ∆ | ˇtt P RI | trρpUi qs “ duˇ ij qu
               p Rq “ td P ∆ | d “ ıptq ^ t P RI u
                Å I

             p RN qI “ td P ∆ | d “ `RN ptq ^ t P RN I u
              Ä


               pR1 zR2 qI “ R1I zR2I
           pR1 [ R2 qI “ R1I X R2I
           pR1 \ R2 qI “ tt P R1I Y R2I | ρpτ pR1 qq “ ρpτ pR2 qqu
             pσUi :C RqI “ tt P RI | trρpUi qs P C I u
pDijq rU1 , . . . , Uk sRqI “ txρpU1 q : d1 , . . . , ρpUk q : dk y P T∆ ptρpU1 q, . . . , ρpUk quq |
                              ˇ                                                       ˇ
                              ˇtt P RI | trρpU1 qs “ d1 , . . . , trρpUk qs “ dk uˇ ij qu


                               Fig. 3. Semantics of DLR` expressions.


xU1 : d1 , . . . , Un : dn y stands for the U-labelled tuple t over ∆ (tuple, for short) such
that trUi s “ di , for 1 ď 1 ď n. We write trU1 , . . . , Uk s 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∆ pUq.
    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 represent-
ing a canonical renaming for all attributes. We consider, as a shortcut, the notation
ρptU1 , . . . , Uk uq “ tρpU1 q, . . . , ρpUk qu.
The global objectification function is an injective function, ı : T∆ pUq Ñ ∆, associating
a unique global identifier to each possible tuple.
The local objectification functions, `RNi : T∆ pUq Ñ ∆, 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

                     @U . ρpU q P rU s< ^ @V P rU s< . ρpU q “ ρpV q.

     An interpretation is a model for a knowledge base pT , <q if it satisfies all the formu-
las 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 fol-
lowing logical implication holds:

                           KB |ù DrV1 , V2 sR2 Ď Dď1 rV1 , V2 sR2

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 de-
pendencies [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:

 1. τ pRN q P T if RN P R;
 2. tU u P T if U P U;
 3. tU1 , . . . , Uk u P T if Dijq rV1 , . . . , Vk sR P T and tUi , Vi u Ď rUi s< for 1 ď i ď k.

    We call projection signature graph the directed acyclic graph pĄ, T q with the at-
tribute 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.
                                              U3 U4 U5
                                 !                         )                 ! U3     U4 U5
                                                                                                     )
                                     U1 U2
                                     V1 , V2 , 3 , 4 , 5
                                              V   V   V                          V3 , V4 , V5 , W4
                                              W1 W2 W3                           W1 W2 W3


                                 (                    ! U3      U4 U5
                                                                             )
                      U1 U2
                      V1 , V2
                                                           V3 , V4 , V5                                  tW4 u
                                                           W1 W2 W3


              (              (                             ! U3     U4
                                                                         )            ! U5 )
         U1             U2
                                                               V3 , V4                 V5
         V1             V2
                                                               W1 W2                   W3

                                           ! U3 )                                     ! U4 )
                                             V3                                        V4
                                             W1                                        W2




                     Fig. 4. The projection signature graph of the example.



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 ,...,Uk u the tree formed by the nodes in the projection signature graph dom-
inated by the set of attributes tU1 , . . . , Uk u. Given two relation signatures (i.e., two sets
of attributes) τ1 , τ2 Ď U, by PATHT pτ1 , τ2 q we denote the path in pĄ, T q between τ1
and τ2 , if it exists. Note that PATHT pτ1 , τ2 q “ 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 , τ2 q 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 Dijq rU1 , . . . , Uk sR (resp. Dijq rU sR)
with a cardinality q ą 1 only if the length of the path PATHT ptU1 , . . . , Uk u, τ pRqq
(resp. PATHT ptU u, τ pRqq) is 1. This allows to map cardinalities in DLR˘ into cardi-
nalities 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].
                                            AR , A R                                 AR
                                              1      2                                  3
                             QtU ,U u                    QtU ,U ,U u
                                1  2                        3  4  5
                                                                                QtU ,U ,U u          QtW u
                                                                                   3  4  5              4

                   tU1 ,U2 u    tU1 ,U2 u     tU3 ,U4 ,U5 u    tU3 ,U4 ,U5 u    tU3 ,U4 ,U5 u              tW4 u
                  A          ,A              A              ,A               ,A                           A
                   R1           R2            R1               R2               R3                         R3

             QtU u            QtU u                      QtU ,U u                        QtU u
                1                2                          3  4                            5


     tU1 u    tU1 u    tU2 u   tU2 u               tU3 ,U4 u    tU3 ,U4 u    tU3 ,U4 u              tU5 u    tU5 u    tU5 u
    A      ,A         A      ,A                   A          ,A           ,A                    A         ,A       ,A
     R1       R2       R1      R2                  R1           R2           R3                     R1       R2       R3


                                                 QtU u                         QtU u
                                                    3                             4

                                     tU3 u    tU3 u    tU3 u                 tU4 u    tU4 u    tU4 u
                                    A      ,A       ,A                      A      ,A       ,A
                                     R1       R2       R3                    R1       R2       R3




                        Fig. 5. The ALCQI signature generated by the example.


5     Mapping DLR˘ to ALCQI
We show that reasoning in DLR˘ is E XP T IME-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 E XP T IME-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 ˝ . . . ˝ Sn q´ for Sn´ ˝ . . . ˝ S1´ , the shortcut
Dij1 S1 ˝ . . . ˝ Sn . C for Dij1 S1 . . . . . Dij1 Sn . 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˘ knowl-
edge 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.
For each relation name RN the mapping introduces a concept name AlRN and a role
name QRN (to capture the local reification), and a concept name AτRN           i
                                                                                  for each pro-
jected signature τi in the projection signature graph dominated by τ pRN q, τi P Tτ pRN q
                                                                                                       τ pRN q
(to capture global reifications of the projections of RN ). Note that ARN        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
CHILD T pτj , τi q, i.e., we exclude the case where τi is one of the roots of the multitree
induced by the projection signature.
                            p Cq: “ C :
                       pC1 [ C2 q: “ C1: [ C2:
                       pC1 \ C2 q: “ C1: \ C2:
                                         `                     ˘´
                      pDijq rUi sRq: “ Dijq PATHT pτ pRq, tUi uq: . R:
                           p Rq “ R:
                            Å :

                         p RN q: “ AlRN
                          Ä


                            pR1 zR2 q: “ R1: [ R2:
                        pR1 [ R2 q: “ R1: [ R2:
                        pR1 \ R2 q: “ R1: \ R2:
                          pσUi :C Rq: “ R: [ @PATHT pτ pRq, tUi uq: . C :
                                             `                                  ˘´
             pDijq rU1 , . . . , Uk sRq: “ Dijq PATHT pτ pRq, tU1 , . . . , Uk uq: . R:


                   Fig. 6. The mapping for concept and relation expressions.


The mapping ¨: applies also to a path. Let τ, τ 1 P T be two generic sets of attributes
such that the function PATHT pτ, τ 1 q “ τ, τ1 , . . . , τn , τ 1 , then, a path is mapped as fol-
lows:
                                       1 :
                         PATH T pτ, τ q      “ Qτ1 ˝ . . . ˝ Qτn ˝ Qτ 1 .

    Intuitively, the mapping reifies each node in the projection signature graph: the tar-
get 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 τ pRi q, 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 , τ2 q returns an empty path then the translation for
the corresponding expression becomes the bottom concept. Note that in DLR˘ the car-
dinalities 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 ap-
plies to cardinalities. So, if we need to express a cardinality constraint Dijq rUi sR,] 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, tUi uq| “ 1.
    In order to explain the need for the path function in the mapping, notice that a rela-
tion 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τ pRi q, Ui q
function. For example, considering Fig. 5, in order to access the attribute U4 of the re-
lation R3 in the expression pσU4 :C R3 q, the path PATHT pτ pR3 q, tU4 uq: is equal to the
role chain QtU3 ,U4 ,U5 u ˝QtU3 ,U4 u ˝QtU4 u , so that pσU4 :C R3 q: “ AR3 [@QtU3 ,U4 ,U5 u ˝
QtU3 ,U4 u ˝ QtU4 u . C.
Similar considerations can be done when mapping cardinalities over relation projec-
tions.
    The mapping γpKBq of a DLR˘ knowledge base KB with a signature pC, R, U, τ q
is defined as the following ALCQI TBox:
                                   ď                ď
               γpKBq “ γdsj Y          γrel pRN q Y     γlobj pRN q Y
                                            RN PR                 RN PR
                                        ď                           ď
                                                 C1: Ď C2:   Y                R1: Ď R2:
                                    C1 ĎC2 PKB                   R1 ĎR2 PKB

where
                                τ
        γdsj “ AτRN                 | RN1 , RN2 P R, τi , τj P T , |τi | ě 2, |τj | ě 2, τi ‰ τj
                                j
                                                                                                   (
                  i
                    1
                      Ď       ARN 2


                   ď                ď                         τj
                                               AτRN
                                                                                  (
γrel pRN q “                                      i
                                                    Ď DQτj . ARN , Dě2 Qτj . J Ď K
               τi PTτ pRN q CHILDT pτi ,τj q



γlobj pRN q “ tARN Ď DQRN . AlRN , Dě2 QRN . J Ď K,
               AlRN Ď DQ´
                        RN . ARN , D
                                    ě2 ´
                                      QRN . J Ď Ku.

    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
(see [Artale and Franconi, 2016] for a complete set of proofs of the Theorem).

Theorem 2. A DLR˘ knowledge base KB is satisfiable iff the ALCQI knowledge
base γpKBq is satisfiable.

   As a direct consequence of the above theorem and the fact that DLR is a sublan-
guage of DLR˘ , we have that

Corollary 3. Reasoning in DLR˘ is an E XP T IME-complete problem.


6   Acknowledgements
We thank Alessandro Mosca for working with us on all the preliminary work necessary
to understand how to get these technical results.
References
[Abiteboul et al., 1995] Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of
  Databases. Addison-Wesley, 1995.
[Artale and Franconi, 2016] Alessandro Artale and Enrico Franconi. Extending DLR with la-
  belled tuples, projections, functional dependencies and objectification (full version). CoRR,
  abs/1604.00799, April 2016.
[Artale et al., 2007] A. Artale, D. Calvanese, R. Kontchakov, V. Ryzhikov, and M. Za-
  kharyaschev. Reasoning over extended ER models. In Proc. of the 26th Int. Conf. on Concep-
  tual Modeling (ER’07), volume 4801 of Lecture Notes in Computer Science, pages 277–292.
  Springer, 2007.
[Baader et al., 2003] Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and
  Peter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation
  and Applications. Cambridge University Press, 2003.
[Berardi et al., 2005] D. Berardi, D. Calvanese, and G. De Giacomo. Reasoning on UML class
  diagrams. Artificial Intelligence, 168(1–2):70–118, 2005.
[Calvanese et al., 1998] D. Calvanese, G. De Giacomo, and M. Lenzerini. On the decidability of
  query containment under constraints. In Proc. of the 17th ACM Sym. on Principles of Database
  Systems (PODS’98), pages 149–158, 1998.
[Calvanese et al., 2001] Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. Iden-
  tification constraints and functional dependencies in description logics. In Proceedings of the
  Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01, pages 155–
  160. Morgan Kaufmann, 2001.
[Chandra and Vardi, 1985] Ashok K. Chandra and Moshe Y. Vardi. The implication problem
  for functional and inclusion dependencies is undecidable. SIAM Journal on Compututing,
  14(3):671–677, 1985.
[Franconi and Mosca, 2013] Enrico Franconi and Alessandro Mosca. Towards a core ORM2
  language (research note). In OTM Workshops, volume 8186 of Lecture Notes in Computer
  Science, pages 448–456. Springer, 2013.
[Mitchell, 1983] John C. Mitchell. The implication problem for functional and inclusion depen-
  dencies. Information and Control, 56(3):154–173, 1983.

</pre>