Chair for Automata Theory LTCS{Report Description Logics with Concrete Domains and Functional Dependencies

Description Logics (DLs) with concrete domains are a useful tool in many applica-tions. 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 fun-damental family of key constraints: functional dependencies. In this paper, we consider the basic DL with concrete domains ALC(D), 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 depen-dencies 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