Introduction to Relational Calculus
by K. Yue
1. Introduction
-
Non-procedural, declarative, and high level.
-
Two kinds:
- Domain Relational Calculus
(DRC)
- Tuple Relational Calculus (TRC)
- Results specified by the set builder form: {s | cond(s)}
- cond(s) is known as a formula.
- Constructs:
- Variables:
- TRC: tuples (bound to tuples): e.g. s, t, student, class, etc.
- DRC: Attributes (bound to domain value): e.g. a, b, c, stuId, firstName, etc.
- The variable is sometime known as 'dummy variable'.
- Constants: string, int, etc., E.g. 12, 'csci', 3.7.
- Comparison operators: <, <, =, etc.
- Boolean operators: and (conjunction, ∧ or just ,), or (disjunction ∨), not (¬), implies (⇒), etc.
- Membership functions: belongs to, ε, not belongs to, ∉, etc.
- Quantifiers: there exists (existential, ∃), for all (universal ∀).
- An atom can be thought of as a simple Boolean expression:
- e ∈ R, or
- x op y where x and y are attributes or constants, and op is a comparison operation.
- A formula is either an atom or formula connected by Boolean operator or qualifiers.
- A formula that is not an atom can be thought of a compound Boolean expression.
- A variable is bound if it appears in qualifier expressions. Otherwise, it is a free variable.
- Free variables can only appear in the LHS of |.
- All RA expressions can be expressed in RC.
- RA and RC have the same expressive power.
- Any query language that can express all RA is known to be relational complete.
- Relational Calculus expressions need to be safe: results should be a finite set of tuples.
- Care should be taken especially for the negation operation. E.g. {s |¬ (s ∈ Student) } is unsafe.
- For a given implementation of relational calculus:
- There may be restricted of supported constructs.
- There may be certain canonical requirements: e.g. conjunction (joined by the and operator) of disjunction (joined by the or operator).
Example:
{i | i ∈ I ∧ i % 2 =0}
{i | i ∈ I, i % 2 =0} -- set builder form.
{t | ∃r ∈R, r.firstname = t.firstname, r.lastname = t.lastname}
- t is a free variable.
- It will have two attributes: t.firstname and t.lastname.
Alternatively, we can use the set builder form in the LHS before |:
{(r.firstname, r.lastname) | r ∈ R}
R(A,B,C,D) / S(C,D)
{(a,b) | (∀(c,d) ∈ S) (a,b,c,d) ∈ R)}
Exercises:
How do you use RC to implement RA operations?
2. TRC
- The variables in TRC are tuples.
- SQL is based on TRC.
3. DRC
- The variables in DRC are attributes (domain values).
- Query By Example (QBE) is based on DRC.
Exercise:
Work on some of the query questions listed in the toyu Query Exercise in DRC and TRC.