Slide 6 - Relational Algebra V2

• Relational Query Languages use Relational Algebra with basic relational operators.

Relational Algebra

• Based on Set Theory
• Operators used to access relations to retrieve and manipulate tuples
• Operators can be nested for complex operations
• Input is one or more relations with an output relation
• Uses composition in operations

Basic Operations

• Select (σ): Chooses a subset of tuples from the input relation based on a condition
• Projection (π): Removes unwanted columns from the input relation
• Cross-product (X): Combines all possible tuple pairs from two input relations
• Set-difference (-): Yields tuples that exist in the first relation but not the second
• Union (U): Combines tuples from two input relations into a single output table
• Renaming (p): Changes the name of an attribute or a table

Example Relational Database Schema

• Includes different schemas
• Students(sid: string, name: string, login: string, age: integer, gpa: real)
• Courses(cid: string, cname: string, credits: integer)
• Enrolled(sid: string, cid: string, grade: string)
• Instructor(iid: string, iname: string, irank: string, isalary: real)
• Teaches(iid: string, cid: string, year: integer, semester: string)

Project Operator (π)

• The project operator: attribute list (Table)
• Tuples are points in the multi-dimensional space
• Each attribute corresponds to one dimension
• Projection retains listed attributes and eliminates unlisted ones
• Can result in duplicate tuples if a “key” attribute isn't contained in the projection list
• Eliminating the duplicate output tuples may be expensive
• projection of schema (X,Y,Z) into Schema (X,Y), two projected tuples become the same

Select Operator (σ)

• The Select Operator: predicate (Table)
• Takes input predicate and table names and produces rows that satisfy the predicate
• Same schema as the input

Cross Product (X)

• Table1 X Table2 produces all possible combinations of tuple pairs
• Output schema is a combination of the schemas of the two input tables
• Number of output tuples is the table1 x table2
• Example Courses x Enrolled with concatenated of the schema
• Courses(cid: string, cname: string, credits: integer)
• Enrolled(sid: string, cid: string, grade: string)

Union (U)

• Gives two tables with compatible schemas
• Must have: same number of attributes AND same data type per matched attribute pairs
• Eliminates duplicates
• WL_Enrolled(sid: string, cid: string, grade: string) + Calumet_Enrolled(sid: string, cid: string, grade: string)
• WL_Enrolled U Calumet_Enrolled

Set Difference (-)

• Table 1 and Table 2 are compatible schemas
• Must contain the same number of attributes and the same data type per matched attribute pairs
• Produces tuples in the first table that aren't in the second table
• WL_Enrolled(sid: string, cid: string, grade: string) - Calumet_Enrolled(sid: string, cid: string, grade: string)
• WL_Enrolled - Calumet_Enrolled
• Note that set difference is not commutative

Renaming (p)

• Assigns a name to the result of a relational algebra expression
• Returns expression E under the name X, attributes renamed to A1, A2, ..., An

Composition of Operators

• Can find the names of students with a GPA of 4.0, using π name(σgpa=4.0(Students))
• First selects the tuples with gpa=4.0, then project the name

Additional Relational Algebra Operators

• Non-basic operations can be realized by composing multiple basic operations
• Relational Algebra is closed under the relational operators
• Includes intersection, join, and division operators

Intersect

• Uses two relations with compatible schemas to find the common tuples in both input relations
• Can be realized using basic relational algebra operators
• r n s = r - (r - s)

Join

• Natural join
• Equi-join
• Theta-join

Natural Join

• Finds equality of all the common attributes between tables
• Output Schema = R U S Schemas of r and s
• Example: Courses <Natural Join> Enrolled
• Common attribute is: cid

Equi-Join

• Output Schema = Same as schema of R XS
• Contains an equality predicate with one attribute from each table R and S
• Join is based on equality of the join predicate (r.a = s.b)

Theta-Join

• Output Schema = Same as schema of RXS
• Contains a general predicate (0 comparator) with at least one attribute from each table R and S

Division

• Finds the tuples in a relation (r) that join with all the tuples in relation (s)
• RNS ≠ Ø
• Find the students who enrolled in all courses, or instructors who taught all database courses
• Table r (sid, cid), Table S (cid)
• Schema of r ÷ s = (sid)
• The division operator is realized by basic relational algebra operators

Extended Relational-Algebra Operations

• Include Aggregate Functions and Operations as well as Outer Join

Aggregate Functions and Operations

• Applies to Groups
• Takes a relation (or a relational algebra expression that produces a relation)
• Can contain an optional list of grouping attributes G1, G2, ..., Gn
• Aggregate functions F1, F2, ..., Fn take input from a certain attribute (A1, A2, ..., An) from the input relation, and produce a scalar value as output.
• Example functions are count, sum, avg, min, and max
• Example statement would be to compute average gpa of students grouped by age: Age gby avg(gpa)(students)

Outer Join

• Computes the join regularly but adds the tuples from one relation that do not join with null values
• Include Left outer-join, Right outer-join, and Full outer-join

Modifying Underlying Relations

• Uses insert, delete, and update functions
• Assume E is some Relational Algebra expression that returns a table containing one constant tuple
• Deletes tuples from a relation r: r ← r - E
• Inserts tuples into a relation r: r ← r U E
• Updates a value inside one attribute in a tuple in a relation r ← ∏ F1, F2, ..., FI (r)
  • Set Fi = Ai for the attributes you do not want to change their values
  • For the attribute Aj that you want to update, Fj = new value, Plugging in Aj's place the new value
  • May depend on the old value (e.g., old value + Constant, A1+A2, or Constant2)

Relational Algebra and SQL

• Select: SELECT * FROM r WHERE r.id = 123 AND r.a ='a';
• Project: Select r.a, r.b+100 FROM r
• Union: (SELECT * FROM r) UNION (SELECT * FROM s);
• Set Difference: (SELECT * FROM r) EXCEPT (SELECT * FROM s);
• Cross Product: SELECT * FROM r, s; SELECT * FROM r CROSS JOIN s;
• Rename: Select cid as CourseID into Table1 FROM Courses;
• Intersect: (SELECT * FROM r) INTERSECT (SELECT * FROM s);
• Join: Select * from r, s where r.a = s.b;

SQL Evaluation

• Conceptual evaluation by Relational Algebra operations: πA1,A2, ..., An (σP1 and P2 and ... and Pk (T1X T2 X ... XTm))