Dependencies in Relational Databases

We attempt a more rigorous definition of the relational database model based on /THAL 88/ as it was originally introduced by E.F. Codd /CODD 70/ using the theory of abstract data types /REI 84/ and especially the approach of /PDGG 88/, /VOSS 87/ and /DEAB 85/. The underlying concept used in the relational model is the same as that used to define a mathematical relation (in set theory and algebra). Simply, a relation is a subset of the Cartesian products of a list of domains, a domain being merely a set of entity values.

Many relational queries can be formulated in terms of expressions whose operands represent relations and whose operators are the relational operations. Codd’s relational algebra is a high-level language in which questions can be put simply and succinctly /CODD 72/. Concepts from relational algebra have been incorporated into the design of several new database query languages, into view conceptions and into the conception of internal database schemata /IMLI 82/. Expressions in relational algebra manipulate tables of information by means of high-level operations such as select, project, and join. In section 2.1. an algebraic language is introduced. The underlying principle in algebraic languages is to consider the information we wanted to select can be expressed in relations obtained by successive application of database operators. In chapter 2.3, we consider the algebraic dependencies as an important application of the algebraic language.

This chapter deals with the relationship between logic and relational database theory. The aim of the chapter is to show, by many results published in the literature, how logic can provide a formal support to study classic database problems, and in some cases, how logic can go further, helping first in their comprehension, and then their solution. Logic is just a formal system; many other formal systems have been proposed and applied to databases. In the axiomatic approach, a formal system relies upon an object language, semantics or interpretation of formulas in that language and a proof theory.

Dependencies constitute an inherent property of database systems. They express the different ways that data are associated with each other and therefore, the semantics in relational database schemata. Functional dependence is an important property of a relation. In a relation which verifies some functional dependency, there is a functional connection between the parts of tuples. Functional dependencies can be defined like functions f: X --> Y which are mappings satisfying the conditions:

The decomposition of a relation in a relational database management system is a central issue that has been extensively studied during the last decennium. There are many reasons for decomposing a relation. The most important seem to be

The next dependency we will discuss is neither uni-relational nor many-sorted. A great deal of research has gone into understanding single relations, whether they are designed properly. Much less is known about how the relations should fit together. In general, an inclusion dependency (IND) is of the form where R and S are predicates (or relation scheme names), and the A₁’s and B₁’s are attributes of the corresponding schemes. The inclusion dependency holds for a database if each tuple that is a member of the relation corresponding to the left-hand side is also in the relation corresponding to the right-hand side. Hence, IND’s are valuable for database design, since they permit us to selectively define what data must be duplicated in what relations. IND’s, together with FD’s, are perhaps the most important integrity constraints for relational databases. Although IND’s have been extensively utilized for databases, they only recently were subject of theoretical investigations. Their expressive power is not utilized yet. They could, for instance, play a more important role in management of distributed databases (replication).

In many database applications, the knowledge of the real world modeled by the database is incomplete. A lot of research has been devoted to the problem of querying these so-called incomplete databases. In any real-world database, there will be entries having values that are “special”, in the sense that they are not drawn from the value set for that entry. Some of such special values are of the meaning “value unknown”, “item inapplicable”, “value exists but cannot be stored”, “value is not complete classified” etc. (14 different types of null values are well known /ANSI 75/).

In the study of the relational database model, the vertical decomposition of relations into projections of these relations was emphasized since the introduction in /CODD 72/. The use of vertical decompositions always requires some constraints to be satisfied, for instance a join dependency or a functional dependency, in order to be able to regain the original relation by taking the join of its projections. In /ARDE 80/, /THAL 84/ and AABM 80/ the idea of D. Smith and J. Smith /SMSM 77/, to decompose a relation horizontally into restrictions of these relations, using the union as composition operator, was formalized, using Codd-functional and multivalued dependencies. Such horizontal decompositions /DBPA 83/ are useful in the normalization of schemata in which hidden constraints are involved.

In the previous chapters, more than 80 different dependency classes are introduced and considered. In /THAL 86/, more than 600 different references to papers on dependency theory are given. By some authors it was noticed that dependency theory is in a chaotic state. This book should be understood as an attempt to present the most important results on dependency theory. The usefulness of such a great number of different constraints is an open problem. But the variety can be explained as follows: