Relational Algebra and Calculus Flashcards

Unary Relational Operations: SELECT and PROJECT

• SELECT Operation:

  • Extracts a subset of tuples from a relation that satisfies a specified selection condition.
  • The selection condition is a Boolean expression containing clauses of the form:
    • <attribute name> <comparison op> <constant value>
    • <attribute name> <comparison op> <attribute name>
  • The <selection condition> is applied independently to each individual tuple t in relation R.
  • A tuple is selected if the condition evaluates to TRUE.
  • Boolean conditions can use AND, OR, and NOT operators to create complex selection criteria.
  • Unary operation, applied to a single relation.
  • Defined by the symbol \sigma.

• Selectivity:

  • Represents the fraction of tuples selected by a selection condition.

• Commutativity:

  • The SELECT operation is commutative.

• Cascading:

  • Multiple SELECT operations can be cascaded into a single operation using the AND condition.

The PROJECT Operation

• Function:

  • Selects specific columns from a table, discarding the other columns.

• Degree:

  • Refers to the number of attributes in the <attribute list>.

• Duplicate Elimination:

  • The result of a PROJECT operation is a set of distinct tuples; duplicates are eliminated.

• Symbol:

  • Represented by the symbol \pi.

Sequences of Operations and the RENAME Operation

• In-line Expression:

  • Allows combining multiple operations into a single expression.

• Sequence of Operations:

  • A series of relational algebra operations performed in a specific order.

• RENAME Operation:

  • Used to rename attributes in intermediate results.

Relational Algebra Operations from Set Theory

• Operations:

  • UNION, INTERSECTION, and MINUS.
  • Merge elements of two sets in various ways.
  • Binary operations, requiring relations to have the same type of tuples.

• UNION (R \cup S):

  • Includes all tuples that are in R, in S, or in both.
  • Duplicate tuples are eliminated.

• INTERSECTION (R \cap S):

  • Includes all tuples that are present in both R and S.

• SET DIFFERENCE (or MINUS) (R – S):

  • Includes all tuples that are in R but not in S.

The CARTESIAN PRODUCT (CROSS PRODUCT) Operation

• Description:
  • Also known as CROSS PRODUCT or CROSS JOIN.
  • Denoted by \times.
  • Binary set operation; relations do not need to be union compatible.
  • Useful when followed by a selection that matches values of attributes.

Binary Relational Operations: JOIN and DIVISION

• The JOIN Operation:

  • Denoted by \Join.
  • Combines related tuples from two relations into single “longer” tuples.
  • General join condition:
    • <condition> AND <condition> AND ... AND <condition>

• Natural Join:

  • Allows the combination of relations that are associated by a Foreign Key.

• THETA JOIN:

  • Each <condition> is of the form Ai \theta Bj, where:
    • A is an attribute of R.
    • B is an attribute of S.
    • A and B have the same domain.
    • \theta (theta) is one of the comparison operators: {=,
  • The result consists of all combinations of tuples in R and S that satisfy the relation \theta.

• EQUIJOIN:

  • A special case of the THETA JOIN where the operator \theta is the equality operator (=).
  • Always has one or more pairs of attributes with identical values in every tuple (e.g., Foreign Key).

• Join Selectivity:

  • The expected size of the join result divided by the maximum size nR * nS.

• Inner Joins:

  • A type of match and combine operation.
  • Formally defined as a combination of CARTESIAN PRODUCT and SELECTION.

A Complete Set of Relational Algebra Operations

• The set {\sigma, \pi, \cup, \rho, –, \times} is a complete set.
• Any relational algebra operation can be expressed as a sequence of operations from this set.

The DIVISION Operation

• Denoted by:

  • \div

• Application:

  • Apply to relations R(Z) \div S(X). Attributes of R are a subset of the attributes of S.
  • The result consists of the restrictions of tuples in R to the attribute names unique to R, i.e., in the header of R but not in the header of S.

• Simulation:

  • Can be simulated with the basic operations {\sigma, \pi, \cup, \rho, –, \times}.

Operations of Relational Algebra

Selection ($\sigma$)

Projection ($\pi$)

Union ($\cup$)

Intersection ($\cap$)

Difference (-)

Cartesian product ($\times$)

Join ($\Join$)

*Division ($\div$)

Notation for Query Trees

• Query Tree (or Query Evaluation Tree):
  • A tree data structure that corresponds to the relational algebra expression.
  • Represents the input relations of the query as leaf nodes of the tree.
  • Represents the relational algebra operations as internal nodes.
  • Execution terminates when the root node is executed.

Additional Relational Operations

• Generalized Projection:

  • Allows functions of attributes to be included in the projection list.

• Aggregate Functions and Grouping:

  • Common functions applied to collections of numeric values.
  • Include SUM, AVERAGE, MAXIMUM, and MINIMUM.
  • Group tuples by the value of some of their attributes.
  • Apply aggregate functions independently to each group.

Recursive Closure Operations

• Operation applied to a recursive relationship between tuples of the same type.

OUTER JOIN Operations

• Outer Joins:
  • Keep all tuples in R, or all those in S, or all those in both relations regardless of whether or not they have matching tuples in the other relation
  • Types:
    • LEFT OUTER JOIN
    • RIGHT OUTER JOIN
    • FULL OUTER JOIN

The OUTER UNION Operation

• Take the union of tuples from two relations that have some common attributes
• Not union (type) compatible - Partially compatible
• All tuples from both relations are included in the result
• Tuples with the same value combination will appear only once

The Tuple Relational Calculus

• Declarative Expression:

  • Specifies a retrieval request nonprocedurally.
  • Any retrieval that can be specified in basic relational algebra can also be specified in relational calculus.

• Tuple Variables:

  • Range over a particular database relation.
  • Satisfy COND(t):
    • Specify the range relation R of t.
    • Select particular combinations of tuples.
    • Define the set of attributes to be retrieved (requested attributes).

• Expressions and Formulas:

  • General expression form:
    • {t | COND(t)}
  • Truth value of an atom:
    • Evaluates to either TRUE or FALSE for a specific combination of tuples.
  • Formula (Boolean condition):
    • Made up of one or more atoms connected via logical operators AND, OR, and NOT.

• Existential and Universal Quantifiers:

  • Universal quantifier: \forall
  • Existential quantifier: \exists
  • Define a tuple variable in a formula as free or bound.

• Transforming Quantifiers:

  • Transform one type of quantifier into the other with negation (preceded by NOT).
  • AND and OR replace one another.
  • Negated formula becomes unnegated, and vice versa.

• Safe Expressions:

  • Guaranteed to yield a finite number of tuples as its result; otherwise, the expression is called unsafe.
  • An expression is safe if all values in its result are from the domain of the expression.

The Domain Relational Calculus

• Differs from tuple calculus in the type of variables used in formulas.
• Variables range over single values from domains of attributes.
• A formula is made up of atoms that evaluate to either TRUE or FALSE for a specific set of values. These are called the truth values of the atoms.
• QBE language:
  • Based on domain relational calculus.