“——————————————————————————————————————————————————

Support translation: http://amzn.to/1Z7d5oc

——————————————————————————————————————————————————

Relational Algebra

What is an Algebra?

algebra (al-je-bre) noun

Mathematics

1 A generalisation of arithmetic in which symbols, usually letters of the alphabet, represent numbers or members of a specific set of numbers and are related by operations that hold for all numbers in the set.

2 A set together with operations defined in the set that obey specified laws.

3 Word introduced by Arab mathematician al-Khwarizmi (circa 900 AD) and brought over into Latin by Robert of Chester in 1145.

[Middle English, bone-setting and Italian, algebra, both from Medieval Latin, from Arabic al-jabr, the (science of) reuniting: al, the + jabr, reunification, bone-setting.]

Algebraic languages are common in computing: Boolean algebra for logic gates; and Relational algebra for database DML.

Basic ingredients of an algebra are a set (i.e. operand) and operations (i.e. operators) that act on all elements of the set.

Operator properties (for example, consider an integer set and the addition operation) include: Addition is commutative over the integers since 3 + 4 = 4 + 3 (plus(3,4) == plus(4,3)); and Addition is said to be associative over the integers since 3 + (4 + 5) = (3 + 4) + 5 (plus (3,plus(4,5)) == plus(plus(3,4),5))).

Characteristics of the Rel. Algebra

It manipulates entire relations through a

semantically unambigous set of operations (Ed

Codd 1970).

The relational algebra’s sets are the relation’s

extension (tuples,rows) and the operators have

either a set theoretic origin or relation oriented

favour.

A relational algebraic expression has as inputs one

(unary), or two (binary), relations and sometimes a

selection condition.

While an expression’s output is a single relation.

Other Characteristics:

the algebra’s operators work on all of the relation’s tuples;

the algebra has a procedural computational

model;

But it is not “”Turing complete””, one can write a

Pascal program that manipulates relations for

which there is no algebraic equivalent.

a selection condition has to be evaluated against

each tuple independently;

the output of an algebraic operation is an

acceptable input to a consequent algebraic

expression – this is called expression

composition.

Operators: Union (binary)

What about the typing of a relational algebraic expression and its resultant relation?

“”UNION”” COMPATIBILITY (u.c.) of TWO RELATIONS For a binary expression, the two participating relations (operands — R1 and R2) must have the following structural constraints for the expression to be type correct: 1) both relations have the same degree (i.e. n); & 2) for each attribute (1 < = i <= n), the domain (R1.Attr_i) = domain(R2.Attr_i). THE DATA TYPE OF AN Expression’s IF the two relations are in u.c. THEN the relation schema of the resultant is arbitrary chosen to be that of the first operand. ELSE … (operand specific – e.g. product operator) Semantics: The resultant relation has all the tuple present in either the first, the second or both operands.

Typing:

The type of the resultant relation schema is that of the first operand if both operand relations are in u.c.

Notation:

R1 U R2 UNION(R1,R2)

commutative YES associative YES

Operators: Difference (binary)

Semantics:

The resultant relation includes all the tuples of the first operand that are not present in the second operand.

Typing:

The type of the resultant relation schema is that of the first operand if both operand relations are in u.c.

Notation:

R1 – R2 DIFF(R1,R2)

commutative NO associative NO

Operators: Selection (unary)

Semantics:

Create a new relation by extracting from the operand all tuples that satisfy the selection conditions.

Tuples:

The type of the resultant relation schema is equivalent to the operand’s schema.

A selection condition has the following form:

Attribute name Comparison op. Constant value or Attribute name Comparison op. Attribute name

A series of Selection conditions could be combined as in select condition1 AND select condition2 or select condition1 OR select condition2

Some typical comparison operators for ordered domains include >, < , ==, !=, etc

Notation:

(select condition) R1 SELECT (R1, selection condition)

Note:

The resultant is a subset of the operand!

commutative YES associative YES

Relational Algebra: Operators: Product (binary)

Semantics:

Create a new relation by executing a Cartesian product

of the two operands.

(If the cardinalities of R1 and R2 are 60000 and 500

respectively, their product’s cardinality is 60000 * 500 =

3,000,000!)

Typing:

The operands can have any relation schema. The resultant relation schema is equivalent to the concatenation of the operand’s relation schema.

Notation:

This is an extremely computationally expensive

operation!

Also, the resultant extension is not usually meaningful!!

commutative Yes

associative Yes

Operators: Projection (unary)

Semantics:

Create a new relation by removing from the operand all attributes (and consequently their values) that are not mentioned in the projection expression.

Typing:

The type of the resultant schema is equivalent to the operand’s schema but excluding attributes not mentioned in the attribute list.

Notation:

(attr…x1,…,attr_xn) PROJECT(R1,attr_x1,…,attr_xn)

Note:

Duplicate values are implicitly removed!

Further Notes:

In an algebraic expression with a string of projects we have two things going on – restructuring and re-extending!! With certain algebraic manipulations one can overcome these restrictions.

commutative (in general) No associative (in general) No

Minimal set of operators

It can be shown that a subset of the presented operators (specifically the select, project, union, difference and product) are adequate, or complete, to describe the other operators (for example join, intersection etc).

The exclusive use of operators from the complete set make reading some natural algebraic expressions extremely unyielding!

For example, the intersection operator has this form:

INTERSECTION (R1,R2)

is equivalent to DIFF ( UNION (R1,R2), UNION (DIFF(R1,R2), (DIFF(R2,R1) ) )

or equivalent to

DIFF(R1,DIFF(R1,R2))

Why an algebra?

a simple language

set at a time access

semantically sound

expresses the same queries that another relational model based language describes

(i.e. the declarative relational calculus)

procedural

optimisable

Query (one) â€“ Company

Retrieve then name and address of all employees who work for the â€˜Researchâ€™ department.

research_dept := select dname=â€™Researcgâ€™ (department);

research_dept_emps := select dnumber=dno (research_dept product employee);

algl1 := project fname, lname, address (research_dept_emps);

Query (two) â€“ Company

For every project located in â€˜Staffordâ€™, list the Project number, the controlling department number, And the department managerâ€™s last name, address, And birthdate.

Stafford-_projs := select plocation=â€™Staffordâ€™ (projects);

Contr_dept := select dnum-dnumber (Stafford_projs product department);

proj_dept_mgr := select mgrssn=ssn (contr_dept product employee);

alg2 := project pnumber, dnum, lname, address, bdate (proj_dept_mgr);

Query (three) â€“ Company

Find the names of employees who work on all the Projects controlled by department number 5.

Dept5_projs(pno) := project pnumber (select dnum=5 (projects)); emp_proj(ssn,pno) := project essn, pno (works_on); emp_proj_ssns := project ssn (emp_proj); % All possibilities of employees working on dept5 projects. Poss_emps_dept5 := (dept5_projs product emp_proj_ssns);/ % Employees that donâ€™s work on all dept5 projects.. emps_not_dept5 :=project ssn (poss_emps_dept5 difference emp_proj); result_emp_ssns :=emp proj ssns difference emps_not_dept5; alg3 :=project lname, fname (result_emp_ssns njoin employee);

Query (four) â€“ Company

Make a list of project numbers for projects that Involve an employee whose last name is â€˜Smithâ€™, Either as a worker or as a manager of the Department that controls the project.

Smiths(essn) := project ssn (select lname= â€˜Smithâ€™ (employee));

smith_worker_projs := project pno (works_on njoin smiths);

mgrs := project lname, dnumber (select ssn=mgrssn (employee product department));

smith_mgrs := selecy lname=â€™Smithâ€™ (mgrs);

smith_managed_depts(dnum) := project dnumber (smith_mgrs);

smith_mgr_projs(pno) := project pmumber (smith_managed_depts njoin projects);

alg3 := smith_worker_projs union smith_mgr_projs;

Query (five) â€“ Company

List the names of all employees with two or more Dependents.

% Make two copies of employees with dependents.

Empdep1(essn, depname1) := project essn, dependent_name (dependent);

empdep2(essn2, depname2) := empdep1;

& Employees with more than one dependent.

Emps_gtone_dep(ssn) := project essn1 (select (essn=essn2) and (depname1<>depname2) (empdep1 product empdep2));

alg5 := project lname, fname (employee njoin emps)gtone_dep);

Query (six) – Company

Retrieve the names of employees who have no Dependents.

All_emps := project ssn (employee); Emps_with_deps(ssn) := project essn (dependent); Emps_without_deps := (all_emps

Difference emps_with_deps); Alg6 := project lname, fname

(emps_without_deps njoin employee);

Query (seven) â€“ Company

List the names of managers who have at least One dependent.

Mgrssn(ssn) := project mgrssn (department); Emps_with_deps(ssn) := project essn (dependent); Mgrs_with_deps := (mgrssn intersect emps_with_deps); Alg7 := project lname, fname

(mgrs_with_deps njoin employee);

”

“——————————————————————————————————————————————————