Databases Reference
In-Depth Information
In fact, it has been shown how relational DBs can be seen as special
theories of first-order logic [4]. Thus, they could be interpreted as deductive
DBs. By carrying out this logical reconstruction, it is possible to formally
validate query evaluation or update processing algorithms, which is hard to
address in the context of relational DBs.
This chapter provides an overview of the main features of deductive
DBs and illustrates the main problems encountered when dealing with inten-
sional information. Our presentation is based on giving an intuitive idea of
those problems and providing several examples. For that reason, we some-
times omit certain details that are not possible to cover without a more for-
mal explanation. There are various places where these details can be found.
Several topics are devoted, entirely or in part, to deductive DBs [1, 515].
We also provide references to relevant papers when presenting problems not
sufficiently addressed by those topics.
Section 4.2 defines basic concepts of deductive DBs and compares
them to relational DBs. Section 4.3 presents the main approaches to query
processing. Section 4.4 describes the main problems present in update proc-
essing and the main achievements in this area. Section 4.5 examines the main
functionalities provided by existing prototypes of deductive DBs.
4.2
Basic Concepts of Deductive Databases
This section presents the basic notions needed to understand the problems
behind deductive DBs. More precisely, it provides a formal definition of
deductive DBs, a brief overview of their semantics, a discussion of the advan-
tages provided by the intensional information and a comparison of the
expressive powers of relational and deductive DBs. The language used to
define deductive DBs is usually called Datalog. For that reason, deductive
DBs are sometimes known as Datalog programs.
4.2.1
Definition of a Deductive Database
A deductive DB consists of three finite sets: a set of facts, a set of deductive
rules, and a set of integrity constraints. Facts state basic information that is
known to be true in the DB. Deductive rules allow the derivation of new
facts from other facts stored in the DB. Integrity constraints correspond to
conditions that each state of the DB should satisfy.
To formally define those concepts, we need to introduce the follow-
ing terminology. A term is either a variable or a constant. If P is a predicate
