Keys for Free in Description Logics

Proc. of the 13th Int. Workshop on Description Logics (DL 2000). Volume 33 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2000.

DLR is an expressive DL with n-ary relations, particularly suited for modeling database schemas and queries. 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 do not capture yet, namely the notion of key. In this paper we give keys for free to those who like DLR . In particular, the question addressed in this paper is as follows: can we add keys to DLR and still have EXPTIME associated reasoning techniques? Somewhat surprisingly, we answer positively to the question, by adapting the DLR reasoning algorithm in such a way that reasoning on a DLR schema with keys can be done with the same worst-case computational complexity as for the case without keys.

@inproceedings{DL-2000,
   title = "Keys for Free in Description Logics",
   year = "2000",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini",
   booktitle = "Proc. of the 13th Int. Workshop on Description Logics
(DL 2000)",
   pages = "79--88",
   volume = "33",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}