Relational algebra

In database theory, relational algebra is a theory that uses algebraic structures for modeling data and defining queries on it with well founded semantics.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 10 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In database theory, relational algebra is a theory that uses algebraic structures for modeling data and defining queries on it with well founded semantics. The theory was introduced by Edgar F. Codd as part of his relational model of data in 1970.

The main application of relational algebra is to provide a theoretical foundation for relational databases, particularly query languages for such databases, chief among which is SQL. Relational databases store tabular data represented as relations. Queries over relational databases often likewise return tabular data represented as relations.

The main purpose of relational algebra is to define operators that transform one or more input relations to an output relation. Given that these operators accept relations as input and produce relations as output, they can be combined and used to express complex queries that transform multiple input relations (whose data are stored in the database) into a single output relation (the query results).

Unary operators accept a single relation as input. Examples include operators to filter certain attributes (columns) or tuples (rows) from an input relation. Binary operators accept two relations as input and combine them into a single output relation.…

In database theory, relational algebra is a theory that uses algebraic structures for modeling data and defining queries on it with well founded semantics. The theory was introduced by Edgar F. Codd as part of his relational model of data in 1970.

The main application of relational algebra is to provide a theoretical foundation for relational databases, particularly query languages for such databases, chief among which is SQL. Relational databases store tabular data represented as relations. Queries over relational databases often likewise return tabular data represented as relations.

The main purpose of relational algebra is to define operators that transform one or more input relations to an output relation. Given that these operators accept relations as input and produce relations as output, they can be combined and used to express complex queries that transform multiple input relations (whose data are stored in the database) into a single output relation (the query results).

Unary operators accept a single relation as input. Examples include operators to filter certain attributes (columns) or tuples (rows) from an input relation. Binary operators accept two relations as input and combine them into a single output relation.

For example, taking all tuples found in either relation (union), removing tuples from the first relation found in the second relation (difference), extending the tuples of the first relation with tuples in the second relation matching certain conditions, and so forth. A relation of arity is a set of tuples.

Relational algebra operates on homogeneous sets of tuples, S = \{(s_{j1},s_{j2}, ... s_{jn}) \mid j \in 1 ... m \}, where an tuple is a tuple (row; index ) with (or data domains), thus is the number of rows of tuples in a table and is the number of columns (and all entries in each column have the same ). A relation also has a unique tuple called the header which gives each column a unique name or attribute inside the relation.

Attributes are used in projections and selections. \sigma_{\text{isFriend = true} \,\lor\, \text{isBusinessContact = true}}( \text{addressBook} ). The result would be a relation containing every attribute of every unique record where is true or where is true.

A selection is written as \sigma_{a \theta b}( R ) or \sigma_{a \theta v}( R ) where: and are attribute names is a binary operation in the set \{\; \} is a value constant is a relation The selection \sigma_{a \theta b}( R ) denotes all tuples in for which holds between the and the attribute. The selection \sigma_{a \theta v}( R ) denotes all tuples in for which holds between the attribute and the value .

For an example, consider the following tables where the first table gives the relation , the second table gives the result of \sigma_{\text{Age} \ge 34}( \text{Person} ) and the third table gives the result of \sigma_{\text{Age} = \text{Weight}}( \text{Person} ) . | | |} More formally the semantics of the selection is defined as follows: \sigma_{a \theta b}( R ) = \{\ t : t \in R,\ t(a) \ \theta \ t(b) \ \} \sigma_{a \theta v}( R ) = \{\ t : t \in R,\ t(a) \ \theta \ v \ \} The result of the selection is only defined if the attribute names that it mentions are in the heading of the relation that it operates upon.

Generalized selection

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

For an example, consider the following tables where the first table gives the relation and the second the result of \sigma_{\text{Age} \ge 30 \ \land \ \text{Weight} \le 60}(\text{Person}) . | |} Formally the semantics of the generalized selection is defined as follows: \sigma_\varphi(R) = \{ \ t : t \in R, \ \varphi(t) \ \} The result of the selection is only defined if the attribute names that it mentions are in the header of the relation that it operates upon. The generalized selection is expressible with other basic algebraic operations.

A simulation of generalized selection using the fundamental operators is defined by the following rules: \sigma_{\varphi \land \psi}(R) = \sigma_\varphi(R) \cap \sigma_\psi(R) \sigma_{\varphi \lor \psi}(R) = \sigma_\varphi(R) \cup \sigma_\psi(R) \sigma_{\lnot \varphi}(R) = R - \sigma_\varphi(R)

Computer languages

In computer languages it is expected that any truth-valued expression be permitted as the selection condition rather than restricting it to be a simple comparison. In SQL, selections are performed by using WHERE definitions in SELECT , UPDATE , and DELETE statements, but note that the selection condition can result in any of three truth values (true, false and unknown) instead of the usual two.

In SQL, general selections are performed by using WHERE definitions with AND , OR , or NOT operands in SELECT , UPDATE , and DELETE statements. \rho_{a/b}(R) = \{ \ t[a/b] : t \in R \ \}, where t[a/b] is defined as the tuple , with the attribute renamed to , so that: t[a/b] = \{ \ (c, v) \ | \ ( c, v ) \in t, \ c \ne b \ \} \cup \{ \ (a, \ t(b) ) \ \}. (R \bowtie S) \cup ((R - \pi_{r_1, r_2, \dots, r_n}(R \bowtie S)) \times \{(\omega, \dots, \omega)\}) (R \bowtie S) \cup (\{(\omega, \dots, \omega)\} \times (S - \pi_{s_1, s_2, \dots, s_n}(R \bowtie S))) R ⟗ S = (R ⟕ S) ∪ (R ⟖ S) There is nothing in relational algebra introduced so far that would allow computations on the data domains (other than evaluation of propositional expressions involving equality).

For example, it is not possible using only the algebra introduced so far to write an expression that would multiply the numbers from two columns, e.g. a unit price with a quantity to obtain a total price. Practical query languages have such facilities, e.g. the SQL SELECT allows arithmetic operations to define new columns in the result SELECT unit_price * quantity AS total_price FROM t , and a similar facility is provided more explicitly by Tutorial D's EXTEND keyword.

In database theory, this is called extended projection. \sigma_{A}(R)=\sigma_{A}\sigma_{A}(R)\,\! \sigma_{A}\sigma_{B}(R)=\sigma_{B}\sigma_{A}(R)\,\! \sigma_{A \land B}(R)=\sigma_{A}(\sigma_{B}(R))=\sigma_{B}(\sigma_{A}(R)) \sigma_{A \lor B}(R)=\sigma_{A}(R)\cup\sigma_{B}(R) In the above case the condition A is broken up in to conditions B, C and D using the split rules about complex selection conditions, so that A = B \wedge C \wedge D and B contains attributes only from R, C contains attributes only from P, and D contains the part of A that contains attributes from both R and P. Note, that B, C or D are possibly empty. Then the following holds: \sigma_{A}(R \times P) = \sigma_{B \wedge C \wedge D}(R \times P) = \sigma_{D}(\sigma_{B}(R) \times \sigma_{C}(P)) \sigma_{A}(R\setminus P)=\sigma_{A}(R)\setminus \sigma_{A}(P) =\sigma_{A}(R)\setminus P \sigma_{A}(R\cup P)=\sigma_{A}(R)\cup\sigma_{A}(P) \sigma_{A}(R\cap P)=\sigma_{A}(R)\cap\sigma_{A}(P)=\sigma_{A}(R)\cap P=R\cap \sigma_{A}(P) \pi_{a_1, \ldots ,a_n}(\sigma_A( R )) = \sigma_A(\pi_{a_1, \ldots,a_n}( R ))\,\,\text{if}\,A \subseteq \{a_1,\ldots,a_n\} \begin{align}&\pi_{a_1, \ldots , a_n}(\pi_{b_1,\ldots , b_m}(R)) = \pi_{a_1, \ldots , a_n}(R)\\[4pt] &\,\,\,\text{where}\,\,\{a_1, \ldots , a_n\} \subseteq \{b_1, \ldots , b_m\}\end{align} \pi_{a_1, \ldots, a_n}(R \cup P) = \pi_{a_1, \ldots, a_n}(R) \cup \pi_{a_1, \ldots, a_n}(P). \, Projection does not distribute over intersection and set difference.

Counterexamples are given by: \begin{align} \pi_A(\{ \langle A=a, B=b \rangle \} \cap \{ \langle A=a, B=b' \rangle \}) &= \emptyset \\ \pi_A(\{ \langle A=a, B=b \rangle \}) \cap \pi_A(\{ \langle A=a, B=b' \rangle \}) &= \{ \langle A=a \rangle \} \end{align} and \begin{align} \pi_A(\{ \langle A=a, B=b \rangle \} \setminus \{ \langle A=a, B=b' \rangle \}) &= \{ \langle A=a\rangle \} \\ \pi_A(\{ \langle A=a, B=b \rangle \}) \setminus \pi_A(\{ \langle A=a, B=b' \rangle \}) &= \emptyset \end{align} where is assumed to be distinct from . \rho_{a / b}(\rho_{b / c}(R)) = \rho_{a / c}(R)\,\! \rho_{a / b}(\rho_{c / d}(R)) = \rho_{c / d}(\rho_{a / b}(R))\,\! \rho_{a / b}(R \setminus P) = \rho_{a / b}(R) \setminus \rho_{a / b}(P) \rho_{a / b}(R \cup P) = \rho_{a / b}(R) \cup \rho_{a / b}(P) \rho_{a / b}(R \cap P) = \rho_{a / b}(R) \cap \rho_{a / b}(P) (A \times B) \cup (A \times C) = A \times (B \cup C) Even the query language of SQL is loosely based on a relational algebra, though the operands in SQL (tables) are not exactly relations and several useful theorems about the relational algebra do not hold in the SQL counterpart (arguably to the detriment of optimisers and/or users). The SQL table model is a bag (multiset), rather than a set.

For example, the expression (R \cup S) \setminus T = (R \setminus T) \cup (S \setminus T) is a theorem for relational algebra on sets, but not for relational algebra on bags.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378658866 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

7 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.