=Paper=
{{Paper
|id=Vol-2037/paper6
|storemode=property
|title=A Decidable Very Expressive n-ary Description Logic for Database Applications (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-2037/paper_6.pdf
|volume=Vol-2037
|authors=Alessandro Artale,Enrico Franconi,Rafael Peñaloza,Francesco Sportelli,Valeria Fionda,Giuseppe Pirrò,Andrea Calì,Davide Martinenghi,Riccardo Torlone,Roberto Corizzo,Gianvito Pio,Michelangelo Ceci, Donato Malerba,Serena Ammirati,Donatella Firmani,Marco Maiorino,Paolo Merialdo,Elena Nieddu,Andrea Rossi,Michele Ianni,Elio Masciari,Roberto Boselli,Mirko Cesarini,Fabio Mercorio,Mario Mezzanzanica,Flora Amato,Vincenzo Moscato,Antonio Picariello,Giancarlo Sperlì,Montserrat Estañol,Mirjana Mazuran,Xavier Oriol,Letizia Tanca,Ernest Teniente,Francesca Spezzano,Andrea Calì,Giuseppe De Santis,Tommaso Di Noia,Nicola Mincuzzi,Pietro Hiram Guzzi,Pierangelo Veltri,Swarup Roy,Jugal Kalita,Simone Porreca,Francesco Leotta,Massimo Mecella,Tiziana Catarci,Laura Di Rocco,Roberto Marzocchi,Tiziano Cosso,Barbara Catania,Giovanna Guerrini,Ilaria Bartolini,Marco Patella,Loredana Caruccio,Vincenzo Deufemia,Giuseppe Polese,Bernardo Cuteri,Francesco Ricca,Gianluca Cima,Giuseppe De Giacomo,Maurizio Lenzerini,Antonella Poggi,Alex Badan,Luca Benvegnù,Matteo Biasetton,Giovanni Bonato,Alessandro Brighente,Stefano Marchesin,Alberto Minetto,Leonardo Pellegrina,Alberto Purpura,Riccardo Simionato,Matteo Tessarotto,Andrea Tonon,Nicola Ferro,Francesco Buccafurri,Gianluca Lax,Serena Nicolazzo,Antonino Nocera,Marco Manna,Francesco Ricca,Giorgio Terracina,Carlotta Domeniconi,Francesco Gullo,Andrea Tagarelli,Francesco De Fino,Barbara Catania,Giovanna Guerrini,Roberto Interdonato,Chiara Pulice,Andrea Tagarelli,Giovanni Amendola,Nicola Leone,Marco Manna,Tania Cerquitelli,Evelina Di Corso,Francesco Ventura,Silvia Chiusano,Antonio Circiello,Andrea Cappelli,Sonia Bergamaschi,Marco Varone,Sergio Greco,Cristian Molinaro,Irina Trubitsyna,Devis Bianchini,Valeria De Antonellis,Michele Melchiori,Marco Cameranesi,Claudia Diamantini,Laura Genga,Domenico Potena,Enzo Veltri,Donatello Santoro,Giansalvatore Mecca,Paolo Papotti,Jian He,Gouliang Li,Nan Tang,Giuseppe Tradigo,Rocco Picarelli,Luciano Caroprese,Paolo Cappadone,Ester Zumpano,Andrea Tagarelli,Angelo Furfaro,Carlo Tansi,Pierangelo Veltri,Pietro Hiram Guzzi,Massimiliano de Leoni,Andrea Marrella,Alfredo Cuzzocrea,Osvaldo Gervasi,Mirko Mariotti,Flavio Vella,Alessandro Costantini,Gloria Bordogna,Alfredo Cuzzocrea,Luca Frigerio,Giuseppe Psaila,Danilo Amendola,Nunziato Cassavia,Sergio Flesca,Michele Ianni,Elio Masciari,Giuseppe Papuzzo,Chiara Pulice,Pietro Cinaglia,Pierangelo Veltri,Mario Cannataro,Antonella Longo,Marco Zappatore,Mario Bochicchio,Lucia Vaira,Alfredo Cuzzocrea
|dblpUrl=https://dblp.org/rec/conf/sebd/ArtaleFPS17
}}
==A Decidable Very Expressive n-ary Description Logic for Database Applications (Extended Abstract)==
<pdf width="1500px">https://ceur-ws.org/Vol-2037/paper_6.pdf</pdf>
<pre>
    A Decidable Very Expressive n-ary Description Logic
       for Database Applications (extended abstract)

         Alessandro Artale, Enrico Franconi, Rafael Peñaloza, Francesco Sportelli
                KRDB Research Centre, Free University of Bozen-Bolzano, Italy
             {artale,franconi,penaloza,sportelli}@inf.unibz.it



         Abstract. We introduce DLR`, an extension of the n-ary propositionally closed
         description logic DLR to deal with attribute-labelled tuples (generalising the po-
         sitional notation), projections of relations, and global and local objectification of
         relations, able to express inclusion, functional, key, and external uniqueness de-
         pendencies. 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 reason-
         ing 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.


1     Introduction
We introduce the new description logic (DL) DLR` extending the n-ary DL DLR [Cal-
vanese 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 con-
cepts and (compatible) n-ary relations, (ii) concepts as unary projections of n-ary re-
lations, and (iii) relations with a component selected to be of a certain type. For ex-
ample, if Pilot and RacingCar are concepts and DrivesCar, DrivesMotobike,
DrivesVehicle are binary relations, we can write the following axioms:
    Pilot Ď Dr1sσ2:RacingCar DrivesCar
    DrivesCar \ DrivesMotobike Ď DrivesVehicle .
DLR` extends DLR in the following way.
    – While DLR instances of n-ary relations are n-tuples of objects—whose compo-
      nents 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 (see, e.g., [Kanellakis, 1990]). For ex-
      ample, the relation Employee may have the signature:
          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 iden-
      tifiers 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 as-
      sume 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 ax-
      ioms CarDrivingEvent ” DrivesCar and CarOwningEvent ” OwnsCar,
      model the fact that a driving event by a person of a car is not necessarily the own-
      ing 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 identifica-
tion 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, lastnamesEmployeeĎDď1 rfirstname, lastnamesEmployee ,
and that the attribute deptAddr functionally depends on the attribute dept within the
relation Employee:
        DrdeptsEmployee Ď Dď1 rdepts 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     The Description Logic DLR`
A DLR` signature is a tuple L “ pC, R, O, U, τ q where C, R, O and U are finite, mu-
tually 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 , . . . , Un u Ď 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
              J | K | CN | C | C1 [ C2 | C1 \ C2 | Dijq rUi sR |
                                                                              Å        Ä
     C   Ñ                                                                       R |      RN
                                                                    ijq
     R   Ñ    RN | R1 zR2 | R1 [ R2 | R1 \ R2 | σUi :C R | D rU1 , . . . , Uk sR
     ϕ   Ñ    C1 Ď C2 | R1 Ď R2 | CN poq | RN pU1 :o1 , . . . , Un :on q | o1 “ o2 | o1 ‰ o2
     ϑ   Ñ    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
              τ pDijq rU1 , . . . , Uk sRq “ tU1 , . . . , Uk u   if tU1 , . . . , Uk u Ă τ pRq
                                    τ pRq “ H                    otherwise
                             Fig. 2. The signature of DLR` relations.

                                                                         Å
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 , . . . , Uk sR for Dě1 rU1 , . . . , Uk sR 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 :on q, and
same/distinct individual axioms of the form o1 “o2 and o1 ‰o2 , with oi PO. 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 re-
lation pÕ, Uq 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Õ, Uq. 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 . . . Un1
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 at-
tribute renaming induced by the renaming schema <; that is, τ 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 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 pos-
sible 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 τ pR1 q “ tW1 , W2 , W3 , W4 u,
τ pR2 q “ tV1 , V2 , V3 , V4 , V5 u, and the renaming axiom W1 W2 W3 Õ V3 V4 V5 . The TBox
Texa consists of the axioms:

                          DrW1 , W2 sR1 Ď Dď1 rW1 , W2 sR1                                       (1)
                                                  ď1
                            DrV3 , V4 sR2 Ď D          rV3 , V4 spDrV3 , V4 , V5 sR2 q           (2)
                           JI “ ∆
                           KI “ H
                      p CqI “ JI zC I
             pC1 [ C2 qI “ C1I X C2I
             pC1 \ C2 qI “ C1I Y C2Iˇ                                     ˇ
                            I                         I
            pDijq rU    i sRq “ td P ∆ | tt P R | trρpUi qs “ du ij qu
                                           ˇ                              ˇ
                     Å      I                                   I
                    p     Rq  “ td P ∆ | d   “ ıptq    ^  t P R   u
                 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
    pD rU1 , . . . , Uk sRqI “ txρpUˇ 1 q : d1 , . . . , ρpUk q : dk y P T∆ ptρpU1 q, . . . , ρpU
      ijq
                                                                                               ˇ k quq |
                                 1 ď ˇtt P RI | trρpU1 qs “ d1 , . . . , trρpUk qs “ dk uˇ ij qu
                              Fig. 3. Semantics of DLR` expressions.


                     DrW1 , W2 , W3 sR1 Ď DrV3 , V4 , V5 sR2 .                                             (3)
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 : dn y stands for the tuple t such that trUi s “ 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 , . . . , Uk s. The relation
signature function τ can be applied also to labelled tuples to obtain the set of labels on
which the tuple is defined. T∆ pUq 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 , . . . , Uk uq to denote tρpU1 q, . . . , ρpUk qu.
The global objectification function is an injective function, ı : T∆ pUq Ñ ∆, associat-
ing a unique global identifier to each tuple. The local objectification functions, `RNi :
T∆ pUq Ñ ∆, are associated to each relation name in the signature, and as the global
objectification function they are injective: they associate an identifier—which is guar-
anteed 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 func-
tion 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 in-
stance axiom CN poq if oI P CN I, the relation instance axiom RN pU1 :o1 , . . . , Un :on q
if xρpU1 q : oI1 , . . . , ρpUn q : oIn y P RN I , and the axioms o1 “ o2 and o1 ‰ o2 if oI1 “ oI2 ,
and oI1 ‰ oI2 , 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 , V4 sR2 Ď Dď1 rV3 , V4 sR2 .


3    Expressiveness of DLR`

DLR` is an expressive description logic able to assert relevant constraints in the con-
text of relational databases, such as inclusion dependencies (inclusion axioms among ar-
bitrary 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 combi-
nations of tuples in the relations that are equal on their selected attribute names. Let
R1 , R2 be relations with τ pR1 q “ tU, U1 , . . . , Un1 u and τ pR2 q “ tV, V1 , . . . , Vn2 u;
their equijoin over U and V is the relation R “ R1 ’ R2 that uses the signature
                                                                U “V
τ pRq “ τ pR1 q Y τ pR2 qztV u, and is expressed by the DLR` axioms:
     DrU, U1 , . . . , Un1 sR ” σU :pDrU sR1 [DrV sR2 q R1
     DrV, V1 , . . . , Vn2 sR ” σV :pDrU sR1 [DrV sR2 q R2
     U ÕV .
A functional dependency axiom pR : U1 . . . Uj Ñ U q (also called internal uniqueness
axiom [Halpin and Morgan, 2008]) states that the values of the attributes U1 . . . Uj
uniquely determine the value of the attribute U in the relation R. Formally, the in-
terpretation I satisfies this functional dependency axiom if, for all tuples s, t P RI ,
srU1 s “ trU1 s, . . . , srUj s “ trUj s imply srU s “ trU s. Functional dependencies can be
expressed in DLR`, assuming that tU1 , . . . , Uj , U u Ď τ pRq, with the axiom:
    DrU1 , . . . , Uj sR Ď Dď1 rU1 , . . . , 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ď1 rU1 , . . . , Uj sR .
The external uniqueness axiom prU 1 sR1 Ó . . . Ó rU h sRh q states that the join R of the
relations R1 , . . . , Rh via the attributes U 1 , . . . , U h has the joined attribute function-
ally dependent on all the others [Halpin and Morgan, 2008]. This can be expressed in
DLR` with the axioms:
     R ” R1 ’ ¨ ¨ ¨ ’ Rh
              U 1 “U 2       U h´1 “U h
    R : U11 , . . . , Un11 , . . . , U1h , . . . , Unhh Ñ U 1
where τ pRi q “ 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 ex-
ternal uniqueness axioms, constraining only the elements of a concept C; they can be
expressed in DLR` with the axiom:
    rU 1 sσU1 :C R1 Ó . . . Ó rU h sσ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 asso-
ciation 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 , . . . , Uk u P T for all Dijq rV1 , . . . , Vk sR
appearing as sub-formulas in T and tUi , Vi u Ď rUi s< 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 , . . . , Uk u Ď U, the pro-
jection 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,
PATH T pτ1 , τ2 q denotes the set of paths in pĄ, T q between τ1 and τ2 . Notice that
PATH T pτ1 , τ2 q “ H both when a path does not exist and when τ1 Ď τ2 . The notation
CHILD T pτ1 , τ2 q 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` knowledge base that satisfies the
following syntactic conditions:
 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 Dijq rU1 , . . . , Uk sR appearing in T , if q ą 1 then the
    length of the path PATHT pτ pRq, tU1 , . . . , Uk uq is 1.
                        tW1 , W2 , W3 , W4 u                        tV1 , V2 , V3 , V4 , V5 u

                                           "                        *
                                               W1 , W 2 , W 3
                               tW4 u                                         tV1 u         tV2 u
                                                V3 , V4 , V5

                                               "                *          "        *
                                                   W1 , W 2                    W3
                                                   V3 , V4                     V5

                              "        *           "        *
                                  W1                   W2
                                  V3                   V4

                    Fig. 4. The projection signature graph of Example 1.


The conditions in DLR˘ restrict DLR` in the way that multiple projections of rela-
tions 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 unique-
ness and identification axioms by encoding them into a set of saturated ABoxes (as
originally proposed in [Calvanese et al., 2001]) and check whether there is a saturation
that satisfies the constraints. Therefore, we can conclude that DLRifd extended with
unary functional dependencies is included in DLR˘, provided that projections of rela-
tions in the knowledge base form a multitree projection signature graph. Since (unary)
functional dependencies are expressed via the inclusions of projections of relations, 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. Concerning the ability of DLR˘ to capture conceptual
data models, only the mapping of ORM schemas is affected by the DLR˘ restrictions:
the projections involved in the ORM schema should satisfy the DLR˘ multitree re-
striction.
     The main result of this work is that reasoning in DLR˘ is an E XP T IME-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   Implementation
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.


References
[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.
[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., 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.
[Calvanese et al., 2008] Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. Con-
  junctive query containment and answering under description logic constraints. ACM Trans.
  Comput. Logic, 9(3):22:1–22:31, June 2008.
[Calvanese et al., 2014] Diego Calvanese, Wolfgang Fischl, Reinhard Pichler, Emanuel
  Sallinger, and Mantas Simkus. Capturing relational schemas and functional dependencies in
  RDFS. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages
  1003–1011. AAAI Press, 2014.
[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 et al., 2012] Enrico Franconi, Alessandro Mosca, and Dmitry Solomakhin. ORM2:
  formalisation and encoding in OWL2. In International Workshop on Fact-Oriented Modeling
  (ORM 2012), pages 368–378, 2012.
[Halpin and Morgan, 2008] Terry Halpin and Tony Morgan. Information Modeling and Rela-
  tional Databases. Morgan Kaufmann, 2nd edition, 2008.
[Kanellakis, 1990] Paris C. Kanellakis. Elements of relational database theory. In A.R. Meyer,
  M. Nivat, M.S. Paterson, D. Perrin, and J. van Leeuwen, editors, The Handbook of Theoretical
  Computer Science, volume B, chapter 17, pages 1075–1144. North Holland, 1990.
[Sportelli and Franconi, 2016] Francesco Sportelli and Enrico Franconi. Formalisation of ORM
  derivation rules and their mapping into OWL. In ODBASE Conference 2016, pages 827–843,
  2016.
[Toman and Weddell, 2009] David Toman and Grant E. Weddell. Applications and extensions
  of PTIME description logics with functional constraints. In IJCAI 2009, Proceedings of the
  21st International Joint Conference on Artificial Intelligence, pages 948–954, 2009.

</pre>