Relational Algebra

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

Sup­port trans­la­tion:
 — —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  —  — —
Rela­tion­al Algeb­ra
What is an Algeb­ra?
algeb­ra (al-je-bre) noun
1 A gen­er­al­isa­tion of arith­met­ic in which sym­bols, usu­ally let­ters of the alpha­bet, rep­res­ent num­bers or mem­bers of a spe­cific set of num­bers and are related by oper­a­tions that hold for all num­bers in the set.
2 A set togeth­er with oper­a­tions defined in the set that obey spe­cified laws.
3 Word intro­duced by Arab math­em­atician al-Khwar­izmi (cir­ca 900 AD) and brought over into Lat­in by Robert of Chester in 1145.

[Middle Eng­lish, bone-set­ting and Itali­an, algeb­ra, both from Medi­ev­al Lat­in, from Arab­ic al-jabr, the (sci­ence of) reunit­ing: al, the + jabr, reuni­fic­a­tion, bone-set­ting.]
Algeb­ra­ic lan­guages are com­mon in com­put­ing: Boolean algeb­ra for logic gates; and Rela­tion­al algeb­ra for data­base DML.
Basic ingredi­ents of an algeb­ra are a set (i.e. oper­and) and oper­a­tions (i.e. oper­at­ors) that act on all ele­ments of the set.
Oper­at­or prop­er­ties (for example, con­sider an integer set and the addi­tion oper­a­tion) include: Addi­tion is com­mut­at­ive over the integers since 3 + 4 = 4 + 3 (plus(3,4) == plus(4,3)); and Addi­tion is said to be asso­ci­at­ive over the integers since 3 + (4 + 5) = (3 + 4) + 5 (plus (3,plus(4,5)) == plus(plus(3,4),5))).
Char­ac­ter­ist­ics of the Rel. Algeb­ra
It manip­u­lates entire rela­tions through a
semantic­ally unam­big­ous set of oper­a­tions (Ed
Codd 1970).

The rela­tion­al algebra’s sets are the relation’s
exten­sion (tuples,rows) and the oper­at­ors have
either a set the­or­et­ic ori­gin or rela­tion ori­ented

A rela­tion­al algeb­ra­ic expres­sion has as inputs one
(unary), or two (bin­ary), rela­tions and some­times a
selec­tion con­di­tion.
While an expression’s out­put is a single rela­tion.

Oth­er Char­ac­ter­ist­ics:

the algebra’s oper­at­ors work on all of the relation’s tuples;

the algeb­ra has a pro­ced­ur­al com­pu­ta­tion­al

But it is not ““Tur­ing com­plete””, one can write a
Pas­cal pro­gram that manip­u­lates rela­tions for
which there is no algeb­ra­ic equi­val­ent.

a selec­tion con­di­tion has to be eval­u­ated again­st
each tuple inde­pend­ently;

the out­put of an algeb­ra­ic oper­a­tion is an
accept­able input to a con­sequent algeb­ra­ic
expres­sion — this is called expres­sion

Oper­at­ors: Uni­on (bin­ary)
What about the typ­ing of a rela­tion­al algeb­ra­ic expres­sion and its res­ult­ant rela­tion?
““UNION”” COMPATIBILITY (u.c.) of TWO RELATIONS For a bin­ary expres­sion, the two par­ti­cip­at­ing rela­tions (oper­ands — R1 and R2) must have the fol­low­ing struc­tur­al con­straints for the expres­sion to be type cor­rect: 1) both rela­tions have the same degree (i.e. n); & 2) for each attrib­ute (1 < = i <= n), the domain (R1.Attr_i) = domain(R2.Attr_i). THE DATA TYPE OF AN Expression’s IF the two rela­tions are in u.c. THEN the rela­tion schema of the res­ult­ant is arbit­rary chosen to be that of the first oper­and. ELSE … (oper­and spe­cific — e.g. pro­duct oper­at­or) Semantics: The res­ult­ant rela­tion has all the tuple present in either the first, the second or both oper­ands.
The type of the res­ult­ant rela­tion schema is that of the first oper­and if both oper­and rela­tions are in u.c.
com­mut­at­ive YES asso­ci­at­ive YES
Oper­at­ors: Dif­fer­ence (bin­ary)
The res­ult­ant rela­tion includes all the tuples of the first oper­and that are not present in the second oper­and.
The type of the res­ult­ant rela­tion schema is that of the first oper­and if both oper­and rela­tions are in u.c.
R1 — R2 DIFF(R1,R2)
com­mut­at­ive NO asso­ci­at­ive NO
Oper­at­ors: Selec­tion (unary)
Cre­ate a new rela­tion by extract­ing from the oper­and all tuples that sat­is­fy the selec­tion con­di­tions.
The type of the res­ult­ant rela­tion schema is equi­val­ent to the operand’s schema.
A selec­tion con­di­tion has the fol­low­ing form:
Attrib­ute name Com­par­is­on op. Con­stant value or Attrib­ute name Com­par­is­on op. Attrib­ute name
A series of Selec­tion con­di­tions could be com­bined as in select con­di­tion1 AND select con­di­tion2 or select con­di­tion1 OR select con­di­tion2
Some typ­ic­al com­par­is­on oper­at­ors for ordered domains include >, < , ==, !=, etc
(select con­di­tion) R1 SELECT (R1, selec­tion con­di­tion)
The res­ult­ant is a sub­set of the oper­and!

com­mut­at­ive YES asso­ci­at­ive YES
Rela­tion­al Algeb­ra: Oper­at­ors: Pro­duct (bin­ary)
Cre­ate a new rela­tion by execut­ing a Cartesian pro­duct
of the two oper­ands.
(If the car­din­al­it­ies of R1 and R2 are 60000 and 500
respect­ively, their product’s car­din­al­ity is 60000500 =

The oper­ands can have any rela­tion schema. The res­ult­ant rela­tion schema is equi­val­ent to the con­cat­en­a­tion of the operand’s rela­tion schema.
This is an extremely com­pu­ta­tion­ally expens­ive
Also, the res­ult­ant exten­sion is not usu­ally mean­ing­ful!!

com­mut­at­ive Yes
asso­ci­at­ive Yes

Oper­at­ors: Pro­jec­tion (unary)
Cre­ate a new rela­tion by remov­ing from the oper­and all attrib­utes (and con­sequently their val­ues) that are not men­tioned in the pro­jec­tion expres­sion.
The type of the res­ult­ant schema is equi­val­ent to the operand’s schema but exclud­ing attrib­utes not men­tioned in the attrib­ute list.
(attr…x1,…,attr_xn) PROJECT(R1,attr_x1,…,attr_xn)
Duplic­ate val­ues are impli­citly removed!
Fur­ther Notes:
In an algeb­ra­ic expres­sion with a string of pro­jects we have two things going on — restruc­tur­ing and re-extend­ing!! With cer­tain algeb­ra­ic manip­u­la­tions one can over­come these restric­tions.
com­mut­at­ive (in gen­er­al) No asso­ci­at­ive (in gen­er­al) No
Min­im­al set of oper­at­ors
It can be shown that a sub­set of the presen­ted oper­at­ors (spe­cific­ally the select, pro­ject, uni­on, dif­fer­ence and pro­duct) are adequate, or com­plete, to describe the oth­er oper­at­ors (for example join, inter­sec­tion etc).
The exclus­ive use of oper­at­ors from the com­plete set make read­ing some nat­ur­al algeb­ra­ic expres­sions extremely unyield­ing!
For example, the inter­sec­tion oper­at­or has this form:
is equi­val­ent to DIFF ( UNION (R1,R2), UNION (DIFF(R1,R2), (DIFF(R2,R1) ) )
or equi­val­ent to
Why an algeb­ra?
a sim­ple lan­guage
set at a time access
semantic­ally sound
expresses the same quer­ies that another rela­tion­al mod­el based lan­guage describes
(i.e. the declar­at­ive rela­tion­al cal­cu­lus)
Query (one) – Com­pany
Retrieve then name and address of all employ­ees who work for the ‘Research’ depart­ment.
research_dept := select dname=’Researcg’ (depart­ment);
research_dept_emps := select dnumber=dno (research_dept pro­duct employ­ee);
algl1 := pro­ject fname, lname, address (research_dept_emps);
Query (two) – Com­pany
For every pro­ject loc­ated in ‘Stafford’, list the Pro­ject num­ber, the con­trolling depart­ment num­ber, And the depart­ment manager’s last name, address, And birth­d­ate.
Stafford-_projs := select plocation=’Stafford’ (pro­jects);
Con­tr_dept := select dnum-dnum­ber (Stafford_­projs pro­duct depart­ment);
pro­j_dept_m­gr := select mgrssn=ssn (con­tr_dept pro­duct employ­ee);
alg2 := pro­ject pnum­ber, dnum, lname, address, bdate (pro­j_dept_m­gr);
Query (three) – Com­pany
Find the names of employ­ees who work on all the Pro­jects con­trolled by depart­ment num­ber 5.
Dept5_projs(pno) := pro­ject pnum­ber (select dnum=5 (pro­jects)); emp_proj(ssn,pno) := pro­ject essn, pno (work­s_on); emp_­pro­j_ssns := pro­ject ssn (emp_­proj); % All pos­sib­il­it­ies of employ­ees work­ing on dept5 pro­jects. Pos­s_emps_dept5 := (dept5_­projs pro­duct emp_proj_ssns);/ % Employ­ees that don’s work on all dept5 pro­jects.. emps_not_dept5 :=pro­ject ssn (pos­s_emps_dept5 dif­fer­ence emp_­proj); res­ult_em­p_ssns :=emp proj ssns dif­fer­ence emps_not_dept5; alg3 :=pro­ject lname, fname (res­ult_em­p_ssns njoin employ­ee);
Query (four) – Com­pany
Make a list of pro­ject num­bers for pro­jects that Involve an employ­ee whose last name is ‘Smith’, Either as a work­er or as a man­ager of the Depart­ment that con­trols the pro­ject.
Smiths(essn) := pro­ject ssn (select lname= ‘Smith’ (employ­ee));
smith_­work­er­_­projs := pro­ject pno (work­s_on njoin smiths);
mgrs := pro­ject lname, dnum­ber (select ssn=mgrssn (employ­ee pro­duct depart­ment));
smith_m­grs := selecy lname=’Smith’ (mgrs);
smith_managed_depts(dnum) := pro­ject dnum­ber (smith_m­grs);
smith_mgr_projs(pno) := pro­ject pmum­ber (smith_­man­aged_depts njoin pro­jects);
alg3 := smith_­work­er­_­projs uni­on smith_m­gr_­projs;
Query (five) – Com­pany
List the names of all employ­ees with two or more Depend­ents.
% Make two cop­ies of employ­ees with depend­ents.
Empdep1(essn, dep­name1) := pro­ject essn, depend­ent_­name (depend­ent);
empdep2(essn2, dep­name2) := emp­de­p1;
& Employ­ees with more than one depend­ent.
Emps_gtone_dep(ssn) := pro­ject ess­n1 (select (essn=essn2) and (depname1<>depname2) (emp­de­p1 pro­duct emp­de­p2));
alg5 := pro­ject lname, fname (employ­ee njoin emps)gtone_dep);
Query (six) — Com­pany
Retrieve the names of employ­ees who have no Depend­ents.
All_emps := pro­ject ssn (employ­ee); Emps_with_deps(ssn) := pro­ject essn (depend­ent); Emps_without_deps := (all_emps
Dif­fer­ence emps_with_deps); Alg6 := pro­ject lname, fname
(emps_without_deps njoin employ­ee);
Query (sev­en) – Com­pany
List the names of man­agers who have at least One depend­ent.
Mgrssn(ssn) := pro­ject mgrssn (depart­ment); Emps_with_deps(ssn) := pro­ject essn (depend­ent); Mgrs_with_deps := (mgrssn inter­sect emps_with_deps); Alg7 := pro­ject lname, fname
(mgrs_with_deps njoin employ­ee);

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