or
TECHNISCHE HOGESCHOOL EINDHOVEN
Onderafdeling der Wiskunde
Memorandum 1979-1 ~ november 1979
Productverzamelingen en database-relaties door E.O. de Brock
Technische Hogeschool Onderafdeling der Wiskunde PO Box 513, Eindhoven Nederland
I
INHOUD
1.
Inleiding
2.
Overzicht
3.
Declaratie van variabelen
4.
Type-definities
5.
Productverzamelingen
6.
Productverzamelingen voor de informatica
7.
De algemene definitie van productverzameling
8.
Voorbeelden van type-definities en declaraties van variabelen
9.
Wat is een DB-relatie?
10.
Terugblik
11.
Een schrijfwijze voor statements
12.
Een verwarrende schrijfwijze voor statements
13.
Wat is een array?
-
1 -
1. INLEIDING Er worden een aantal ideeen uiteengezet op het gebied van de informatica in het algemeen en op het gebied van DB's (databases) in het bijzonder. In de eerste plaats wordt er in
§
7 een minder bekende definitie
van
productverzameling uit de wiskunde van stal gehaald. In dit memorandum blijft de definitie van "relatie" onveranderlijk "deelverzameling van een productverzameling"; dus bij wijziging van de definitie van "productverzameling" verandert tevens de betekenis van "relatie". Met de definitie van productverzameling uit
§
7 worden relaties verkregen die zeer geschikt zijn voor
de beschrijving van databases; zo zijn dan bijvoorbeeld attributen (kolomhoofden van een tabel) ook onderdeel van de relatie. Genoemde definitie van productverzameling wordt ook gebruikt om records en arrays te definieren. De tweede idee: In het boek "An Introduction to Database Systems" spreekt C.J. Date over "time-varying relations". Haar hoe wordt het begrip "timevarying" formeel ondervangen? Want een "time-varying relation" is blijkbaar meer dan alleen maar een relatie. Als oplossing suggereert F. Remmen: Een DB-relatie is een type, namelijk een deelverzameling van de machtsverzameling van een cartesisch product. De definitie van DB-relatie die in
§
9 wordt gegeven is ontstaan naar
aanleiding van hat artikel "Database Abstractions: Aggregation" van J.M.Smith en D.C.P. Smith in de Communications of the ACM 20 (1977), p. 405-413, alsmede naar aanleiding van het college "Database Systemen" van F. Remmen; in beide gevallen wordt er gesproken over (DB-)relaties en over variabelen, doch in geen van beide gevallen wordt een DB--relatie opgevat als zijnde een variabele. In
§
9 wordt een DB-relatie wel gedefinieerd als een variabele:
Een DB-relatie is een variabele; een variabele waarvan de actuele waarde een wiskundige relatie is. Nog iets over dit memorandum: Uiteraard kan niet alles worden behandeld. Er zijn twee soorten afkappingen gemaakt: 1)
bepaalde uitbreidingen worden nog niet aangepakt; bijvoorbeeld worden records met variant part(s) nog niet behandeld;
2)
bepaalde gebruikte begrippen worden nog niet exact gedefinieerd, bijvoorbeeld de begrippen "toestand" en "variabele".
/
- 2 -
Enige bekendheid met verzamelingenleer en informatica wordt voorondersteld. De leesbaarheid en de didactische waarde van dit memorandum zijn aanmerkelijk verhoogd dankzij de waardevolle discussies met F. Remmen, W. Peremans en M.L. Potters; bovendien zijn dankzij hen allerlei aspecten veel beter benadrukt. 2. OVERZICHT Ons startpunt is de declaratie van variabelen; in
3 wordt verteld wat
§
het doel is van het declareren. Zo'n declaratie blijkt soms heel onoverzichtelijk te zijn. Er is behoefte aan afkortingen en die behoefte leidt tot het invoeren van type-definities
(§
4).
In de wiskunde bestaan er verschillende definities lingen. De meest bekende zegt, dat A {(a;bic)
*
*
B
vanproductverzame~
C de verzameling
a E A AbE B ACE C} is; onder het 3-tupel (a;b;c) wordt dan
verstaan het paar «a;b);c). Een tweede mogelijkheid is om A
*
B
*
C te
definieren als de verzameling van alle functies f met dome in {1,2,3} waarvoor geldt, dat f(1) · E A, f(2) EBen f(3) E C, zie
§
5. Deze tweede definitie
laat zich namelijk gemakkelijker generaliseren tot willekeurig veel "factorverzamelingen" A.
l.
:
i~I A.l. is de verzameling van alle functies f op I met
f(i) E Ai voor elke i E I. Deze generalisatie wordt aan de hand van een voorbeeld ingeleid in
§
6. In
§
7 volgt dan de exacte definitie.
Wanneer "relatie" wordt gedefinieerd als "deelverzameling van een productverzameling" dan heeft het begrip "re l a tie" na elk van de voornoemde definities van productverzameling een andere betekenis. De betekenis van "relatie", die hoort bij de definitie van productverzameling in
§
7, is
zeer geschikt voor de DB-theorie (zie de opmerkingen aan het eind van In
§
6).
§
8 worden enige voorbeelden gegeven van declaraties van variabelen en
bijbehorendetype-definities. Een en ander ziet er wel PASCAL-achtig uit, maar de ideeen erachter zijn anders, c.q. scherper (zie bijvoorbeeld De definitie van DB-relatie wordt in
§
§
10).
9 gegeven. Tevens wordt gezegd
wat wordt bedoeld met de attributen van een DB-relatie. De voorafgaande opvattingen worden in
§
11 gebruikt om een heldere (en
tevens krachtige) schrijfwijze voor statements te schetsen. Die opvattingen
/
- 3 -
achter die schrijfwijze wordt in
§
12 vergeleken met een bekende en veel
gebruikte schrijfwijze. Met de definitie van productverzameling, zoals die in
§
7 is gegeven,
blijkt een "array" een speciaal soort productverzameling te zijn, te weten een productverzameling, waarin alle factorverzamelingen aan elkaar gelijk zijni zie de laatste paragraaf. 3. DECLARATIE VAN VARIABELEN Het doel van het declareren van een variabele is om aan te geven binnen welke verzameling de waarde van die variabele mag varieren. Voorbeelden: 1)
VAR X : {1 , ••. , 300 }.
2)
We willen een variabele B declareren die de volgende vier gegevens bevat: het artikel, de kleur, de besteldatum en het aantal stuks. Hierbij is de besteldatum zelf weer samengesteld uit drie onderdelen. De declaratie wordt: {bed,stoel,tafel} {1, ..• ,12}
*
* {wit,bruin} * ({1, ... ,31} *
{1950, ... ,2000})
*
{1, ... ,1000}.
We zullen - naar een idee van T. M. V. Janssen van het MC - de actuele waarde van een variabele X aangeven met
Vx
(lees: value X). Met andere
woorden: de declaratie "VAR X : {1, ... , 300}" betekent
Vx
E
{1, .•. , 300}
in elke toestand.
4. TYPE-DEFINITIES De declaratie van de variabele X is wel overzichtelijk, doch die van B niet. We willen daarom soms afkortingen gebruiken: We geven sommige verzamelingen een (vaak suggestieve) naam, via een zogenaamde type-definitie. Voorbeeld: TYPE
ART
{bed,stoel,tafel},
AANTAL
=
DATUM
= {l, .•. , 31}
{1, ••. ,1000},
* {l , ... ,12} *
{1950, ••. , 2000}.
- 4 -
De declaratie van B kan er nu veel overzichtelijker uitzien : VAR B
ART * {wit,bruin} * DATUM
*
AANTAL.
5. PRODUCTVERZAMELINGEN Volgens een definitie uit de verzamelingenleer be staat de productverzameling D1
* ... * Dn uit alle verzamelingen, van de volgende vorm.
{(lid ),···, (nid )}, waarbij d 1 n i
E:
Di voor elke i
E:
{i, ... ,n}.
Wanneer we zeker weten, dat de volgorde niet essentieel is, gebruiken we de komma, in het andere geval De elementen van D1
* ... * Dn
'i ' .
zijn dus functies op de verzameling
{l, •.. ,n}! Omdat we toch altijd de standaardwaarden 1, •.. ,n gebruiken,
kunnen we de notatie vereenvoudigen tot de gebruikelijke notatie: (d1i ••• idn). We hebben hierbij een ordening geintroduceerd: we schrijven eerst het element uit D1 op, dan dat uit D , •.. , tens lotte dat uit Dn. 2 We noemen (d1i ... idn) een (n-) tupel en d t.e.m. d respectievelijk n 1 e e de l t.e.m. de n coordinaat van dat tupelo Dankzij de voorgaande definitie van D * ... *D kunnen we de afzondern 1 lijke coordinaten van een tupel als volgt aangegeven: Zij B E: DATUM, bijvoorbeeld
B=
(li10i1979). De tweede coordinaat van de functie (!)
B
kunnen we aangeven met 'B(2)' en er geldt 8(2) = 10. Zelfs wanneer de productverzamelingen "genest" voorkomen kunnen we tHke coordinaat aangeven: Zij a bijvoorbeeld a
=
E:
ART * {wit,bruin}
*
DATUM * AANTAL,
(bediwiti (li10;1979);1). Nu geldt a(2)
= wit
en a(3)
(lil0i1979). Doch a(3) is zelf ook een functie en we zien bijvoorbeeld, dat a(3)(2)
=
10 en a(3)(3)
=
1979.
6. PRODUCTVERZAMELINGEN VOOR DE INFORMATICA We zagen in de vorige paragraaf, dat de elementen van D * ... *D n 1 functies zijn op een v66rgeschreven domein (namelijk {l, .•. ,n}). Doch het enig essentiele van dat domein is, dat het n elementen heeft.
,
,
- 5 -
Voorbeeld:
A*B*C = {f: {l,2,3} + A UBU C
I
fO)
E A" ~
f(2)
E B 1\ ~
f(3)
E C}. ~
(1)
We zullen een ruimere definitie van "productverzameling" geven, namelijk een waarin we het domein zelf mogen kiezen *). We moeten dan wel aangeven welk element van dat domein bij A "hoort", welke bij B en welke bij C, zie de pij ltjes bij (1). We
g~ven
eerst de nota tie aan de hand van een voorbeeld, dan de verzame-
lingstheoretische beschrijving van dat voorbeeld en vervolgens geven we in §
7 de algemene definitie van zo'n productverzameling.
De notatie:
PRODUCT NR - A,
~Hier
KL - B,~
gebruiken we de komma,
want de volgorde is niet van belang
SRT- C
END.
Nu de verzamelingstheoretische beschrijving van dit voorbeeld: PRODUCT NR - A, KL - B, SRT - C END
=
{f: {NR,KL,SRT} + A U B U C
E
f(NR)
A " f(KL)
~
E
B " f(SRT)
~
E
C}.
~
Bij deze opvatting van productverzameling zijn de "kolommen" van een relatie niet geordend, overeenkomstig de wensen in DB-theorie. Bovendien kunnen we, overeenkomstig het DB-gebruik, aan een "kolom" van een relatie refereren via zijn "attribuut" (zie
§
9), in plaats van via de relatieve
positie van de "kolom". 7. DE ALGEMENE DEFINITIE VAN PRODUCTVERZAMELING Om de algemene definitie te vinden, bekijken we het voorbeeld aan het eind van
§
6 nog eens nauwkeurig. We zien, dat er met elke "index" (in dat
*) Die ruimere definitie wordt bijvoorbeeld gebruikt om productverzamelingen met willekeurig veel "factorverzamelingen" te definieren.
/
/
- 6 -
voorbeeld KL, NR en SRT) precies een verzameling correspondeert (functiebegrip dus). Zij daarom F een functie waarvoor geldt, dat F(i) voor elke i
E
domein (F)
een verzameling is:
PRODUCT FEND
def.
{f
If
is een functie A dom(f) = dom(F)A f(i) E F(i) voor elke i E dom(f)}.
Met het geven van bovenstaande algemene definitie doorbreken we de traditie, dat in de DB-literatuur definities alleen aan de hand van voorbeelden worden gegeven. Het domein van F noemen we wel de indexverzameling van de productverzameling PRODUCT F END. In het voorbeeld aan het eind van de vorige paragraaf is F gelijk aan {(SRTiC),
(NRiA),
(KLiB)}. We merken op, dat we daar de notatie hebben ver-
fraaid: de accolades en de haakjes (die syntactisch overbodig zijn) zijn weggelaten, terwijl de punt-komma's zijn vervangen door De productverzamelingen "oude stijl"
(§
'-'
5) kunnen we uitdrukken in de
nieuwe (dus de nieuwe definitie omvat de oudei de oude definitie is overbodig) :
8. VOORBEELDEN VAN TYPE-DEFINITIES EN DECLARATIES VAN VARIABELEN Aan de hand van het voorafgaande zullen we nu enige voorbeelden geven van type-definities en declaraties van variabelen. We willen nog aandacht vestigen op het samengestelde type BESTELLING, waarin DATUMS ook weer een productverzameling is. We zullen ook een variabele X declareren die over de indexverzameling van BESTELLING kan varieren.
i
I
- 7 -
TYPE
. "=: {bed, steel, tafel},
ART
. . .: .~1'1'1Y'. . . :
...= ... 15")-1' -~.. ~ ~
{\ ;i
{1, ... ,31},
MND
- {1,..., 12} ,
'-
JAAR - {1950, ••• ,2000} ODUCT
A
ART,
KL - {wit,bruin}, D - DATUMS, NR - AANTAL
2; VAR
Y
AANTAL,
Z
DATUMS,
X
{A, D, KL,NR} ,
M
{l, .. ,12},
B
BESTELLING,
BREL : POWERSET OF BESTELLING. Misschien ten evervleede geven we de definitie van 'POWERSET': Zij V een verzameling: POWERSET OF V def. {W
Dus inclusief
¢
I W .=. V}.
en V zelf!
Wanneer we dan tech suggestieve namen willen gebruiken: met enze epvatting van type-definities is BESTELLING de verzameling van alle megelijke bestellingen en zeu daarem misschien beter BESTELLINGEN kunnen werden ge...noemd. Dezelfde .ep.merking geldt veer ART en AANTAL. Bij DATUMS is de benaming -we1. · ·yo:i s t ' ~.
9. WAT IS EEN DB-RELATIE ? nctueJ l? , --< ' 1,·,. " n de variabele BREL is een relatie, zeals blijkt uit o'('ige paragraaf; BREL neemen we een DB-relatie:\
/
- 8 -
Een DB-relatie is een variabele; een variabele waarvan de actuele waarde een wiskundige relatie is. KL,NR,A en D noemen we de "attributen" van de DB-relatie BREL: De attributen van een DB-relatie zijn de indices van de onderliggende productverzameling ! 10. TERUGBLIK Belangrijk in het voorafgaande, en verhelderend, is de (voor velen alternatieve) definitie van productverzameling in DATUMS bijvoorbeeld (zie
§
§
7; de productverzameling
8) is de verzameling van aIle functies f op het
domein {JAAR,MND,DAG} waarvoor geldt, dat f(DAG)
E
{1, ••• ,31}, f(MND)
E
{1, ... ,12
en f(JAAR) E {1950, ••. ,2000}. Dus MND is noch een variabele op {1, •.. ,12}, noch (een naam voor) de verzameling {1, .•. ,12} (geen type-aanduiding); MND is een index. We willen het effect van de definitie uit
§
7 ook illustreren aan de vol-
gende twee voorbeelden: TYPE
A
PRODUCT
D
boolean,
C - integer END,
B
= PRODUCT
E
boolean,
C - integer END. Omdat de indices D en C, respectievelijk E en C zijn "opgenomen" in de definitie van de productverzamelingen A respectievelijk B, zijn A en B inderdaad twee verschillende verzamelingen. 11. EEN SCHRIJFWIJZE VOOR STATEMENTS We verkrijgen eenheldere
en krachtige schrijfwijze voor statements met
behulp van de volgende 3 ideeen:
I
I
- 9 -
1)
de notatie Vx voor de actuele waarde van de variabele X;
2)
de opvatting, dat een productverzameling een verzameling functies is, elk met de indexverzameling als domein; de functionele notatie, geintroduceerd aan het eind van
3)
§
5.
We nemen als voorbeeld de variabele B van § 8: v BE BESTELLING, dus v B is een functie met dome in {A,D,KL,NR } waarvoor onder meer geldt, dat vB(KL) E {wit,bruin} en vB(D)
E
DATUMS. Uit de definitie van
DATUMS volgt, dat vB(D) weer een functie is, met {JAAR,DAG,MND} als domein. Zo zien we, dat vB (D)(MND)
E
{l, ... , 12}.
De voorgaande uitleg vatten we samen in de volgende twee plaatjes:
r
functie
argument
variabele::4 - VB
€
BESTELLING
functie
argument
A
functie
argument Ii'.
(KL)
J 'I
(D)
(MND)
E {wit,bruin} E
BESTELLING
E
DATUMS
E
{l, ... ,12}
We schrijven enige statements op in onze nota tie (voor de declaratie van X en B zie
§
8):
Vx := A; vB(KL) := wit; VB (vX) := bed; vB(D) (MND)
:=
10; vB(D) (DAG)
:=
1; vB(D) (JAAR)
:=
1979.
We kunnen de laatste drie assignments ook in een keer doen (let wel: vB(D) is een functie, dus een verzameling paren): VB(D)
:=
{(JAAR; 1979), (MND; 10), (DAG; 1)}.
/
/
- 10 I
We mogen dus niet opschrijven
vB(D)
:=
(1;10;1979) , de indices moeten
erbij vermeld worden. We kunnen zelfs in een keer een complete assignment op B doen: vB := {(NR;l), (KL;wit), (A;bed) , (D;{(DAG;1), (MND;10), (JAAR;1979)})}. 12. EEN VERWARRENDE SCHRIJFWIJZE VOOR STATEMENTS De in de informatica gebruikte notatie verschilt in twee opzichten van die in
§
11: V
1)
Bij elke variabele wordt het "value-teken" ( ) weggelaten. Dat kan leiden tot verwarring, bijvoorbeeld bij pointer-variabelen.
2)
Er wordt B.D geschreven in plaats van vB(D). Het tweede notatie-verschil is op zich niet belangrijk, echter weI de
verschillen in opvattingen, die er achter steken: B.D is een (samengestelde) variabele, terwijl vB(D) geen variabele is, maar de functie vB toegepast op het argument D. Er bestaat in de informatica namelijk een zeer algemene definitie (die in
§
11 overbodig was), welke bij elke variabele X van PRODUCT-type (in
bijvoorbeeld PASCAL record-type) en bij elke index A behorend bij dat PRODUCTtype een nieuwe variabele X.A definieert. Zoln variabele wordt gedefinieerd, dus niet gedeclareerd; zeer venijnig ! In die algemene definitie wordt zoln nieuwe variabele X.A vastgelegd door voor elke toestand zijn waarde te definieren (we maken gebruik van de notatie uit
§
11):
V(X.A)
r
variabele
def.
v
X
(A).
~
variabele
functie argument
,
,
- 11 -
Het wonderlijke is nu, dat A zowel in de variabele X.A voorkomt als in de type-definitie (als index). A wordt nu een "selector" genoemd en men weet niet precies wat dat is. Bij "nesting" van PRODUCT-typen worden ook bij gedefinieerde variabelen weer "automatisch" nieuwe variabelen gedefinieerd (!): Zo is B.D (zie
§
8)
een variabele van het ?RODUCT-type DATUMS, dus is meteen ook de variabele B.D.MND van type {1, ••• 12} gedefinieerd. In
§
11 gebruikten we slechts een
variabele (B):vB(D) (MND); bij elke variabele ' komt de value-operator v~~r. **) We schrijven nu de statements uit
§
11 op met de notatie uit deze para-
graaf:
X :=A
*) ; B.KL := wit; B.X := bed *) ;
B.D.MND := 10; B.D.DAG := 1; B.D.JAAR
:=
1979.
We merken op, dat door de laatste assignment (delen van) drie (!) variabelen worden veranderd, te weten de variabelen B,B.D en B.D.JAAR. Ook dat kan aanleiding geven tot verwarring en tot fouten, bijvoorbeeld bij correctheidsbewijzen. Bij de visie van
§
11 wordt er per assignment
maar (een deel van) een variabele verru1derd ! De variabelen B,B.D en B.D.JAAR "overlappen" elkaar: in
§
11 kennen we
geen elkaar overlappende variabelen.
*) Een variabele over een indexverzameling is in de informatica vaak niet toegestaan. Vanwege mogelijke verwarring bij B.X misschien?
**) Zodra we de value-operator hebben toegepast op een variabele is er geen "dynamisch" aspect meer. In § 12 is er echter na de toepassing van B op D (B.D) nog steeds een dynamisch aspect. Zelfs na toepassing van B.D op MND is dat aspect er nog steeds: B.D.MND is immers een variabele. In § 11 ontdoen we ons zo snel mogelijk van dat moeilijke aspect: het "dynamische" aspect.
,
. - 12 -
13. WAT IS EEN ARRAY ? We trekken tens lotte de voorgaande visie nog door naar het begrip "array". Welnu: Een veel voorkomende situatie is, dat bij een product alle verzamelingen gelijk zijn (en vaak ook de index verzameling groot). Als de indexverzameling bijvoorbeeld 100 elementen bevat, dan zouden we bij de definitie van dat product 100 regels moeten opschrijven, hetgeen overbodig wordt door de volgende notatie, waarin we ARRAY als een speciaal geval van PRODUCT zien: Laten I en W verzamelingen zijn: ARRAY
I
OF
W
def.
PRODUCT {(i; W)
Of, als we dedefinitie uit
ARRAY
I
OF
W;:: {f
I
§
liE I}
END.
7 toepassen:
f is een functie " domein (f) f(i) E W voor elke i E I}.
= I"
