Foundations of Knowledge Systems

with Applications to Databases and Agents

Gerd Wagner

Kluwer Academic Publishers, Boston/Dordrecht/London

(available from Amazon)

Contents

Preface

In order to design and understand database and knowledge-based applications it is important to build upon well-established conceptual and mathematical foundations. What are the principles behind database and knowledge systems ? What are their major components ? Which are the important cases of knowledge systems ? What are their limitations ? Addressing these questions, and discussing the fundamental issues of information update, knowledge assimilation, integrity maintenance, and inference-based query answering, is the purpose of this book.

Databases, Logic and SQL

Various Kinds of Information

The book presents a comprehensive framework for the conceptual integration and uniform treatment of all these types of information. This includes the definition of generic knowledge system models capable to handle fuzzy, temporal, confidential, and unreliable information.

Various Types of Rules

In addition to information about the current and possible state of affairs in the form of facts and integrity constraints, a knowledge base may also represent terminological and heuristic knowledge in the form of deduction rules. This type of rule is well-known from deductive databases and logic programs. It is shown how the concept of deduction rules can be applied to the various kinds of information that have to be processed in practical knowledge systems, leading to such powerful concepts like temporal and fuzzy deduction rules. Typically, the semantics of these rules involves nonmonotonic inference on the basis of the Closed-World Assumption.

Reaction rules can be used to specify the reactive behavior of a knowledge base when it receives messages, either from the external world, or from other nodes of a network it participates in. This concerns, in particular, the communication and cooperation taking place in multidatabases and between cooperative knowledge bases.

How to Use this Book

Introduction

The Success of Database Systems

Only through the formal conceptualization of relational databases by Codd in the early seventies it became possible to overcome the inadequacy of the database technology  prevailing at that time. Only the logic-based formal concepts of the relational database model have led to more cognitive adequacy, and have thus constituted the conceptual basis for further progress (towards object-relational, temporal, deductive, etc. databases). Unlike much of theoretical computer science, Codd's theory of relational databases is an example of a practical theory.
 

The Difficulties of `Expert Systems'

One may argue that these problems are due to the inherent difficulties of knowledge representation and processing, but it rather seems that the expert system community has failed to establish scientific foundations and has also failed to learn from its neighbor fields of logic programming and deductive databases which have successfully developed a formal concept of rules based on a logical semantics.
 

What is a Knowledge System ?

•  New incoming pieces of information must be assimilated into a knowledge base by means of an update operation. This includes simple insertion of new information, deletion (retraction) of old information, and possibly a number of more involved change operations for assimilating new pieces of information which are in conflict with some already-stored pieces. The update operation should satisfy some principle of minimal mutilation.

• Queries posed to the knowledge base must be answered by means of an inference-based query answering operation. The inference procedure should be complete with respect to some well-understood logic, and  sound with respect to a preferential entailment relation in that logic.

The concept of a knowledge system constitutes a useful framework for the classification and comparison of various computational systems and formalisms like, e.g., relational, temporal and deductive databases. It is more general than that of a logic (i.e. a consequence relation). A standard logic can be viewed as a special kind of knowledge system. On the other hand, by suitably defining the inference and update operations, knowledge systems can serve as the basis for the operational definition of logics.
 

Knowledge Systems and Logic

Logic has provided a model of theory-based reasoning by means of consequence relations, but it has not been concerned with the assimilation of new sentences into a changing theory. For a theory of knowledge systems, however, we need a model of both knowledge-based inference and of knowledge assimilation.
 

About this Book

The theory of knowledge systems presented in this book should be construed as an attempt of a practical theory which aims at establishing solid conceptual foundations and generic models to be used in the software engineering of knowledge and information systems. It is my firm belief, that knowledge systems have to evolve from, and have to be integrated with, database and information system technology. The starting points in this evolution are the  entity-relationship modeling method and the system of relational databases which are presented in Chapter 1 and 2. These and the following chapters on object-relational databases, reaction rules, deduction rules, temporal databases and fuzzy databases are intended for class room use in computer science at the graduate levels. More advanced topics, such as representing negative information using bitables, or elements of a general theory of deduction rules, are covered in the remaining chapters.

The main technical contributions of this book are:

1. a formal model of object-relational databases;
2. a general account of reaction rules in connection with the concept of knowledge- and perception-based agents, originally proposed in (Wagner 1996);
3. a new semantics of deduction rules that is based on stable generated closures and derived from the notion of stable generated models of (Herre and Wagner 1997);
4. a new generalization of database tables, called bitables, for representing negative information in connection with  incomplete predicates (the logical ideas of this generalization have already been presented in (Wagner 1991);
5. a new model of fuzzy and possibilistic databases based on a new compositional definition of possibilistic logic;
6. a new definition of inference-based query answering in multi-level secure (MLS) databases;  and
7. a new model of lineage databases for tracking the lineage and reliability of information items.

The knowledge system concepts proposed in this book have obvious applications in advanced database and in agent-based systems. An agent system needs to include a knowledge system as one of its main components. In particular, the knowledge systems of MLS factbases for protecting confidential information, and of  lineage factbases for tracking and weighting the reliability of different information sources, may be relevant to agent systems. Even more important is the concept of reaction rules that allows the declarative specification of the reactive behavior of agents. This book is for those who want to design knowledge-based agents, and it is for those who want to develop innovative database systems. It can be used both by computer science students and by professionals in computer science and other fields with some background in logic to obtain organized access to many advanced concepts in the theory of databases and knowledge representation.

Those sections that are primarily of interest to logic-oriented readers are indicated with "pure logic" next to the section head. Additional non-classical logic background, not required for understanding the book, is provided in the appendix as an option for the logic-oriented reader to gain deeper insights into the connections between knowledge systems and logic.

This is probably the first book to cover such a broad range of diverse database and knowledge systems. Necessarily, not all relevant questions are addressed and the discussion of certain advanced topics may be incomplete, biased, or even erroneous. As a human with limited resources, I may have overlooked important issues and ignored important related work I should have mentioned. I apologize for this and promise to do my best to provide necessary corrections and supplements on the book's Web page which is http://www.informatik.uni-leipzig.de/~gwagner/ks.html

Notice that this Web page may also contain solutions to exercises and other supplementary material which could not be included in the book.

1 Conceptual Modeling of Knowledge Bases

1.1 Introduction

1.2 Predicate Logic

In predicate logic, all basic entities (or individuals) of a given universe of discourse are conceived of as forming a flat set without any further classification. Normally, but not necessarily, they have names called constant symbols (such as 1,2,3, ..., I, II, III, ..., Venus, 007, `James Bond', etc.). An entity, in predicate logic, may have zero, one or more names. For example, `2', `II' and `two'  denote the same natural number. Likewise, `007' and `James Bond' denote the same person. Properties of, and relationships among, entities are expressed as sentences (or assertions) with the help of predicate symbols. The meaning of a predicate, in standard predicate logic, is given by its extension, i.e. the set of all tuples to which the predicate applies (forming a relation in the sense of set theory).

Notice that in the meta-model of predicate logic, there is no distinction between properties and relationships, both are expressed by predicates. On the other hand, in first order predicate logic, there is a strict distinction between basic entities (denoted by constants), functions and predicates while in natural discourse, both functions and predicates are treated as entities as well. These simplifications made by the predicate calculus do not pose any problem in the domain of mathematics (in fact, they proved to be very fertile). But in other, more empirical, application domains they are cognitively inadequate. For such domains, standard predicate logic is conceptually too flat, i.e. it does not offer sufficient support for those concepts needed to capture the essential semantics of empirical domains.

Therefore, the research discipline of conceptual modeling in computer science had to come up with new meta-models for being able to capture those parts of domain semantics that are relevant for database and knowledge system applications. The most fundamental of these meta-models is the Entity-Relationship Modeling method proposed by Chen (1976).

1.3 Entity-Relationship Modeling

In addition to defining a semi-formal terminology, the ER modeling method assigns visual representations to its concepts. The resulting ER diagrams are a convenient and concise way of expressing an ER model.
 

Entities and Entity Types

Obviously, in an information processing system such as a database or a knowledge system, one does not deal with the entity itself (in the ontological sense) but rather with some representation of it. For linguistic simplicity, however, the term `entity', in ER modeling, is used in its epistemic (representational) sense. Examples of entities are the natural numbers 1,2,3,..., Leo (our dog), James Bond (alias 007), Berlin, the planet Venus, my Alfa Romeo automobile, the 200th birthday of Schubert, the letter `K', or the disease hepatitis A.

Entities of the same type share a number of attributes and attribute functions representing their properties or characteristics. An attribute associates with each entity a stored value from its domain. An attribute function associates with each entity a value to be computed by invoking the function. Together, the values of all attributes of an entity form the state of it. There may be different entities having the same state. In that case, one needs an appropriate naming mechanism for identifying and distinguishing entities independently of their state.

A standard name is a unique identifier assigned to an entity during its entire life cycle. If a primary key is defined for an entity type, it may be used as a standard name for entities of that type. An example of a primary key is the social security number assigned to employees. We assume, however, that entities can be identified independently of the existence of a primary key. How this is achieved need not be defined in the ER meta-model. Whenever an ER model is implemented in some practical knowledge system, there has to be a method to assign standard names to entities such as, e.g., primary keys in relational databases, or object IDs in object-relational databases. In contrast to predicate logic, in the ER meta-model and in database theory, it is commonly assumed that all entities have (standard) names.

There may be certain restrictions on the admissible values for attributes, called integrity constraints. A fundamental type of an integrity constraint is a key dependency, that is a minimal set of attributes whose values identify an entity. A key is a constraint since it implies that there must be no pair of entities of the same type having the same values for their key attributes. One of these key dependencies may be designated as the primary key of the entity type. Natural primary keys, such as social security numbers or flight numbers, are often used to identify entities and to access them in an information system. Sometimes there is no natural primary key, or even no key at all, in the definition of an entity type. It is a matter of implementation, and not of conceptual modeling, how to deal with this situation. In a relational database, an artificial primary key attribute has to be added to maintain entity identity while in an object-relational database an immutable object ID is automatically assigned to an entity on its creation.

In summary, an entity type is defined by a name, a list of attributes with associated domains, a list of attribute functions with associated signatures and implementations, and a possibly empty set of integrity constraints including key dependencies. Notice that an entity type, unlike the set-theoretic notion of a data type, is not a purely extensional concept. There may be two different entity types, say Lecturers and Researchers, with exactly the same list of attributes (and attribute functions) and possibly with the same extension. In contrast, two data type definitions, say ULONG and DWORD, having the same extension are equal, by the axioms of set theory.

At any moment, an entity type defined for a particular knowledge base is associated with its current extension consisting of all entities of that type which are currently represented in the knowledge base. An entity type is like a container, and the associated extension is its content. Thus, an entity type corresponds to a table in a  natural way: the columns of the table correspond to the attributes, a populated table contains the current extension of the entity type, and a table row, forming an attribute value tuple, corresponds to a specific entity.

Entity types are visually represented in the form of a labeled box which may be partitioned into a head and a body part, if the attribute list is to be included in the diagram. In that case, the name of the entity type is written in the head of the box, and the attributes are listed in its body.

The domain of an attribute is either an intensionally or an extensionally defined set of possible values. Typically, an intensional domain is defined by a formal grammar, while an extensional domain is defined by an explicit set of values. Examples of intensional domains are the integers, strings with at most 20 characters, or JPEG pictures. Examples of extensional domains are the names of foreign currencies or the names of colors. An extensional domain of an attribute of some entity type may be defined by the extension of another (single attribute) entity type.

Notice that different entities may belong to different epistemic categories. There are

1. concrete physical objects comprising passive objects (such as the Venus or  my Alfa Romeo), and physically embodied agents (such as the Star Wars robot R2, our dog Leo, or James Bond),
2. software objects (such as the word processor window I am currently writing in)
3. software agents (such as the Microsoft Office97 assistant `Clippit')
4. events (such as the 200th birthday of Schubert, or the mouse click to the beginning of this line),
5. locations (such as Berlin),
6. analytical concepts (such as the natural number 1),
7. empirical concepts (such as the disease hepatitis A),
8. symbols (such as the letter `K').

Relationships and Relationship Types

A relationship between two entities is symbolically represented as an ordered pair labeled with the name of the relationship type. For instance, the expression attends(Kim, Logic1)

represents a relationship of type attends between the entity `Kim' of type Student and the entity `Logic 1' of type Course. Mostly, relationships are binary, like attends, but in some cases three or more entities are related which is represented by corresponding n-tuples.

There are two special relationships between entity types which are independent of the application domain and which are therefore distinguished from domain relationships: subclass and aggregation relationships.

The subtype relationship between abstract data types has to be distinguished from the subclass relationship between entity types. Unlike objects in object-oriented programming, entities are not instances of abstract data types (often called `classes' in OO programming) but of entity types. Recall that an entity type is a named container with an associated abstract data type, namely the tuple type defining the attributes and attribute functions of all entities of that type. There may be several distinct entity types associated with the same abstract data type. A tuple type is a specialization (or a subtype) of another tuple type if it has additional attributes. If an entity type E is a specialization of an entity type D in the sense that every entity of type E is also an entity of type D, then E is called a subclass of D. This implies that every attribute of D is also an attribute of E, and E may have additional attributes (i.e. the data type of E is a subtype of that of D). The subclass relationship between two entity types is sometimes called `isa relationship' because we can say ``E isa D''. For instance, a sales engineer is a sales person, and hence the entity type SalesEngineer is a subclass of SalesPerson. We use the set-theoretic notation E isIncludedInD for expressing a subclass relationship and visualize it by placing a subclass below its superclasses and connect them with simple lines.

In an aggregation relationship, a number of part entities belong exclusively to an aggregate entity and do not exist independently of such an assignment. For instance, Room entities belong to a Building entity, which is expressed as Building HAS Room. An aggregation relationship type is visually represented by drawing the part entity box within the aggregate entity box.

Depending on how many entities from one entity type can be associated with how many entities of another entity type, three kinds of relationship types are distinguished:

• One-to-one: For each entity of either type there is at most one associated entity of the other type.
• Many-to-one from E₁ to E₂: Each entity of type E₂ is associated with zero or more E₁ entities, and each E₁ entity is associated with at most one E₂ entity. A many-to-one relationship from E₁ to E₂ is a (partial) function from E₁ to E₂.
• Many-to-many: each entity of either type is related to zero or more entities of the other type.

Application Domain Predicates

1. the finite set of application domain predicates established by the entity-relationship analysis, and
2. the set of all possible attribute values, i.e. the union of all attribute domains, which forms the set of constant symbols.

ER Modeling Is Object-Oriented

Object-oriented methods often include attempts to model the behavior of a system. Behavior modeling is a significant extension to the ER meta-model. However, the proposed methods, such as Petri nets and state transition diagrams, are not well-integrated with the constructs of state modeling and therefore not satisfactory. Finding a modeling method that integrates both state and behavior is still an open problem.
 

1.4 Identifying Qualified Predicates

• a valid time span during which a predicate is asserted to apply to a tuple,
• a degree of uncertainty with which a property or a relationship holds for an entity,
• a level of security with which the information that a predicate applies to a tuple is classified, or
• an information source according to which a property or relationship holds for an entity (in addition, a certain degree of reliability may be associated with the information source).

Qualified predicates are visualized in an ER diagram by including the qualification as a special attribute at the end of the attribute list separated by a line.
 

1.5 Identifying Incomplete Predicates

There are two kinds of incomplete predicates: total and partial ones. While total predicates may, in principle, be completely represented in a database, partial predicates may not; they are necessarily incomplete. For partial predicates, falsity does not follow from non-truth: if it is not true that the predicate applies to a tuple, this does not already mean that it is therefore false. In general, predicates may have truth-value gaps, and falsity is not equal to non-truth. The classical law of the excluded middle applies only to total predicates no matter if their representation is complete or incomplete. It does not hold for incomplete predicates that are partial.

Incomplete predicates are best explained by partial logic with weak and strong negation. The extension of an incomplete predicate is represented in a bitable consisting of an upper and a lower part. While the upper part contains the truth extension, the lower part contains the falsity extension of the represented incomplete predicate. Thus, bitables allow to store both positive and negative information.

An incomplete predicate is visually represented in an ER diagram by drawing a horizontal line dividing the head of an entity box or of a relationship diamond in an upper and a lower part.

As an example, consider the information system of an organization that wants to record the personal preferences of its employees towards each other by means of a relationship type Likes. The information whether an employee likes or dislikes another employee is obtained by interviews. Obviously, the information collected in this way is incomplete: the employee John need not like or dislike the employee Peter, he may be neutral with respect to Peter. So, it does not follow from John's not liking Peter that he does therefore dislike him. The predicate representing the Like relationship type is incomplete, and, consequently, corresponds to a bitable containing all pairs for which Likes hold, i.e. its truth extension consisting of all pairs  (x,y)  such that x likes y, and, in addition, all pairs for which Likes does definitely not hold, i.e. its falsity extension consisting of all pairs (x,y)  such that x dislikes y.
 

1.6 Identifying Intensional Predicates

Intensional predicates are defined by means of deduction rules consisting of a head (or conclusion) and a body (or premise). They can be used to represent various kinds of relationships between concepts, such as subsumption or synonymy, or to represent properties and relationships based on heuristics and on default assumptions.

In summary, incomplete, qualified and intensional predicates extend the concept of normal predicates and lead to conservative extensions of relational databases. Since these extensions are orthogonal, they form a rather large space of possible combinations.
 
 
 

1.7 Entity-Relationship Modeling in 7 Steps

Step 1: List all potential entity types.

Step 2: Write a summary paragraph for each entity type.

Step 3: Identify relationship types.

Step 4: Determine the epistemic category of all domain predicates.

1. Is it a complete extensional predicate good for absolute assertions ?
2. Is it a qualified predicate such that assertions made with it are informationally correct only relative to some qualification (like a valid-time span, a degree of uncertainty, or a security level) ?
3. Is it an incomplete predicate for which we do not have sufficient information competence in order to guarantee that its complete extension is available ?
4. Is it an intensional predicate whose extension is not explicitly stored in the knowledge base but is derived from other predicates via deduction rules ?

Step 5: Draw an ER diagram.

Step 6: Determine the attributes of entities and relationships.

Step 7: Complete the diagram by deriving additional entity types.

1.8 Agent-Object-Relationship Modeling

ER modeling does not account for the dynamic aspects of information and knowledge processing systems. These aspects are related to notions like communication, interaction, events, activities or processes. As pointed out above, it may be useful to distinguish between different kinds of entity types. In particular, for capturing semantic aspects related to the dynamics of knowledge systems, it is necessary to distinguish between agents and passive objects. While both objects and agents are represented in the system, only agents interact with it, and the possible interactions may have to be represented in the system as well.

Being entities, agents and objects of the same type share a number of attributes representing their properties or characteristics. So, in agent-object-relationship (AOR) modeling, there are the same notions as in ER modeling (such as attribute domain, state, integrity constraint, key, etc.). In fact, objects in AOR modeling are treated exactly like entities in ER modeling.

While ER modeling supports the design of object-oriented  information systems realized with the help of relational and object-relational databases, AOR modeling allows the high-level design of agent-oriented information systems. An agent-oriented information system represents agents and their potential interactions in addition to ordinary objects. It need not be designed as an agent itself, however. Thus, the AOR meta-model is not intended as a methodology for the design of agent-based systems in general but rather of agent-oriented information systems.

Interaction Frames and Agent Roles

Notice that it is a matter of choice whether to represent active entities as agents or as objects. Agents are special objects. One may simply ignore their agent-specific properties and treat them as objects. For instance, if the supplier-to-customer interaction does not have to be explicitly modeled in an enterprise information system. Customers may be simply represented as objects in the same way as orders and bank accounts.

But even if it is not necessary to represent certain agent types in the target system and track their interactions, it may be important to consider them in the conceptual model in order to be able to derive a transaction and process model from the possible interactions with that type of agent. The possible interactions between two agent types (or roles, say between customers and salespersons, or between patients and nurses) are defined by an interaction frame which lists for both participating roles:

1. All types of communication acts that may take place in the agent-to-agent communication frame. Since in the perspective of a `listener', the communication acts of other agents are events, we also speak of communication event types.
2. All relevant types of physical actions which may be performed in response to other actions of (or which are otherwise related to) the interaction frame.
3. All relevant types of environment events which may be perceived by an agent and which are related to the interaction frame.
4. A set of correctness properties defining the correct behavior of agents within the interaction frame. Correctness properties are temporal logic assertions expressing either a safety or a progress property. Typically, these properties refer to communication events (or messages) and possibly to the mental state of agents.

 Mental Attributes

1.9 Summary

1.10 Further Reading

1.11 Exercises

Problem 1-2  Assume that the university is interested in information about its employees being smokers or non-smokers. This information, however, can only be obtained on a voluntary basis.  Extend the university ER model from the previous exercise in an appropriate way.

Problem 1-3  Establish an ER model of the hospital domain consisting of the entity types Person,  Patient,  Room,  Physician, Diagnosis and Treatment. Notice that diagnoses are uncertain and that information about patients (including their diagnoses and treatments) must be associated with a security level to protect it from unauthorized access.
 

2 The Fundamental Case: RELATIONAL DATABASES

After introducing the basic concepts of relational databases, three major components of databases are discussed: queries, integrity constraints and updates. It is shown that query answering is based on logical inference, and that updates are subject to certain logical conditions involving the specified integrity constraints. Then, the problem of null values in databases is presented as a violation of the database completeness assumption. Finally, we present Reiter's database completion theory and discuss the relation of databases to predicate logic model theory.

2.1 Introduction

Already in 1970, Edgar F. Codd published his pioneering article ``A Relational Model of Data for Large Shared Data Banks'' in the Communications of the ACM, where he defined the principles of the relational database model. This was the first convincing conceptualization of a general purpose database model, and it is not an accident that it relies on formal logic.

In the mid-eighties finally, IBM presented its database management system DB2, the first industrial-strength implementation of the relational model, which continues to be one of the most successful systems for mainframe computers today. There are now numerous other relational database management systems that are commercially available. The most popular ones include Informix, Ingres, Oracle, Sybase and Microsoft SQL Server. To a great extent, the overwhelming success of these systems is due to the standardization of the database programming language SQL originally developed at IBM in the seventies. SQL is a declarative language for defining, modifying and querying relational database tables. SQL queries correspond to first order predicate logic formulas.

While most well-established information processing systems and tools such as programming languages, operating systems or word processors have evolved from practical prototypes, the unprecedented success story of the relational database model is one of the rare examples -- certainly the most important one -- where a well-established and widely used major software system is based on a formal model derived from a mathematical theory (in this case set theory and mathematical logic.)

Logically, a relational database is a finite set of finite set-theoretic relations over elementary data types (called tables), corresponding to a finite set of atomic sentences. Such a collection of ground atoms can also be viewed as a finite interpretation of the formal language associated with the database in the sense of first order model theory.

The information represented in a relational database is updated by inserting or deleting atomic sentences corresponding to table rows (or tuples of some set-theoretic relation). Since a relational database is assumed to have complete information about the domain represented in its tables, if-queries are answered either by yes or by no. There is no third type of answer such as unknown. Open queries (with free variables) are answered by returning the set of all answer substitutions satisfying the query formula.
 

2.14 Deficiencies of the Relational Database Model

Besides these general purpose issues, there are several special purpose extensions of relational databases that are required to handle qualifications (such as valid time, security and reliability) and various forms of incompleteness (such as incomplete predicates and disjunctive information).
 

Adequate Support for Standard Names

Complex-Valued Attributes

Attribute Functions

Subclass Hierarchy and Inheritance

User-Defined Types and Large Objects

Reaction Rules

Deduction Rules

Valid Time and Belief Time

Spatial and Geographic Information

Incomplete Predicates

Security

Uncertainty and Reliability

Disjunctive Information

2.15 Summary

3 Object-Relational Databases

Historically, the successful application of object-oriented programming languages such as Smalltalk, C++ and Java, has led to the development of a number of object-oriented  database (OODB) systems which support the storage and manipulation of persistent objects. These systems have been designed as programming tools to facilitate the development of object-oriented application programs. However, although they are called `database systems', their emphasis is not on knowledge representation but rather on persistent object management. Any database concept which is intended as an implementation platform for information systems and knowledge representation must support tables as its basic representation concept on which query answering is based. Tables correspond to extensional predicates, and each table row corresponds to a sentence or proposition. This correspondence is a fundamental requirement for true database systems. If it is violated, like in the case of OODBs, one deals with a new notion of `database system', and it would be less confusing to use another term instead (e.g. `persistent object management system') as proposed by (Kim 1995).

One can view the evolution of relational to object-relational databases in two steps:

1. The addition of abstract data types (ADTs) leads to ADT-relational databases consisting of complex-valued tables. ADTs include user-defined base types and complex types together with user-defined functions and type predicates, and the possibility to form a type hierarchy where a subtype of a tuple type inherits all attributes defined for it.
2. The addition of object identity, object references and the possibility to define subtables within an extensional subclass hierarchy results in object-relational databases consisting of complex-valued tables and object tables.

1. Object IDs in ORDBs are logical  pointers. They are not bound to a physical location (like C++ pointers).
2. In addition to the intensional subtype hierarchy of the type system, ORDBs have an extensional subclass (or subtable) hierarchy that respects the subtype relationships defined in their type system.

7 Temporal Databases

8 Fuzzy Databases

8.1 Introduction

Classical probability theory, based on the axioms of Kolmogorov, on the other hand, makes very strong assumptions. In many practical cases, it is therefore not applicable to the problem of handling uncertain information. Also, probabilistic methods are computationally much more costly than fuzzy methods because they are non-compositional.

Imprecise information often comes in the form of disjunctive or vague sentences, while uncertain information is often expressed in the form of sentences qualified by a degree of uncertainty like, for instance, `very likely' or `with 60% certainty'. Sometimes, such a qualification is called a subjective probability or a degree of belief. A particular form of uncertainty is given by statistical information.  Sentences qualified by statistical uncertainty are based on statistical samples measuring relative frequencies. An example of such a sentence is "80% of all jaundice patients have hepatitis". Through their empirical grounding, these sentences are more reliable than sentences qualified by a mere subjective degree of belief.

In the literature, there is no clear taxonomy of uncertainty in databases and knowledge bases. An obvious distinction, however, concerns the uncertainty expressed at the level of attribute values, or at the level of the applicability of a predicate to a tuple. While the former is related to the issue of handling vagueness, the latter is related to an account of certainty-qualified sentences. In our formal exposition, we do not treat vagueness expressed by fuzzy-set-valued attributes, but only the more fundamental issue of gradual uncertainty based on fuzzy relations over ordinary (`crisp') attributes.