Bruger:Pkj61/Relationel algebra

Relationel algebra er en tilpasning/udvidelse af logisk algebra og læren om relationer inden for mængdelæren. Disciplinen har til formål inden for datalogi at danne et teoretisk grundlag for opbygningen af relationelle databaser og blev først introduceret af Edgar F. Codd i 1970. Relationel algebra danner grundlag for opbygningen af programmeringssprog til relationelle databaser som f.eks. SQL

Primitive relationelle operationer

De primitive operationer i relationel algebra bygger på tilsvarende operationer i logisk algebra.

As in any algebra, some operators are primitive and the others are derived in terms of the primitive ones. It is useful if the choice of primitive operators parallels the usual choice of primitive logical operators. Although it is well knownSkabelon:By whom that the usual choice in logic of AND, OR and NOT is somewhat arbitrary^{[kilde mangler]}, Codd made a similar arbitrary choice for his algebra.

Five primitive operators of Codd's algebra are the selection, the projection, the Cartesian product (also called the cross product or cross join), the set union, and the set difference. Another operator, rename was not noted by Codd, but the need for it is shown by the inventors of ISBL. These six operators are fundamental in the sense that if you omit any one of them, you will lose expressive power. Many other operators have been defined in terms of these six. Among the most important are set intersection, division, and the natural join. In fact ISBL made a compelling case for replacing the Cartesian product with the natural join, of which the Cartesian product is a degenerate case.

Altogether, the operators of relational algebra have identical expressive power to that of domain relational calculus or tuple relational calculus. However, for the reasons given in section Introduction, relational algebra is less expressive than first-order predicate calculus without function symbols. Relational algebra corresponds to a subset of first-order logic, namely Horn clauses without recursion and negation.

Set operators

Although three of the six basic operators are taken from set theory, there are additional constraints that are present in their relational algebra counterparts: For set union and set difference, the two relations involved must be union-compatible—that is, the two relations must have the same set of attributes. Because set intersection can be defined in terms of set difference, the two relations involved in set intersection must also be union-compatible.

The Cartesian product is defined differently from the one in set theory in the sense that tuples are considered to be 'shallow' for the purposes of the operation. That is, the Cartesian product of an n-tuple by an m-tuple has the 2-tuple "flattened" into an (n + m)-tuple. In set theory, the Cartesian product is a set of 2-tuples. More formally, R × S is defined as follows:

R × S = {(r₁, r₂, ..., r_n, s₁, s₂, ..., s_m) | (r₁, r₂, ..., r_n) ∈ R, (s₁, s₂, ..., s_m) ∈ S}

Like the Cartesian product, the cardinality of the result is the product of the cardinalities of its factors, i.e., |R × S| = |R| × |S|. In addition, for the Cartesian product to be defined, the two relations involved must have disjoint headers—that is, they must not have a common attribute name.

Projection (π)

Hovedartikel: Projection (relational algebra).

A projection is a unary operation written as $\pi _{a_{1},\ldots ,a_{n}}(R)$ where $a_{1},\ldots ,a_{n}$ is a set of attribute names. The result of such projection is defined as the set that is obtained when all tuples in R are restricted to the set $\{a_{1},\ldots ,a_{n}\}$.

This specifies the specific subset of columns (attributes of each tuple) to be retrieved. To obtain the names and phone numbers from an address book, the projection might be written $\pi _{contactName,contactPhoneNumber}(addressBook)$. The result of that projection would be a relation which contains only the contactName and contactPhoneNumber attributes for each unique entry in addressBook.

Selection (σ)

Hovedartikel: Selection (relational algebra).

A generalized selection is a unary operation written as $\sigma _{\varphi }(R)$ where $\varphi$ is a propositional formula that consists of atoms as allowed in the normal selection and the logical operators $\land$ (and), $\lor$ (or) and $\lnot$ (negation). This selection selects all those tuples in R for which $\varphi$ holds.

To obtain a listing of all friends or business associates in an address book, the selection might be written as $\sigma _{isFriend=true\lor isBusinessContact=true}(addressBook)$. The result would be a relation containing every attribute of every unique record where isFriend is true or where isBusinessContact is true.

Rename (ρ)

Hovedartikel: Rename (relational algebra).

A rename is a unary operation written as $\rho _{a/b}(R)$ where the result is identical to R except that the b attribute in all tuples is renamed to an a attribute. This is simply used to rename the attribute of a relation or the relation itself.

To rename the 'isFriend' attribute to 'isBusinessContact' in a relation, $\rho _{isBusinessContact/isFriend}(addressBook)$ might be used.