Relational algebra (RA) can be viewed as ...

• mathematical system for manipulating relations, or
• data manipulation language (DML) for the relational model

Relational algebra consists of:

• operands: relations, or variables representing relations
• operators that map relations to relations
• rules for combining operands/operators into expressions
• rules for evaluating such expressions

RA can be viewed as the "machine language" for RDBMSs

Core relational algebra operations:

• selection: choosing a subset of rows
• projection: choosing a subset of columns
• product, join: combining relations
• union, intersection, difference: combining relations
• rename: change names of relations/attributes

Common extensions include:

• aggregation, projection++, division

Select, project, join provide a powerful set of operations for constructing relations and extracting relevant data from them.

Adding set operations and renaming makes RA complete.

Standard treatments of relational algebra use Greek symbols.

We use the following notation (because it is easier to reproduce):

Operation		Standard Notation		Our Notation
Selection		σexpr(Rel)		Sel[expr](Rel)
Projection		πA,B,C(Rel)		Proj[A,B,C](Rel)
Join		Rel1 expr Rel2		Rel1  Join[expr]  Rel2
Rename		ρschemaRel		Rename[schema](Rel)

For other operations (e.g. set operations) we adopt the standard notation.

We define the semantics of RA operations using

• regular "conditional set" expressions   e.g. { X | condition }

  (tuple relational calculus ... cf. Haskell list comprehensions)

• tuple notations:
  • t[AB]   (extracts attributes A and B from tuple t)
  • (x,y,z)   (enumerated tuples; specify attribute values)
• quantifiers, set operations, boolean operators

All RA operators return a result relation (no DB updates).

For convenience, we can name a result and use it later.

E.g.

Temp = R op1 S op2 T
Res  = Temp op3 Z
-- which is equivalent to
Res  = (R op1 S op2 T) op3 Z

Each "intermediate result" has a well-defined schema.

Example database #0 to demonstrate RA operators:

Example database #1 to demonstrate RA operators:

Example database #2 to demonstrate RA operators:

Selection returns a subset of the tuples in a relation r that satisfy a specified condition C.

C is a boolean expression on attributes in R.

Result size:   |σ_C(r)| ≤ |r|

Result schema:   same as the schema of r   (i.e. R)

Programmer's view:

result = {}
for each tuple t in relation r
    if (C(t)) { result = result ∪ {t} }

Example selections:

Example queries:

• Find details about the Perryridge branch?
  • Sel [branchName=Perryridge] (Branch)
• Which accounts are overdrawn?
  • Sel [balance<0] (Account)
• Which Round Hill accounts are overdrawn?
  • Sel [branchName=Round Hill ∧ balance<0] (Account)

Projection returns a set of tuples containing a subset of the attributes in the original relation.

X specifies a subset of the attributes of R.

Note that removing key attributes can produce duplicates.

In RA, duplicates are removed from the result set.
(In many RDBMS's, duplicates are retained   (i.e. they use bag, not set, semantics))

Result size:   |π_X(r)| ≤ |r|     Result schema:   R'(X)

Programmer's view:

result = {}
for each tuple t in relation r
    result = result ∪ {t[X]}

Example projections:

Example queries:

Proj [branchName] (Branch)

Which branches actually hold accounts?

• Proj [branchName] (Account)

What are the names and addresses of all customers?

• Proj [name,address] (Customer)

Generate a list of all the account numbers

• Proj [accountNo] (Account)    or
• Proj [account] (Depositor)    (if we assume every account has a depositor)

Union combines two compatible relations into a single relation via set union of sets of tuples.

Compatibility = both relations have the same schema

Result size:   |r₁ ∪ r₂|   ≤   |r₁| + |r₂|     Result schema: R

Programmer's view:

result = r1
for each tuple t in relation r2
    result = result ∪ {t}

Example queries:

• Which suburbs have either customers or branches?
  • Proj[address](Customer) ∪ Proj[address](Branch)
• Which branches have either customers or accounts?
  • Proj[homeBranch](Customer) ∪ Proj[branchName](Account)

The union operator is symmetric i.e.   R ∪ S   =   S ∪ R.

Intersection combines two compatible relations into a single relation via set intersection of sets of tuples.

Uses same notion of relation compatibility as union.

Result size:   |r₁ ∪ r₂|   ≤   min(|r₁|,|r₂|)     Result schema: R

Programmer's view:

result = {}
for each tuple t in relation r1
    if (t ∈ r2) { result = result ∪ {t} }

Example queries:

• Which suburbs have both customers and branches?
  • Proj[address](Customer) ∩ Proj[address](Branch)
• Which branches have both customers and accounts?
  • Proj[homeBranch](Customer) ∩ Proj[branchName](Account)

The intersection operator is symmetric i.e.   R ∩ S   =   S ∩ R.

Difference finds the set of tuples that exist in one relation but do not occur in a second compatible relation.

Uses same notion of relation compatibility as union.

Note: tuples in r₂ but not r₁ do not appear in the result

i.e. set difference != complement of set intersection Programmer's view:

result = {}
for each tuple t in relation r1
    if (!(t ∈ r2)) { result = result ∪ {t} }

Example difference:

 

Clearly, difference is not symmetric.

Example queries:

• Which customers have no accounts?
  • AllCusts = Proj[customerNo](Customer)
    CustsWithAccts = Proj[customer](Depositor)
    Result = AllCusts - CustsWithAccts
• Which branches have no customers?
  • AllBranches = Proj[branchName](Branch)
    BranchesWithCusts = Proj[homeBranch](Customer)
    Result = AllBranches - BranchesWithCusts

Product (Cartesian product) combines information from two relations pairwise on tuples.

Each tuple in the result contains all attributes from r and s, possibly with some fields renamed to avoid ambiguity.

If t₁ = (A₁...A_n) and t₂ = (B₁...B_n) then (t₁:t₂) = (A₁...A_n,B₁...B_n)

Note: relations do not have to be union-compatible.

Result size is large:   |r × s| = |r|.|s|     Schema: R∪S

Programmer's view:

result = {}
for each tuple t1 in relation r
    for each tuple t2 in relation s
        result = result ∪ {(t1:t2)} }

Example product #1:

Example product #2:

By itself, product isn't a useful querying mechanism.

However, it gives a basis for combining information across relations.

A special (and very common) usage of product:

• form all possible pairs in r × s
• select just the "interesting" pairs   (matching key values)

This usage is represented by a separate operation: join.

Note: join is not implemented using product   (which is why RDBMSs work)

Join is critically important in implementing "navigation" in relational databases.

Example query #1:

• Who are the owners of account A101?
  • combine information from Customer and Depositor
  • tmp1 = Customer × Depositor
    tmp2 = Sel [account=A101] (tmp1)
    tmp3 = Sel [customer=customerNo] (tmp2)
    res   = Proj [name] (tmp3)

Example query #2:

• Which accounts are held in branches in Horseneck or Brooklyn?
  • combine information from Account and Branch
  • tmp1 = Account × Branch
    tmp2 = Sel [B.address = Horseneck] (tmp1)
    tmp3 = Sel [B.address = Brooklyn] (tmp1)
    tmp4 = tmp2 ∪ tmp3
    tmp5 = Sel [A.branchName = B.branchName] (tmp4)
    res   = Proj [A.accountNo] (tmp5)

Example query #3:

• Which customers hold accounts at a Brooklyn branch?
  • need to combine information from all relations
  • tmp1 = Account × Branch × Customer × Depositor
    tmp2 = Sel [B.address = Brooklyn] (tmp1)
    tmp3 = Sel [B.branchName = A.branchName] (tmp2)
    tmp4 = Sel [A.accountNo = account] (tmp3)
    tmp5 = Sel [C.customerNo = A.customer] (tmp4)
    res   = Proj [C.name] (tmp5)

Rename provides "schema mapping".

If expression E returns a relation R(A₁, A₂, ... A_n), then

gives a relation called S

• containing the same set of tuples as E
• but with the name of each attribute changed from A_i to B_i

Rename is like the identity function on the contents of a relation; it changes only the schema.

Rename can be viewed as a "technical" apparatus of RA.

Examples:

Natural join is a specialised product:

• containing only pairs that match on their common attributes
• with one of each pair of common attributes eliminated

Consider relation schemas R(ABC..JKLM), S(KLMN..XYZ).

The natural join of relations r(R) and s(S) is defined as:

Programmer's view:

result = {}
for each tuple t1 in relation r
   for each tuple t2 in relation s
      if (matches(t1,t2))
         result = result ∪ {combine(t1,t2)}

Natural join can also be defined in terms of other relational algebra operations:

We assume that the union on attributes eliminates duplicates.

If we wish to join relations, where the common attributes have different names, we rename the attributes first.

E.g. R(ABC) and S(DEF) can be joined by

Note: |r s| |r × s|, so join not implemented via product.

Example (assuming that A and F are the common attributes):

Strictly, the operation above was: r1 Join Rename[r2(E,A,G)](r2)

Natural join is not quite the same as:

Compare this to the previous result:

As above, we assume   Rename[Marks(sid,subj,mark)](Marks)

Example queries:

• Who is the owner of account A101?
  • Proj[name](Sel[account=A101](Customer Depositor))
• Which accounts are held in branches in Horseneck?
  • tmp1 = Sel[address=Horseneck](Account Branch)
    res   = Proj[accountNo](tmp1))
• Which customers hold accounts at a Brooklyn branch?
  • tmp1 = Account Branch Customer Depositor
    res   = Proj[name](Sel[address=Brooklyn](tmp1))

The theta join is a specialised product containing only pairs that match on a supplied condition C.

Examples:   (r1 Join[B>E] r2) ... (r1 Join[E<D∧C=G] r2)

Can be defined in terms of other RA operations:

Unlike natural join, "duplicate" attributes are not removed.

Note that   r _true s   =   r × s.

Example theta join:

(Theta join is an important component of most SQL queries; many examples of its use to follow)

Comparison between join operations:

• theta join allows arbitrary tests in the condition
  (and leaves all attributes from the original relations in the result)
• equijoin has only equality tests in the condition
  (and leaves all attributes from the original relations in the result)
• natural join has only equality tests on common attributes
  (and removes one of each pair of matching attributes)

Equijoin is a specialised theta join; natural join is like theta join followed by projection.

r Join s eliminates all s tuples that do not match some r tuple.

Sometimes, we wish to keep this information, so outer join

• includes all tuples from each relation in the result
• for pairs of matching tuples, concatenate attributes as for standard join
• for tuples that have no match, assign null to "unmatched" attributes

Example (assuming that A and F are the common attributes):

Contrast this to the result for R Join S presented earlier.

Another outer join example (compare to earlier similar join):

There are three variations of outer join R OuterJoin S:

• left outer join (LeftOuterJoin) includes all tuples from R
• right outer join (RightOuterJoin) includes all tuples from S
• full outer join (OuterJoin) includes all tuples from R and S

Which one to use depends on the application e.g.

If we want to know about all Students, regardless of whether they're enrolled in anything

Operational description of r(R) LeftOuterJoin s(S):

result = {}
for each tuple t1 in relation r
   nmatches = 0
   for each tuple t2 in relation s
      if (matches(t1,t2))
         result = result ∪ {combine(t1,t2)}
         nmatches++
   if (nmatches == 0)
      result = result ∪
                 {combine(t1,Snull)}

where S_null is a tuple from S with all atributes set to NULL.

Consider two relation schemas R and S where S ⊂ R.

The division operation is defined on instances r(R), s(S) as:

Operationally:

• consider each subset of tuples in R that match on t[R-S]
• for this subset of tuples, take the t[S] values from each
• if this covers all tuples in S, then include t[R-S] in the result

Example:

Division handles queries that include the notion "for all".

E.g. Which customers have accounts at all branches?

We can answer this as follows:

• generate a relation of customers and branches where they hold accounts
• generate a relation of all branch names
• find which customers appear in tuples with every branch name

RA operations for answering the query:

• customers and branches where they hold accounts
  • r1 = Account Branch Customer Depositor
    r2 = Proj [name,branchName] (r1)
• branch names
  • r3 = Proj[branchName](Branch)
• customers who appear in tuples with every branch name
  • res   = r2 Div r3

Example of answering the query (in a different database instance):

Division can be implemented in terms of other RA operations.

Consider R/S where R = X ∪ Y and S = Y ...

T = Proj[X](R)		generate all potential result tuples
U = T × S		combine potential results with all tuples from S
V = U - R		find any combined tuples that are not in R; any potential results which occur with all S values in R will be removed; V thus contains potential result tuples which do not occur with all S values in R
W = Proj[X](V)		the X parts of these tuples are "disqualified"
Res = T - W		so remove them to produce the result

Two types of aggregation are common in database queries:

• accumulating summary values for data in tables
  • typical operations Sum, Average, Count
  • many operations work on a single column
    (e.g. Sum[assets](Branch))
• grouping sets of tuples with common values
  • GroupBy[A₁...A_n](R)
  • typically we group using only a single attribute

Example aggregations:

In standard projection, we select values of specified attributes.

In generalised projection we perform some computation on the attribute value before placing it in the result tuple.

Examples:

• Display branch assets in Aus$ rather than US$.
  • Proj [branchname,address,assets*0.75] (Branch)
• Display employee records using age rather than birthday.
  • Proj [id,name,(today-birthdate)/365,salary] (Employee)