代写代考 Relational Model

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 S =  (R X S)

Nested application of SELECT operations
( < cond2> (R)) ≡  AND < cond2> (R)

Is SELECT Commutative?
( < condition2> (R)) =  ( < condition1> (R))

Cascading of the SELECT operation may be applied in any order:
( ( (R))) =  ( ( ( R)))

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

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 S Only match related tuples
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 ⟕ S
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 ⟖ S
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 ⟗ S
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)
T2NoDeps>=2(T1)
ResultLname,Fname (EMPLOYEE ⋈Ssn=Essn T2)

Operations of Relational Algebra

Operations of Relational Algebra

/docProps/thumbnail.jpeg

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com