4. Some Proofs in Relational Algebra

Werner Van Belle¹ - werner@yellowcouch.org, werner.van.belle@gmail.com

1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium

Abstract : Goes into some of the details of the theory behind relational algebra

Reference: Werner Van Belle; Some Proofs in Relational Algebra;

A: Opwarmertje: selectie na projectie / projectie na selectie^¹

Eigenschap:

Zij R = (S,P) en S’  S.

Als A  S’, dan

Bewijs:

Het tweede lid is

Het eerste lid is

Vermits nu A  S’geldt dat  t  P waar t’ = t.S’: t’.A = t.S’.A = t.A en dus zijn beide verzamelingen gelijk.

Opgave:

Als aan de voorwaarde A  S’ niet voldaan is geldt deze eigenschap niet. Geef hiervan een tegenvoorbeeld.

B: Projectie na unie/doorsnede

1. Is deze uitspraak waar ? Zoja. Bewijs dit. Zonee, geef een tegenvoorbeeld.

2. Doe hetzelfde voor de doorsnede.

C: Selecties

3. Bewijs dat

4. Bewijs dat

Is de equi join commutatief ?

D: Dum Dee Dum

DUM is de lege relatie: DUM = {};

DEE is de relatie die het lege element bevat: DEE = {{}} = {};

Wat is DUM  R ?
Wat is DEE  R als het attribuut overeenkomt met een attribuut uit R ?
Wat is DEE  R als het attribuut overeenkomt met geen enkel attribuut van R overeenkomt ?

A: We kunnen geen selectie doen waarbij de conditie een atribuut bevat dat niet in de relatie zit. Bijgevolg kunnen we de selectie (als a  S’) gewoon niet uitvoeren.

B: Ze is waar, maar ik ben te lui om het op te schrijven  Merk op dat de tweede (de doorsnede) niet waar is hoewel we wel op heel eenvoudige wijze kunnen bewijzen dat dit wel waar.

C: DUM join R is {} met de heading van R

DEE join R is R.

Addendum

B1: Projectie na unie is gelijk aan unie na projectie

Dit kan gemakkelijk bewezen worden als volgt:

B2: Projectie na doorsnede is niet gelijk aan doorsnede na projectie

Een tegenvoorbeeld:

A	B
1	2

A	B
1	3

X = {A}

In dit geval is

Het probleem met deze oefening is dat deze op exact dezelfde wijze bewezen kan worden als voor de doorsnede, waar het niet dat er een onnauwkeurigheid in het bewijs plaatsgrijpt…

De fout die men hierbij gemakkelijk maakt is te beweren dat er bestaat een a waarvoor A en B geldt gelijk is aan er bestaat een a waarvoor A geld en er bestaat een andere a waarvoor B geldt. Met andere woorden… er bestaat is niet distribuitief ten opzichte van de en, maar wel ten opzichte van de of.

1 Ik distantieer mij volledig van de afgrijselijke layout van deze oefeningensessie.

http://werner.yellowcouch.org/
werner@yellowcouch.org