The relation schema TRANSCRIPT has three attributes:

• StudentID
• CourseCode
• Mark

The domains of these attributes are respectively

• The set of integers
• The set of module codes {COMP1001, ...,COMP6031}
• The set of integers in the range 0...10

A particular relation T of the relation schema TRANSCRIPT could be:

T = { <1, COMP2004, 77>, <2,COMP2004,76>,<3,COMP1008,44>,<2,COMP1008,66>}

• A relation can be viewed as a table with columns and rows
• An attribute is a named column of a relation
• A domain is the set of allowable values for an attribute
• A tuple is a row of a relation (ordered collection of values)
• The degree of a relation is the number of attributes it contains
• The cardinality of a relation is the number of tuples it contains
• A relation schema is defined by a set of attributes and domain name pairs 

• Each relation in a relational database schema has a distinct name
• Each attribute of each tuple in a relation contains a single atomic value
• Each attribute has a distinct name
• The values of an attribute are all from the same domain
• Each tuple is distinct; there are no duplicate tuples
• The order of the attributes in a tuple is significant
• The order of the tuples in a relation is insignificant

• A theoretical language which defines operations that allow us to construct new relations from other relations
• Both operands and the results of the operations are relations
• Operations:
• Selection, projection, renaming
• Union, intersection, set difference
• Cartesian product
• Join (theta, natural, equi-, couter, semi-)
• Division

• Allows us to analyse the behaviour of complex queries in terms of fundamental operations
• More efficient queries
• More efficient database systems
• A given SQL query may correspond to a number of different relational algebra expressions (query trees)
• Intermediate relations may have different sizes
• Cost of evaluation may vary
• Basis for query optimization

• A unary operation on a relation R that defines a relation which contains only those tuples of R that satisfy the predicate
• Selection extracts rows from a table

• Atomic predicates can take two forms:
• a0b
• a0v
• a, b are attribute names,
• 0 is a binary operator from the set {=<,<,=,>,=>}
• Predicates can be combined with the logical operators: ~,and,or

• A unary operation on a relation R which defines a relation (a vertical subset of R) containing the specified attributes
• Projection extracts columns from a table
• pi_a1,...,an(R)
• pi_A, A={a,...,an}

• A unary operator on a relation R which renames the attributes of R
• The rename specificatin is written as new name/old name
• Remaining does not change the shape of a table

We can combine the relational algebra operations to build expressions of arbitrary complexity

For the sake of legibility, we can name intermediate expressions using the assignment operator <--

pi_fname,lname(o_salary>4000(Staff))

ExpensiveStaff <-- o_salary>4000(Staff)

Result <-- pi_fname,lname(ExpensiveStaff)

• The union of two relations R and S contains all the tupples of R and S (eliminating duplicates)
• R and S must have compatible schemas (same number of attributes, with the same domains)

• The set difference of two relations R and S contains all the tupples in R which are not in S.
• R and S must have compatible schemas (same number of attributes, with the same number of domains)

• The intersection of two relations contains all the tuples that are in both relations
• R and S must have compatible schemas (same number of attrinbutes with the same number of domains)

• This contains the concatenation of every tuple in R with every tuple in S for two relations R and S.
• R and S need not to have compatible schemas

R_|><|F S = o_F(R x S)

Contains the tuples from the cartesian product of the two relations which satisfy the predicate F

[image]

Used in joins, and are of the form:

R.a 0 S.b

where a and b are attributes of R and S respectively and 0 is one of {<, =<, =, >=, >, ~=}

• The former is a theta join in which the only predicate operator is used equality (=)
• A natural join is an equijoin over all the common attributes of the joined relations; one occurrance of each common attribute is removed form the resulting relation

• The (left) outer join of two relations R and S is a join which also indlucdes tuples from R which do not have corresponding tuples in S; missing values are set to null

• Left outer join: R_><|S = R U (R_|><|S)
• Right outer join: R_|><S = S U (R_|><|S)
• R_><S = R U S U (R_|><|S)

R_|>FS = pi_A(R_|><|FS)

Contains all tuples of R which are in the join of R and S with predicate F

R÷S

Given two relations R, and S, with attribute sets A and B, where B is a subset of A, the division of R by S is the set of tuples form R that match every tuple in S

• o_pΛqΛr(R) = o_p(o_q(o_r(R)))
• pi_Lpi_M...pi_N(R) = pi_L(R)
• pi(o(R)) = o(pi(R))
• R_|><|pS = S_|><|R
• R x S = S x R
• o_p(R_|><|pS) = o_p(R)|><|p o_p(S)