2003

1

Plan voor Vandaag

Relationele Databases 2002/2003

• Praktische dingen

Hoorcollege 8 19 juni 2003

• Huiswerk ? 7.1, 7.3, 7.5, 7.9, 7.12, 7.16, 7.20, 7.21, 7.23, en 7.24

Jaap Kamps & Maarten de Rijke April – Juli 2003

• Theorie ? Silberschatz et al: hoofdstuk 10 (§10.1 – §10.2). ? XML • Vragen? • Hoe ziet een tentamen eruit?

2

Huishoudelijke Zaken

3

Huiswerk

• Docenten: 7.1 Explain what is meant by repetition of information and inability to represent information. Explain why each of these properties may indicate a bad relational database design.

1. Jaap Kamps, Email: [email protected] 2. Maarten de Rijke, Email: [email protected] • URL voor de cursus:

? Repetition of information is a condition in a relational database where the values of one attribute are determined by the values of another attribute in the same relation, and both values are repeated throughout the relation. This is a bad relational database design because it increases the storage required for the relation and it makes updating the relation more difficult.

? http://www.science.uva.nl/~kamps/RDB/, of ? http://www.science.uva.nl/~mdr/Teaching/RDB/0203/ • Practicum ? http://www.science.uva.nl/~borkur/teaching/RDB0203/ ? Tweede inleveropdracht is nagekeken... ? Deadline derde inleveropdracht 20 X 24 juni 2002!

4

Huiswerk

5

Huiswerk

7.1 ? Inability to represent information is a condition where a relationship exists among only a proper subset of the attributes in a relation. This is bad relational database design because all the unrelated attributes must be filled with null values otherwise a tuple without the unrelated information cannot be inserted into the relation. ? Loss of information is a condition of a relational database which results from the decomposition of one relation into two relations and which cannot be combined to recreate the original relation. It is a bad relational database design because certain queries cannot be answered using the reconstructed relation that could have been answered using the original relation.

7.3 Why are certain functional dependencies called trivial functional dependencies? ? Certain functional dependencies are called trivial functional dependencies because they are satisfied by all relations.

6

Huiswerk 7.5 Use the definition of functional dependency to argue that each of Armstrong’s axioms (reflexivity, augmentation, and transitivity) is sound. ? The definition of functional dependency is: α → β holds on R if in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that t1[α] = t2[α], it is also the case that t1[β] = t2[β]. ? Reflexivity rule: if α is a set of attributes, and β ⊆ α, then α → β. Assume t1 and t2 such that t1[α] = t2[α] t1[β] = t2[β] since β ⊆ α α→β definition of FD

7

Huiswerk 7.5 ? Augmentation rule: if α → β, and γ is a set of attributes, then γα → γβ. Assume ∃t1, t2 such that t1[γα] = t2[γα] t1[γ] = t2[γ] since γ ⊆ γα t1[α] = t2[α] since α ⊆ γα t1[β] = t2[β] definition of α → β t1[γβ] = t2[γβ] since γβ = γ ∪ β γα → γβ definition of FD ? Transitivity rule: if α → β and β → γ, then α → γ. Assume ∃t1, t2 such that t1[α] = t2[α] t1[β] = t2[β] definition of α → β t1[γ] = t2[γ] definition of β → γ α→γ definition of FD

8

9

Huiswerk

Huiswerk 7.12 Using the functional dependencies of Exercise 7.11,

7.9 Use Armstrong’s axioms to prove the soundness of the decomposition rule.

F = {A → BC,

• Decomposition rule: if α → βγ, then α → β and α → γ. α → βγ βγ → β α→β βγ → γ α→γ

CD → E,

B → D,

E → A}

compute B +.

given reflexivity rule transitivity rule reflexive rule transitive rule

• Computing B + by the algorithm in Figure 7.7 we start with 1. result = {B}. 2. Considering FDs of the form β → γ in F , we find that the only dependencies satisfying β ∈ result are B → B and B → D. Therefore result = {B, D}. 3. No more dependencies in F apply now. Therefore B + = {B, D}.

10

Huiswerk 7.16 Show that the following decomposition of the schema R = (A, B, C, D, E) of Exercise 7.2 is not a lossless-join decomposition:

11

A • Consider the following example of r = a1 a2 with R1 = (A, B, C) and R2 = (C, D, E).

B b1 b2

C c1 c1

C C c1 and ΠR2 (r) = c1 c1 c1

D d1 d2

E e1 e2

A • ΠR1 (r) = a1 a2

(A, B, C) (C, D, E).

B b1 b2

A a1 • ΠR1 (r) ./ ΠR2 (r) = a1 a2 a2

Hint: Give an example of a relation r on schema R such that ΠA,B,C (r) ./ ΠC,D,E (r) 6= r • Recall that F = {A → BC, CD → E, B → D, E → A}.

B b1 b1 b2 b2

C c1 c1 c1 c1

D d1 d2 d1 d2

D d1 d2

E e1 e2

E e1 e2 6= r. e1 e2

12

13

Huiswerk

Huiswerk 7.21 Give a lossless-join decomposition into BCNF of schema R = (A, B, C, D, E) of Exercise 7.2.

7.20 List the three design goals for relational databases, and explain why each is desirable.

• Recall that F = {A → BC, CD → E, B → D, E → A}.

• The three design goals are

1. result := R. Functional dependency B → D is nontrivial and (the only one) with a left hand side that is not a superkey (7.12). We replace R with R − {D} and {B, D}. 2. There is no more FD α → β on Ri such that α → Ri is not in F +.

1. lossless-join decompositions, 2. dependency preserving decompositions, and 3. minimization of repetition of information. They are desirable so we can maintain an accurate database, check correctness of updates quickly, and use the smallest amount of space possible.

By the algorithm of Figure 7.13 we derive the relations R0 = {(A, B, C, E), (B, D)}. This is in BCNF.

14

15

Huiswerk 7.23 In designing a relational database, why might we choose a nonBCNF design? • BCNF is not always dependency preserving. Therefore, we may want to choose another normal form (specifically, 3NF) in order to make checking dependencies easier during updates. This would avoid joins to check dependencies and increase system performance.

Huiswerk 7.24 Give a lossless-join, dependency-preserving decomposition into 3NF of schema R = (A, B, C, D, E) of Exercise 7.2. ? First we note that the dependencies given in Exercise 7.2, F = {A → BC,

CD → E,

form a canonical cover. ∗ C extraneous in CD → E? ∗ D extraneous in CD → E? ∗ B extraneous in A → BC? F 0 = {A → C, CD → E, B ∗ C extraneous in A → BC? F 0 = {A → B, CD → E, B

B → D,

No, C 6∈ D+. No, D 6∈ C +. No, B 6∈ A+ wrt → D, E → A}. No, C 6∈ A+ wrt → D, E → A}.

E → A},

16

Huiswerk

17

Database System Concepts — Hoofdstuk 10

7.24 ? Generating the schema from the algorithm of Figure 7.14: ∗ A → BC gives R1 = (A, B, C); ∗ CD → E gives R2 = (C, D, E); ∗ B → D gives R3 = (B, D); and ∗ E → A gives R4 = (E, A). ? Since, e.g., schema R1 contains a candidate key for R, we get

Over XML. • eXtensible Markup Language • gebaseerd op Hyper-Text Markup Language (HTML) • ideaal formaat voor data uitwisseling

R0 = {(A, B, C), (C, D, E), (B, D), (E, A)}.

• een van de Internet standaarden

Therefore R0 is a third normal form dependency-preserving lossless-join decomposition. ? Note that the original schema R = (A, B, C, D, E) is already in 3NF.

18

19

20

21

22

23

24

25

26

27

28

29

30

31

Searching XML Documents • DB approach: semi-structured data ? Exist various ways to map XML data onto relational DBs ? Queries (XPath and XQuery) are mapped to SQL queries • Information Retrieval approaches ? Go beyond boolean matching ? Give a ranked list of results • XML-IR is a mixture of DB and IR

XML Retrieval • Document structure ? In IR a document is a bag-of-words ? In XML-IR a document is considered as tree of words • Unit of retrieval ? In IR only whole documents can be retrieved ? In XML-IR every XML-element is a retrievable unit • Query format ? IR queries are in natural language ? XML-IR queries may have information on structure

32

33

Stof voor Tentamen

Oud Tentamen • Tentamen van 10 juli 2002.

• Stof = Database System Concepts ? ? ? ? ? ? ? •

H H H H H H H

Relationele Databases IW199113 Woensdag 10 juli 2002, 09.30–12.30 uur

1 2 3 (§1-5) 4 6 7 (§1-7) 10 (§1-2)

Zaal P.227 (Plantage Muidergracht 24) U kunt de tentamenzaal op zijn vroegst 15 minuten na aanvang van het tentamen verlaten. Dit is geen open boek tentamen. Mobiele telefoons, organizers, en andere electronica zijn niet toegestaan. Aanwezigheid van dergelijke apparatuur leidt tot onmiddellijke uitsluiting. Schrijf duidelijk en beknopt, maar geef uitleg waar nodig. Vermeld naam, cursus, en collegekaartnummer op ieder vel papier dat u inlevert. Antwoorden mogen in het Nederlands of Engels gegeven worden.

Vragen?

De waardering voor ieder onderdeel staat vermeld tussen rechte haken aan het slot van het onderdeel. De maximale totale score is 100; voor een voldoende dient u 50 punten te behalen.

34

1. Dit is een algemene vraag over verschillende aspecten van relationele databases. i. Wat is, in de theorie van relationele databases, het verschil tussen de termen relatie en relatie schema? [3] ii. Noem twee belangrijke nadelen van een database systeem. [3] iii. Wat is het verschil tussen fysieke en logische data onafhankelijkheid? [3] iv. Noem twee belangrijke verschillen tussen de relatie-algebra en SQL. [3] v. Noem twee redenen voor het defini¨eren van views. [3] vi. Waarom noemen we sommige functionele afhankelijkheden triviale functionele afhankelijkheden? [3] vii. Leg uit wat er bedoeld wordt met herhaling van informatie en met het onvermogen om informatie te representeren. Leg uit waarom deze eigenschappen op een slecht databaseontwerp kunnen wijzen. [3] viii. Wat is een lossless-join decomposition van een relatieschema? [3]

35

2. Deze vraag gaat over het entity-relationship (E-R) model. i. Bij het ontwerpen van een E-R diagram voor een bepaalde domein, dienen zich vaak verschillende alternatieven aan. Welke criteria hanteert u bij het maken van de geschikte keuze? [5] ii. NoTown Records heeft besloten een database op te zetten van de musici die op hun CDs spelen. Elke musicus die bij NoTown meewerkt aan opnames heeft een SOFI-nummer, een adres, en een telefoonnummer. Minder bedeelde musici delen soms een adres, en geen adres heeft meer dan ´e´en telefoonnnummer. Elk instrument dat gebruikt wordt in een opname van een song bij NoTown heeft een naam (bijvoorbeeld, gitaar, synthesizer). Elke CD die wordt opgenomen onder het NoTown label heeft een titel, een copyright datum, en een CD-identifier. Elke song opgenomen bij NoTown heeft een titel en een auteur. • Een musicus kan meerdere instrument bespelen, en een gegeven instrument kan bespeeld door meerdere door musici. • Op elke CD staat een aantal songs, maar geen song staat op meer dan ´e´en CD. • Elke song wordt uitgevoerd door ´e´en of meer musici, en een musicus kan aan meer dan ´e´en song meewerken als uitvoerder. • Een CD heeft precies ´e´en musicus die optreedt als producent. Een musicus kan uiteraard meerdere CDs produceren. Ontwerp een E-R diagram voor NoTown Records. Identificeer duidelijk de entity sets en relationship sets die u gebruikt. Geef ook duidelijk aan welke primary keys u gebruikt, en welke cardinality constraints u hanteert. Geef tenslotte aan welke randvoorwaarden op de gegevens u niet kunt uitdrukken in uw E-R diagram, en waarom niet. [21]

36

3. Deze vraag gaat over de relatie tussen E-R diagrammen en relationele tabellen. In elk van de volgende onderdelen wordt u gevraagd SQL-uitdrukkingen (CREATE TABLE) te geven die de informatie uit een bijbehorend E-R diagram vastleggen. Neem zowel domain constraints als key informatie op! (Het verdient aanbeveling om allereerst E-R diagrammen te tekenen van de beschrijvingen die hieronder gegeven worden.) i. Een entity set: Bekijk de Employee entity set met attributen ssn (primary key), name, en lot. [5] ii. Een relationship set (zonder cardinality constraints): Bekijk de relation ship set Reports To op de Employee entity set uit het vorige onderdeel. Reports To kent twee rollen: supervisor en subordinate. [5] iii. Een relationship set met een cardinality constraints: Bekijk om te beginnen de Employee entity set uit onderdeel (i). Bekijk daarnaast een nieuwe entity set Departments (met als attributen did (primary key), dname, en budget). En bekijk tenslotte Manages als relationship set tussen Employee en Department, waarbij since een attribuut is van Manages en elke department ten hoogste ´e´en manager heeft. [7] iv. Een weak entity set: Bekijk opnieuw de Employee entity set uit onderdeel (i), maar nu samen met de weak entity set Dependents met attributen pname (partial key) en age. Daarnaast is er een relation ship set Policy. Een Dependents entity kan alleen uniek ge¨ıdentificeerd worden als we de via Policy de key van de bijbehorende Employee entity nemen samen met de partial key pname van de Dependents entity. Een Dependents entity moet verwijderd worden als de bijbehorende Employee entity verwijderd wordt. [8]

37

4. Deze vraag gaat over afhankelijkheden. i. Wat is de afsluiting α+ van een verzameling attributen α? [3] ii. Een bekend algoritme voor het berekenen van de afsluiting α+ van een verzameling attributen α gaat als volgt: closure = α; repeat until there is no change { if there is a functional dependency β → γ with β ⊆ closure, then set closure = closure ∪ γ } Beargumenteer dat dit algoritme correct is. [10] iii. Hoe kan het berekenen van de afsluiting van ´e´en of meerdere verzamelingen attributen helpen om superkeys van een relatieschema te bepalen? [2] iv. Gegeven is de volgende verzameling F van functionele afhankelijkheden voor het relatieschema R = (A, B, C, D, E): A → DE CD → B E→C B→A Geef de candidate keys voor R. [10]

38

5. Deze vraag gaat over normaalvormen. i. Wat is het verschil tussen BCNF en 3NF? [5] ii. Bekijk het Sport relatieschema Sport(speler, team, trainer), en laat verder de volgende afhankelijkheden gegeven zijn: trainer → team (speler, team) → trainer Laat zien dat het Sport relatieschema in 3NF is. [5] iii. Laat zien dat het relatieschema in (ii) niet in BCNF is. [5] iv. Geef een lossless-join decompositie van het Sport relatieschema in BCNF. [10]

39

Overzicht Vandaag • Database System Concepts. ? XML (Hoofdstuk 10, §10.1–§10.2). • Opgaven: ? 7.1, 7.3, 7.5, 7.9, 7.12, 7.16, 7.20, 7.21, 7.23, en 7.24 • Vragen?

VEEL SUCCES!!!

• Hoe ziet een tentamen eruit?

40

Tentamen Relationele Databases • Tentamen ? 8 juli 2003 van 9.30 - 12.30 in zaal M.C3 • Stof = Database System Concepts ? ? ? ? ? ? ?

H H H H H H H

1 2 3 (§1-5) 4 6 7 (§1-7) 10 (§1-2)

41

End!