2001 · 101 citations · 8 references
ComputingComputer ScienceData ManagementKnowledge RepresentationLogicData ModelingDatabase DesignDeductive VerificationDescription LogicsFormal OntologyFormal SemanticsAutomated Reasoning With ConstraintsComplexityConstraintsDescription Logic ConstraintsDescription Logic ReasoningExpressive Description LogicsSatisfiabilityWorst-case Complexity
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.
8
The undecidability of the domino problem
Robert E. Berger · Memoirs of the American Mathematical Society · 1966 · 974 citations
Thomas Kirk, Alon Y. Levy, Yehoshua Sagiv et al. · 1995 · 257 citations
Description logic framework for information integration
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini et al. · 1998 · 244 citations