Relational Model
RELATIONAL ALGEBRA
(CONTINUED)
Copyright By PowCoder代写 加微信 powcoder
“Relational” Mathematics
A mathematical basis is a great way to formally express the myriad of requests we may want to make
Operations from Algebra and Set Theory
Complete Set: The set of operations including
PROJECT ,
INTERSECTION
DIFFERENCE – ,
CARTESIAN PRODUCT X
Any other relational algebra expression can be expressed by a combination of these five operations.
R S = (R S ) – ((R – S) (S – R))
R
Nested application of SELECT operations
Is SELECT Commutative?
Cascading of the SELECT operation may be applied in any order:
The PROJECT Operation – (pi)
Selects columns from table and discards the other columns:
Eliminates duplicates
Result of PROJECT operation is a set of distinct tuples
Project each employee’s first, last name, and salary:
LNAME, FNAME,SALARY(EMPLOYEE)
RENAME Operation – (rho)
In-line expression:
Sequence of operations:
Rename attributes
Rename tables
Name intermediate results
UNION, INTERSECTION, and MINUS
Merge the elements of two sets in various ways
Binary operations
Relations must have the same type of tuples
Relational Algebra Operations
from Set Theory
Includes all tuples in either R, or S, or in both R and S
INTERSECTION
Includes all tuples that are in both R and S
SET DIFFERENCE (or MINUS)
Includes all tuples in R but not in S
UNION, INTERSECT, and SET DIFFERENCE
STUDENT INSTRUCTOR
STUDENT INSTRUCTOR
STUDENT – INSTRUCTOR
INSTRUCTOR – STUDENT
UNION, INTERSECT, and SET DIFFERENCE
Both union and intersection are commutative operations:
R S = S R, and R S = S R
Both union and intersection can be treated as n-ary operations
as both are associative operations
R (S T) = (R S) T
(R S) T = R (S T)
The minus operation is not commutative
R – S ≠ S – R
Join information between 2 or more tables
Binary operators
Cross Product – X
The CARTESIAN operation – X
CROSS PRODUCT or CROSS JOIN
Combine tuples from two relations in a combinatorial fashion, i.e. an exhaustive pairing of tuples
Q = R(A1, A2, . . ., An) x S(B1, B2, . . ., Bm)
Relation Q has degree n + m attributes:
Q(A1, A2, . . ., An, B1, B2, . . ., Bm), in that order.
The two operands do NOT have to be “type compatible”
When is this operation useful?
FEMALE_EMPS SEX=’F’(EMPLOYEE)
EMPNAMES FNAME, LNAME, SSN (FEMALE_EMPS)
EMP_DEPENDENTS EMPNAMES x DEPENDENT
ACTUAL_DEPS SSN=ESSN(EMP_DEPENDENTS)
RESULT FNAME, LNAME, DEPENDENT_NAME (ACTUAL_DEPS)
contains every combination
The JOIN Operation
Denoted by
Combine related tuples from two relations
General join condition of the form
Variations of JOIN
THETA JOIN
Any comparison operator used
Always have one or more pairs of attributes that have identical values in every tuple
Only = comparison operator used
Always have one or more pairs of attributes that have identical values in every tuple
NATURAL JOIN
Denoted by *
Removes second (superfluous) attribute in an EQUIJOIN condition
Inner joins
Type of match and combine operation
Defined formally as a combination of CARTESIAN PRODUCT and SELECTION
THETA JOIN Operation
R S
can be any general boolean expression on the attributes of R and S
Each term of relates a tuple from R with a tuple from S using any {<, , >, , =, }
In practice, is constructed with just one or more equality conditions “AND”ed together:
R.Ai = S.Bj AND R.Ak = S.Bl AND R.Ap = S.Bq
Each attribute pair is called a join attribute
Tuples with NULL or FALSE Condition match are not selected
Retrieve the name of the manager of each department
Combine each DEPARTMENT tuple with the EMPLOYEE tuple whose SSN value matches the MGRSSN value in the department tuple.
DEPT_MGR DEPARTMENT MGRSSN = SSN EMPLOYEE
NATURAL JOIN Operator
A simplification of an Equijoin joins join attributes with the same name
Q R(A,B,C,D) * S(C,D,E)
The implicit join condition is
R.C = S.C AND R.D = S.D
Resulting relation Q(A, B, C, D, E)
List information about each department including its location
Combine DEPARTMENT with DEPT_LOCATIONS
DEPT_LOCS DEPARTMENT * DEPT_LOCATIONS
Use EQUIJOIN
Fname, Lname (EMPLOYEE Dno DNnumber ( Dlocation ‘ ’(DEPT_LOCATIONS)))
Use NATURAL Join
Fname, Lname (EMPLOYEE * (Dno, Dlocation) ( Dlocation ‘ ’(DEPT_LOCATIONS)))
Find the full names of employees who work in
Joins – Binary Operations
Name Notation Notes
Cross-Product R X S Combines all tuples and attributes of R, S
Useful when followed by selection
Join R
Theta-Join R S can be any general boolean expression on the attributes of R and S
Each term of relates a tuple from R with a tuple from S using any {<, , >, , =, }
Equi-Join R S
R.Ai = S.Bj AND
R.Ak = S.Bl AND
R.Ap = S.Bq Combines all attributes of R, S
Constructed with = as the only comparison operator
More equality conditions may be AND’d together
Natural Join R * S A simplification of an Equijoin
Combines all attributes of R, S
Joins attributes with the same name
Matching attributes are implicitly matched
Relational Algebra Operations
UNION
∩ INTERSECTION
R-S SET DIFFERENCE
INNER JOIN
(X followed by )
OUTER JOIN Operations
Previous JOINS (THETA JOIN, EQUIJOIN, NATURAL JOIN) all inner joins
Match elements across tables
Rows with no corresponding elements are thrown away
Sometimes we don’t want to throw away tuples that don’t have matching values
For that we use an outer join
Three types of outer joins:
Left outer join
Right outer join
Full outer join
OUTER JOIN Operations
Outer joins
Keep all tuples in R, or all those in S, or all those in both relations regardless of whether or not they have matching tuples in the other relation
Pads with nulls for unmatched values
OUTER JOIN Operators
The LEFT OUTER join – R S
Keeps every tuple in the first or left relation R
If no matching tuple is found in S, then the attributes of S in the join result are filled or “padded” with null values.
The RIGHT OUTER join – R S
Keeps every tuple in the second or right relation S
The FULL OUTER join – R S
Keeps all tuples in both the left and the right relations when no matching tuples are found, padding them with null values as needed.
Left Outer Join
R ⟕
Still matches on join condition
But in cases where there are no matches on the join condition, keeps the unmatched tuple in R
Attributes from S padded out as NULL values
Left Outer Join
FEMALE_EMPS SEX=’F’(EMPLOYEE)
EMPNAMES FNAME, LNAME, SSN (FEMALE_EMPS)
ACTUAL_DEPENDENTS EMPNAMES ⟕ssn=Essn (DEPENDENT))
Dependent_name Sex Bdate Relationship
Alicia Zelaya 999887777 NULL NULL NULL NULL NULL
Jennifer Wallace 987654321 987654321 1942-02-28 Spouse
Joyce English 453453453 NULL NULL NULL NULL NULL
Right Outer Join
R ⟖
Again matches on join condition
But in cases where there are no matches on the join condition, keeps the unmatched tuple in S
Attributes from R padded out as NULL values
Right Outer Join
FEMALE_EMPS SEX=’F’(EMPLOYEE)
EMPNAMES FNAME, LNAME, SSN (FEMALE_EMPS)
ACTUAL_DEPENDENTS EMPNAMES ⟖Ssn=EssnDEPENDENT
Dependent_name Sex Bdate Relationship
NULL NULL NULL 333445555 1986-04-05 Daughter
NULL NULL NULL 333445555 1983-10-25 Son
NULL NULL NULL 333445555 1958-05-03 Spouse
Jennifer Wallace 987654321 987654321 1942-02-28 Spouse
NULL NULL NULL 123456789 1988-01-04 Son
NULL NULL NULL 123456789 1988-12-30 Daughter
NULL NULL NULL 123456789 1967-05-05 Spouse
Full Outer Join
R ⟗
Again matches on join condition
But in cases where there are no matches on the join condition, keeps all unmatched tuples
Attributes from other relation padded out as NULL values
Full Outer Join
FEMALE_EMPS SEX=’F’(EMPLOYEE)
EMPNAMES FNAME, LNAME, SSN (FEMALE_EMPS)
ACTUAL_DEPENDENTS EMPNAMES ⟗ Ssn=EssnDEPENDENT
Dependent_name Sex Bdate Relationship
Alicia Zelaya 99988777 NULL NULL NULL NULL NULL
NULL NULL NULL 333445555 1986-04-05 Daughter
NULL NULL NULL 333445555 1983-10-25 Son
NULL NULL NULL 333445555 1958-05-03 Spouse
Jennifer Wallace 987654321 987654321 1942-02-28 Spouse
Joyce English 453453453 NULL NULL NULL NULL NULL
NULL NULL NULL 123456789 1988-01-04 Son
NULL NULL NULL 123456789 1988-12-30 Daughter
NULL NULL NULL 123456789 1967-05-05 Spouse
Aggregate Functions
Group tuples by the value of some of their attributes
Allows functions of attributes to be included in the projection list
Apply aggregate function independently to each group
Ex., SUM, AVERAGE, MAXIMUM, and MINIMUM
Relational algebra operators
Aggregate Function Operation
without grouping
F MAX Salary (EMPLOYEE)
retrieves the maximum salary value from the EMPLOYEE relation
F MIN Salary (EMPLOYEE)
retrieves the minimum Salary value from the EMPLOYEE relation
F SUM Salary (EMPLOYEE)
retrieves the sum of the Salary from the EMPLOYEE relation
F COUNT SSN, AVERAGE Salary (EMPLOYEE)
computes the count (number) of employees and their average salary
Note: count just counts the number of rows, without removing duplicates
Aggregate Functions with Groups
List the departments (DNO) and the average salary of each
DNO F AVERAGE SAL ( EMP)
EMP( EMPNO, DNO, SAL,…)
100 D3 66,000
200 D3 55,000
300 D3 66,000
400 D1 66,000
500 D1 55,000
600 D1 60,000
700 D2 66,000
800 D2 60,000
900 D2 66,000
DNO AVG SAL
Aggregate Functions
Query Trees
A query tree is a tree data structure that corresponds to a relational algebra expression.
Input relations are leaf nodes
Relational algebra operations are internal nodes.
Query trees are evaluated from leaf nodes up to the root node.
The root node represents final result of entire relational algebra expression
Used most often in query optimization
Query Trees
input relations of query as leaf nodes of the tree
relational algebra operations as internal nodes
Example Queries
Example Queries
List the names of all employees with two or more dependents
T1(Essn,NoDeps)(EssnFCount(Dep_name)(DEPENDENT)
T2NoDeps>=2(T1)
ResultLname,Fname (EMPLOYEE ⋈Ssn=Essn T2)
Operations of Relational Algebra
Operations of Relational Algebra
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com