zbMATH — the first resource for mathematics

Constraint algebras. (English) Zbl 0962.68050
Kuper, Gabriel (ed.) et al., Constraint databases. Berlin: Springer. 335-342 (2000).
Summary: Algebra-calculus equivalence is a fundamental property of the relational model. A calculus query is first converted into an equivalent algebraic query, which is then optimized and evaluated. As we have seen if we consider unrestricted databases, the classical equivalence between the algebra and the calculus carries over easily. Furthermore, all the algebraic operations described previously can be effectively evaluated over constraint databases, and that the data complexity bounds discussed in Chapter 4 also apply to the algebra.
For practical purposes, however, data complexity is an oversimplification, that hides many significant factors. In this chapter we therefore study how better algebras can be designed for specific constraint domains, making use of specific characteristics of the constraints in question.
We study two languages: FO\((<)\), and a subclass of \(\text{FO}+ \text{LIN}\) known as monotone two-variable linear constraints. For these languages, we see that there is a representation of the relations so that projection can be implemented in the same way as in the relational model. This means that one implements a projection by simply deleting those constraints that involve the variables that are projected out, rather than by using a general purpose quantifier elimination algorithm.
For the entire collection see [Zbl 0935.00022].
68P15 Database theory
68P05 Data structures