Keys, Nominals, and Concrete Domains

C. Lutz, C. Areces, I. Horrocks, and U. Sattler. Keys, Nominals, and Concrete Domains. Journal of Artificial Intelligence Research, 23:667–726, 2004.

Download

[pdf] 

Abstract

Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to 'concrete' domains like numbers and strings with built-in predicates such as >, +, and prefix-of. These hybrid DLs have turned out to be useful in several application areas, such as reasoning about conceptual database models. We propose to further extend such DLs with key constraints that allow the expression of statements like 'US citizens are uniquely identified by their social security number'. Based on this idea, we introduce a number of natural description logics and perform a detailed analysis of their decidability and computational complexity. It turns out that naive extensions with key constraints easily lead to undecidability, whereas more careful extensions yield NExpTime-complete DLs for a variety of useful concrete domains.

BibTeX

@Article{Lutz2004,
  author =       "C. Lutz and C. Areces and I. Horrocks and U. Sattler",
  journal =      "Journal of Artificial Intelligence Research",
  title =        "Keys, Nominals, and Concrete Domains",
  year =         "2004",
  pages =        "667--726",
  volume =       "23",
  abstract =     "Many description logics (DLs) combine knowledge
                 representation on an abstract, logical level with an
                 interface to 'concrete' domains like numbers and
                 strings with built-in predicates such as >, +, and
                 prefix-of. These hybrid DLs have turned out to be
                 useful in several application areas, such as reasoning
                 about conceptual database models. We propose to further
                 extend such DLs with key constraints that allow the
                 expression of statements like 'US citizens are uniquely
                 identified by their social security number'. Based on
                 this idea, we introduce a number of natural description
                 logics and perform a detailed analysis of their
                 decidability and computational complexity. It turns out
                 that naive extensions with key constraints easily lead
                 to undecidability, whereas more careful extensions
                 yield NExpTime-complete DLs for a variety of useful
                 concrete domains.",
}