Abstract

The purpose of the chapter is to help someone familiar with DLs to understand the issues involved in developing an ontology for some universe of discourse, which is to become a conceptual model or knowledge base represented and reasoned about using Description Logics.

We briefly review the purposes and history of conceptual modeling, and then use the domain of a university library to illustrate an approach to conceptual modeling that combines general ideas of object-centered modeling with a look at special modeling/ontological problems, and DL-specific solutions to them.

Among the ontological issues considered are the nature of individuals, concept specialization, non-binary relationships, materialization, aspects of part–whole relationships, and epistemic aspects of individual knowledge.

Background

Information modeling is concerned with the construction of computer-based symbol structures that model some part of the real world. We refer to such symbol structures as information bases, generalizing the term from related terms in Computer Science, such as databases and knowledge bases. Moreover, we shall refer to the part of a real world being modeled by an information base as its universe of discourse (UofD). The information base is checked for consistency, and sometimes queried and updated through special-purpose languages. As with all models, the advantage of information models is that they abstract away irrelevant details, and allow more efficient examination of both the current, as well as past and projected future states of the UofD.

Abstract

In contrast to the relatively complex information that can be expressed in DL ABoxes (which we might call knowledge or information), databases and other sources such as files, semistructured data, and the World Wide Web provide rather simpler data, which must however be managed effectively. This chapter surveys the major classes of application of Description Logics and their reasoning facilities to the issues of data management, including: (i) expressing the conceptual domain model/ontology of the data source, (ii) integrating multiple data sources, and (iii) expressing and evaluating queries. In each case we utilize the standard properties of Description Logics, such as the ability to express ontologies at a level closer to that of human conceptualization (e.g., representing conceptual schemas), determining consistency of descriptions (e.g., determining if a query or the integration of some schemas is consistent), and automatically classifying descriptions that are definitions (e.g., queries are really definitions, so we can classify them and determine subsumption between them).

Introduction

According to [EIMasri and Navathe, 1994], a database is a coherent collection of related data, which have some “inherent meaning”. Databases are similar to knowledge bases because they are usually used to maintain models of some universe of discourse (UofD). Of course, the purpose of such computer models is to support end-users in finding out things about the world, and therefore it is important to maintain an up-to-date and error-free model.

Introduction

Mutual exclusion algorithms, like those we discussed in Chapter 7, have an abstract behaviour described by the following pseudocode:

1. while true do

2. begin

1. remainder region

2. trying region

3. critical section

4. exit region

1. end

It is supposed that such algorithms satisfy the following two properties.

• Mutual exclusion No two processes are in their critical sections at the same time.

• Deadlock freedom If some process is in its trying region then eventually some process is in its critical section. (Note that the process in the critical section might be different from the one initially in its trying region.) Moreover, if a process is in its exit region then that process will eventually enter its remainder region.

As stated in Lynch and Shavit (1992), the known asynchronous mutual exclusion algorithms for n processes require O(n) read and write registers and O(n) operations to access the critical section. These bounds make them rather impractical for large-scale applications, where the number of processes could be very large. This raises the question whether it is possible to achieve mutual exclusion in asynchronous systems consisting of n processes by using a smaller number of shared registers and/or fewer than O(n) operations to access the critical section. Unfortunately, this is impossible for ‘classic reactive systems’ in an asynchronous setting. In fact, Burns and Lynch (1980, 1993) showed the following theorem.

Abstract

In this chapter, we are concerned with the relationship between Description Logics and other formalisms, regardless of whether they were designed for knowledge representation issues or not. We concentrate on those representation formalisms that either (1) had or have a strong influence on Description Logics (e.g., modal logics), (2) are closely related to Description Logics for historical reasons (e.g., semantic networks and structured inheritance networks), or (3) have similar expressive power (e.g., semantic data models). There are far more knowledge representation formalisms than those mentioned in this chapter. For example, “verb-centered” graphical formalisms like those introduced by Simmons [1973] are not mentioned since we believe that their relationship with Description Logics is too weak.

AI knowledge representation formalisms

In artificial intelligence (AI), various “non-logical” knowledge representation formalisms were developed, motivated by the belief that classical logic is inadequate for knowledge representation in AI applications. This belief was mainly based upon cognitive experiments carried out with human beings and the wish to have representational formalisms that are close to the representations in human brains. In this section, we discuss some of these formalisms, namely semantic networks, frame systems, and conceptual graphs. The first two formalisms are mainly presented for historical reasons since they can be regarded as ancestors of Description Logics. In contrast, the third formalism can be regarded as a “sibling” of Description Logics since both have similar ancestors and live in the same time.

Introduction to Hennessy–Milner logic

In the previous chapters we have seen that implementation verification is a natural approach to establishing the correctness of (models of) reactive systems described, for instance, in the language CCS. The reason is that CCS, like all other process algebras, can be used to describe both actual systems and their specifications. However, when establishing the correctness of our system with respect to a specification using a notion of equivalence such as observational equivalence, we are forced to specify in some way the overall behaviour of the system.

Suppose, for instance, that all we want to know about our system is whether it can perform an a-labelled transition ‘now’. Phrasing this correctness requirement in terms of observational equivalence seems at best unnatural and maybe cannot be done at all! (See the paper Boudol and Larsen (1992) for an investigation of this issue.)

We can imagine a whole array of similar properties of a process that we might be interested in specifying and checking. For instance, we may wish to know whether our computer scientist of Chapter 2

• is not willing to drink tea now,

• is willing to drink both coffee and tea now,

• is willing to drink coffee, but not tea, now,

• never drinks alcoholic beverages, or

• always produces a publication after drinking coffee.

Abstract

The purpose of this appendix is to introduce (in a compact manner) the syntax and semantics of the most prominent DLs occurring in this handbook. More information and explanations as well as some less familiar Description Logics can be found in the respective chapters. For DL constructors whose semantics cannot be described in a compact manner, we will only introduce the syntax and refer the reader to the respective chapter for the semantics. Following Chapter 2 on basic Description Logics, we will first introduce the basic Description Logic AL, and then describe several of its extensions. Thereby, we will also fix the notation employed in this handbook. Finally, we will comment on the naming schemes for Description Logics that are employed in the literature and in this handbook.

Notational conventions

Before starting with the definitions, let us introduce some notational conventions. The letters A,B will often be used for atomic concepts, and C,D for concept descriptions. For roles, we often use the letters R, S, and for functional roles (features, attributes) the letters f, g. Nonnegative integers (in number restrictions) are often denoted by n,m, and individuals by a, b. In all cases, we may also use subscripts. This convention is followed when defining syntax and semantics and in abstract examples. In concrete examples, the following conventions are used: concept names start with an uppercase letter followed by lowercase letters (e.g., Human, Male), role names (also functional ones) start with a lowercase letter (e.g., hasChild, married To), and individual names are all uppercase (e.g., CHARLES, MARY).

Knowledge Representation is the field of Artificial Intelligence that focuses on the design of formalisms that are both epistemologically and computationally adequate for expressing knowledge about a particular domain. One of the main lines of investigation has been concerned with the principle that knowledge should be represented by characterizing classes of objects and the relationships between them The organization of the classes used to describe a domain of interest is based on a hierarchical structure, which not only provides an effective and compact representation of information, but also allows the relevant reasoning tasks to be performed in a computationally effective way.

The above principle drove the development of the first frame-based systems and semantic networks in the 1970s. However, these systems were in general not formally defined and the associated reasoning tools were strongly dependent on the implementation strategies. A fundamental step towards a logic-based characterization of required formalisms was accomplished through the work on the Kl-One system, which collected many of the ideas stemming from earlier semantic networks and frame-based systems, and provided a logical basis for interpreting objects, classes (or concepts), and relationships (or links, roles) between them. The first goal of such a logical reconstruction was the precise characterization of the set of constructs used to build class and link expressions. The second goal was to provide reasoning procedures that are sound and complete with respect to the semantics.

Real-time reactive systems

In the first part of this book, we motivated and developed a general-purpose theory that can be used to describe, and reason about, reactive systems. The key ingredients in our approach were:

• an algebraic language, namely Milner's CCS, for the syntactic description of reactive systems;

• automata, e.g. labelled transition systems (LTSs), for describing the dynamic behaviour of process terms;

• structural operational semantics allowing us to associate systematically an LTS with each process term in a syntax-directed fashion;

• notions of behavioural equivalence for the comparison of process behaviours; and

• modal and temporal logics to specify desired properties of reactive systems.

These ingredients gave the foundations for the formal modelling and verification of reactive systems and are the bedrock for the development of (semi-)automatic verification tools for reactive systems.

The theory that we have developed so far, however, does not allow us to describe naturally all the important aspects in reactive computation. Consider, for instance, some, by now ubiquitous, examples of reactive systems, namely embedded systems like the ABS and air bags in cars, cruise-control systems, digital watches, mobile phones, computer monitors, production lines and video-game consoles. These are all examples of real-time systems. A real-time system is a system whose correct behaviour depends not only on the logical order in which events are performed but also on their timing.

The aim of this chapter is to collect under one roof all the mathematical notions from the theory of partially ordered sets and lattices needed to introduce Tarski's classic fixed point theorem. You might think that this detour into some exotic looking mathematics is unwarranted in this textbook. However, we shall then put these possible doubts of yours to rest by using this fixed point theorem to give an alternative definition of strong bisimulation equivalence. This reformulation of the notion of strong bisimulation equivalence is not just mathematically pleasing but also yields an algorithm for computing the largest strong bisimulation over finite labelled transition systems (LTSs), i.e. labelled transition systems with only finitely many states, actions and transitions. This is an illustrative example of how apparently very abstract mathematical notions turn out to have algorithmic content and, possibly unexpected, applications in computer science. As you will see, we shall also put Tarski's fixed point theorem to good use in Chapter 6, where the theory developed in this chapter will allow us to understand the meaning of recursively defined properties of reactive systems.

Posets and complete lattices

We start our technical developments in this chapter by introducing the notion of a partially ordered set (also known as a poset) and some useful classes of such structures that will find application in what follows. As you will see, many examples of posets that we shall mention in this chapter are familiar.

In this chapter we will have a close look at the elegant timed process algebra TCCS introduced by Yi (1990, 1991a, b). Syntactically, TCCS extends CCS with just a single construct, a new prefix ε(d).P that means ‘delay d units of time and then behave as P’. As is the case for a number of other timed process algebras, TCCS takes the view that a real-time system has a two-phase behaviour, phases when the system idles while time passes and phases when the system performs atomic actions, assumed to be instantaneous in time. As we shall see, this separation of concerns – together with other design decisions (e.g. so-called time determinism and maximal progress) – makes for a very elegant TCCS semantics.

Intuition

All the types of reactive system mentioned in Chapter 8 should give us sufficient motivation to describe and analyze formally real-time reactive computations. In the first part of the book, we introduced a collection of languages and models based on the flexible and intuitive idea of communicating state machines, and we argued, by means of several examples, that the resulting formalisms can be used to describe and analyze non-trivial reactive systems. When real-time constraints become important to the proper functioning of reactive systems, we should like to continue building on the time-honoured formalisms we have introduced previously. But are those formalisms sufficiently powerful to describe timing constraints in computation? Can we use them to specify, for instance, features such as timeouts?

Abstract

This chapter reviews the application of Description Logics to software engineering, following a steady evolution of DL-based systems used to support the program understanding process for programmers involved in software maintenance.

Introduction

One of the first large applications of Description Logics was in the area of software engineering. In software, programmers and maintainers of large systems are plagued with information overload. These systems are typically over a million lines of code, some approach fifty million. The size of the workforce dedicated to maintaining these enormous systems is often over a thousand. In addition, turnover is quite high, as is the training investment required to make someone a productive member of the team. This seems, on the surface, to be a problem crying out for a knowledge-based solution, but understanding precisely how Description Logics can play a role requires understanding the basic problems of software engineering “in the large”.

Background

The three principal software maintenance tasks are pro-active (testing), reactive (debugging), and enhancement. Central to effective performance of these tasks is understanding the software. In the 1980s, cognitive studies of programmers involved in program understanding [Soloway et al., 1987] revealed two things:

1. Programmers typically solve problems by realizing “plans” in their programs. This seems to tie the notion of program understanding to plan recognition [Soloway et al., 1986].

2. Delocalized plans (plans which are not implemented in localized regions of code) are a serious impediment to plan recognition, for both humans and automated methods [Soloway and Letovsky, 1986].

Abstract

Description Logics are used to solve a wide variety of problems, with configuration applications being some of the largest and longest-lived. There is concrete, commercial evidence that shows that DL-based configurators have been successfully fielded for over a decade. Additionally, it appears that configuration applications have a number of characteristics that make them well-suited to DL-based solutions. This chapter will introduce the problem of configuration, describe some requirements of configuration applications that make them candidates for DL-based solutions, show examples of these requirements in a configuration example, and introduce the largest and longest-lived family of DL-based configurators.

Introduction

In order to solve a configuration problem, a configurator (human or machine) must find a set of components that fit together to solve the problem specification. Typically, that means the answer will be a parts list that contains a set of components that work together and that the system comprising the components meets the specification. This task can be relatively simple, such as choosing stereo components in order to create a home stereo system. The problem can also be extremely complex, such as choosing the thousands of components that must work together in order to build complicated telecommunications equipment such as cross-connect devices or switches.

One important factor that makes configuration challenging is that making a choice for one component typically generates constraints on other components as well. For example, a customer who chooses a receiver that only supports up to four speakers may not conveniently support a surround sound system with a subwoofer (since this would require more than four speakers).

Abstract

This chapter discusses implemented DL systems that have played or play an important role in the field. It first presents several earlier systems that, although not based on Description Logics, have provided important ideas. These systems include Kl-One, Krypton, Nikl, and Kandor. Then, successor systems are described by classifying them along the characteristics discussed in the previous chapters, addressing the following systems: Classic (“almost” complete, fast); Back, Loom (expressive, incomplete); Kris, Crack (expressive, complete). Finally, a new optimized generation of very expressive but sound and complete DL systems is also introduced. In particular, we focus on the systems Dlp, Fact, and Racer and explain what they can and cannot do.

New light through old windows?

In this chapter a description of the goals behind the development of different DL systems is given from a historical perspective. The description of DL systems allows important insights into the development of the knowledge representation research field as a whole. The design decisions behind the well-known systems which we discuss in this chapter not only reflect the trends in different knowledge representation research areas but also characterize the point of view on knowledge representation that different researchers advocate. The chapter discusses general capabilities of the systems and gives an analysis of the main language features and design decisions behind system architectures. The analysis of current systems in the light of a historical perspective might lead to new ideas for the development of even more powerful DL systems in the future.