Shared Flashcard Set

Details

COMP3017 - Lecture 4 (B) - Relational Algebra
COMP3017 - Lecture 4 (B) - Relational Algebra
31
Computer Science
Undergraduate 2
05/01/2014

Additional Computer Science Flashcards

 


 

Cards

Term
Give an example of a Relation
Definition

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>}

Term
What is the nomeclature of a relational model?
Definition
  • 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 
Term
What are some properties of relations?
Definition
  • 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
Term
What is the definition of Relational Algebra?
Definition
  • 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
Term
Why use Relational Algebra?
Definition
  • 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
Term
What is the seleciton or destriction operator?
Definition
σpredicate(R)
  • 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
Term
Give an example of selection relational function
Definition
[image]
Term
What are some main characteristics of Predicates?
Definition
  • 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
Term
What does projection consist of in Relational Models?
Definition
  • 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
    • pia1,...,an(R)
    • piA, A={a,...,an}

 

Term
Give an example of a projection
Definition
[image]
Term
What are the characteristics of the renaming operator?
Definition
pa'/a(R)
  • 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
 
Term
Give an example of the renaming operator
Definition
[image]
Term
What do complex operations consist of?
Definition

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 <--

 

pifname,lname(osalary>4000(Staff))

ExpensiveStaff <-- osalary>4000(Staff)

Result <-- pifname,lname(ExpensiveStaff)

Term
What is the Set Union operation?
Definition
R U S
  • 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)

 

Term
Give an example of a Union
Definition
[image]
Term
What does the set difference consist of?
Definition
R - S
  • 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)
Term
Give an example of a set difference
Definition
[image]
Term
What are the characteristics of set intersection?
Definition
R ∩ S
  • 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)
Term
Give an example of intersection
Definition
[image]
Term
What is the cartesian product
Definition
R x S
  • 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 = (a,b)
S = (1,2,3)
R x S = ((a,1),(a,2),(a,3),(b1),(b2),(b3))
Term
What is a theta join?
Definition

R|><|F S = oF(R x S)

 

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

 

[image]

 

Term
What are join predicates?
Definition

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 {<, =<, =, >=, >, ~=}

 

Term
What are equijoins and natural joins?
Definition
  • 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
Term
What is an outer join?
Definition
R><|S = R U (R|><|S)
  • 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
Term
What are the variations of the Outer join?
Definition
  • 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)
Term
Give an example of a full outer join
Definition
[image]
Term
What does the semijoin consist of?
Definition

R|>FS = piA(R|><|FS)

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

Term
What are the characteristics of division?
Definition

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

Term
Give an example mapping SQL into Relational Algebra
Definition
[image]
Term
What are some relational transformations?
Definition
  • opΛqΛr(R) = op(oq(or(R)))
  • piLpiM...piN(R) = piL(R)
  • pi(o(R)) = o(pi(R))
  • R|><|pS = S|><|R
  • R x S = S x R
  • op(R|><|pS) = op(R)|><|p op(S)
Term
Draw the diagram for query processing and point out where relational algebra takes place
Definition
[image]
Supporting users have an ad free experience!