Reasoning in description logics using declarative logic programming
Güray Alsaç, Chitta R. Baral · 2004
In this paper our goal is to bridge two popular and wellstudied knowledge representation formalisms: description logics (DLs), and declarative logic programs (DLPs). In recent years there has been tremendous development in both fields in terms of theoretical studies and implementations. However, despite a few papers on allowing logic programming style rules in description logic, there has been little research on how they relate to each other, how one can be simulated by the other, and how ideas and constructs in one can be used in the other. We show that DLs can be simulated in DLPs and point out why early description logic researchers thought this was not possible. Besides giving a general translation that produces a not so efficient DLP we consider special cases for which more efficient DLPs can be constructed. We also suggest new DL constructs inspired by DLPs. Introduction and Motivation One of the important sub-fields of knowledge representation and reasoning centers around description logics, also referred to as concept languages and terminological systems at different stages of its evolution. Its origin traces back to frame based systems and semantic networks, both early attempts to represent the classification of objects to a hierarchy of classes (w.r.t. the subset relationship), represent (mostly binary) relationships between classes, and reason with such information. A critical evolutionary step in this field, the KL-ONE system (Brachman & Schmolze 1985), formalized the main ideas in various frame based and semantic network based systems into a logical characterization of classes (or concepts), and relationships (or roles), and proposed a set of constructs to build new classes and relationships from these. Since then, several different description logics have been proposed, each distinguished by the constructs and kinds of relationships allowed. Many of these have been implemented (for example, (Borgida et al. 1989)), usually in sound but incomplete fashion. For some, reasoning methodologies have been proposed, and for some the complexity of reasoning has been analyzed. In analyzing the complexity it has been noticed that sometimes seemingly minor syntactic extensions increases the complexity drastically. Recently many attempts have been made in developing expressive description logics with greater applicability. Copyright c © 2002, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. For example, in (Calvanese, DeGiacomo, & Lenzerini 2001) identification constraints and functional dependencies are added to the description logicDLR, which already includes n-ary relations. In (Haarslev & Moller 2000) a description logic with number restrictions, role hierarchies and transitively closed roles is proposed. In (Levy & Rousset 1996; Cadoli, Palopoli, & Lenzerini 1997; Donini et al. 1998) description logics are augmented with Datalog constructs and hybrid languages are proposed. We now give a small example of representation using description logic and then discuss the applicability and usefulness of description logics. Consider a simple hierarchy of concepts with person at the top (meaning every object in the world is a person) and beneath it the atomic concepts male and female. Also, let childof be an atomic relation. Using these we can define a new concept child consisting of elements x such that there exists a person y and (x, y) belongs to the relation childof (i.e., x is a child of y). In classical logic this is expressed as child(x) ≡ ∃y childof(x, y) ∧ person(y). In description logic it is said that the concept child can be formed using the concept person and the role childof using the construct ∃≥n as ∃≥1childof.person. Since person is the top concept, it may be skipped and it is enough to write ∃≥1childof or simply ∃childof . Similarly, a concept son can be formed by male u child meaning that the concept son consists of elements who are both male and child. In Borgida’s (Borgida 1992) syntax, the above definitions of child and son are expressed as child = at-least[1, childof ] and son = and[male, child]. Many consider such description logic expressions to be easier to write and follow than the corresponding expression in classical logic, as in the former the variables are not explicitly specified. Some query languages for querying object oriented databases also have a similar syntax. A knowledge base in a description logic consists of two parts traditionally referred to as the TBox (meaning “Terminological Box”) and the ABox (meaning “Assertional Box”). The first consists of several assertions about concepts and roles, such as the definition of child and son in the above example, and the second consists of specific facts about a particular object belonging to a concept or a particular pair of objects belonging to a particular role, such as Jim being