Download (direct link):
Listing 8.2 Example of frame-based knowledge representation.
Semantic networks evolved to frame-based systems. Frame-based systems led to the development of description logics. The frame-based language KL-ONE was also the first description logic because, in addition to supporting frame representation, it was formalized logically with description-forming structures (related to our previous discussion of general descriptions, but used in the more technical sense of intensional descriptions). A description in a description logic is an expression in a formal language that defines a set of instances or tuples (the extension, as we've seen). A description logic, therefore, is a language for representing knowledge that has a syntax and a semantics—a syntax for constructing descriptions and a semantics that defines the meaning of each description.
Description logics are sometimes called terminological logics, classification logics, or concept logics. They are based on a declarative formalism—a language— for defining concepts in multiple hierarchies/taxonomies that are organized in a subsumption framework. Subsumption is a special relation, such as the subclass of or isa relation in object models and ontologies, that organizes the entire model into a generalization/specialization hierarchy, with more general information as you go upward in the hierarchy and more specific information as you go downward. Mathematically, the subsumption relation generates a partially ordered set or poset. Because subsumption in the general case is undecid-able (consider undecidability as meaning that a query may never terminate, since it will be searching an infinite space, and so no decision procedure can be constructed that can decide whether or not a given query will terminate and return with results), description logics try to get around that problem by limiting the knowledge representation language and other tricks.
Description logics as a technical thread of knowledge representation was founded to:
■■ Formalize the nature of knowledge representation logically, or develop a formalism based on logic for the representation and expression of knowledge.
■■ Provide for sound, tractable reasoning methods founded on a firm theoretical and logical basis.
Generally, description logics have tried to create knowledge representation languages that enable both expressivity of the knowledge (i.e., richness of the detail of the semantics of the world portion you want to model) and tractable reasoning—which, in general, means to develop a logical language that is less expressive (but perhaps expressive enough to represent useful knowledge?) and less formally powerful than first-order logic (the predicate calculus) and thus more tractable for machine interpretation and automated inference (to get around the decidability issue mentioned previously). Although we will talk
briefly about first-order logic in the next section, we observe now that most description logics are defined in terms of a function-free first-order logic that uses at most three variables and are defined to be sound, complete, and decid-able (these are formal properties of logics, which we will see shortly), and tractable (amenable to efficient computational use).
Listing 8.3 shows an example of some assertions in the LOOM description logic.18 In this example, the first relation At-Least-One-Son logically defines the set of all persons that have at least one son. The second relation More-Sons-Than-Daughters logically defines the set of all persons for whom it is the case that they have more sons than daughters. The :if-def indicates that the definition is total, rather than partial (:def), and :setof indicates a set expression, that is, an unnamed relation with domain variables (here, ?c) and definition (here, (son ?p ?c)).
(defrelation At-Least-One-Son (?p)
(setof (?c) (son ?p ?c)))
(defrelation More-Sons-Than-Daughters (?pp)
(setof (?b) (son?pp ?b)))
(setof (?g) (daughter ?pp ?g))))))
Listing 8.3 LOOM description logic example.
LOOM is among the class of description logic knowledge representation languages developed during the past 20 years. Others include Classic, KRIS, and more recently, FaCT—the description logic used as the back-end classifier and inference engine of OntoEdit, which enables you to build ontologies in DAML+OIL.19 But now, let's shift into a brief description of logic, the formal substrate for all knowledge representation and Semantic Web languages (and perhaps even English!).
18MacGregor (1994), pp. 2-4.