Description Logics with Concrete Domains and Functional Dependencies

Carsten LutzCarsten Lutz, M. MilicicM. Milicic

Download

Carsten Lutz, M. Milicic
Description Logics with Concrete Domains and Functional Dependencies
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-04-06, 2004. LTCS-Report

Details
Bibtex

KurzfassungAbstract
Description Logics (DLs) with concrete domains are a useful tool in many applications. To further enhance the expressive power of such DLs, it has been proposed to add database-style key constraints. Up to now, however, only uniqueness constraints have been considered in this context, thus neglecting the second fundamental family of key constraints: functional dependencies. In this paper, we consider the basic DL with concrete domains alcd, extend it with functional dependencies, and analyze the impact of this extension on the decidability and complexity of reasoning. Though intuitively the expressivity of functional dependencies seems weaker than that of uniqueness constraints, we are able to show that the former have a similarly severe impact on the computational properties: reasoning is undecidable in the general case, and NExpTime-complete in some slightly restricted variants of our logic.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ LutzMilicic-LTCS-04-06,
  address = {Germany},
  author = {C. {Lutz} and M. {Milicic}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {LTCS-04-06},
  title = {Description Logics with Concrete Domains and Functional Dependencies},
  type = {LTCS-Report},
  year = {2004},
}