Identification constraints and functional dependencies in description logics

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.