Identification Constraints and Functional Dependencies in Description Logics

Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini

Proc. of the 17th Int. Joint Conf. on Artificial Intelligence (IJCAI 2001). 2001.

DLR is an expressive Description Logic (DL) with n-ary relations, particularly suited for modeling database schemas. Although DLR has constituted one of the crucial steps for applying DL technology to data management, there is one important aspect of database schemas that DLs, including DLR , do not capture yet, namely the notion of identification constraints and functional dependencies. In this paper we introduce a DL which extends DLR and fully captures the semantics of such constraints, and we address the problem of reasoning in such a logic. We show that, verifying knowledge base satisfiability and logical implication in the presence of identification constraints and nonunary functional dependencies can be done in EXPTIME, thus with the same worst-case computational complexity as for plain DLR . We also show that adding just unary functional dependencies to DLR leads to undecidability.


@inproceedings{IJCAI-2001,
   title = "Identification Constraints and Functional Dependencies in
Description Logics",
   year = "2001",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini",
   booktitle = "Proc. of the 17th Int. Joint Conf. on Artificial Intelligence
(IJCAI 2001)",
   pages = "155--160",
}
ps.gz pdf