Normalization Slides Modul3

Normalisation

The process of making a good schema design. A set of principles + methodologies.

Normalisation in practice: objective + constraint

Objective: Generate tables whose attributes depend on the complete primary key and nothing else.

Constraint: Maintain all dependencies between attributes in a database decomposition.

Attribute dependencies är samma som Functional dependencies

Functional dependencies (FD) - Definition + what does that mean in a relational model?

Two attributes and have a functional dependency

X →Y iff

‣There exists a function (binary relation) between X and Y.

‣i.e. f(x) = y where for y ∈Y ∀x∈X .

‣In the relational model that means for ANY instance of R, r(R)

‣given r1, r2 ∈ r(R) : r1.X = r2.X ⟹ r1.Y = r2.Y

Define Superkey as FDs

A superkey is any attribute set K of R(A1….An) for which there exists:

• Fk K —> {A1, …., An}

Define Candidate Keys as FDs

A candidate key is any attribute set K of R(A1….An) for those whose |K| is minimal (irreducable).

Define Primary Keys as FDs

The one candidate key chosen by the designer

Define F+ (Closure of F)

Given a set of FDs we can systematically compute ALL implied FDs.

(den "totala mängden" av alla funktionella beroenden som logiskt kan härledas från den ursprungliga mängden F. Du kan förstå det som: F är de "råvaror" eller "grundregler" du har, och F⁺ är alla "sanningar" som dessa råvaror kan generera.)

Ex om F har två regler: A → B och B→C så kan vi med transistivitet härleda A→C.

Vad menas med att F ⊨ X→Y (att F implicerar det funktionella beroendet X→Y)?

Att X→Y ∈ F+

, dvs. att varje relationstillstånd (extension) r(R) som satisfierar alla funktionella beroenden i F också satisfierar X→Y.

Armstrong’s axioms: Regler för att ta fram F+ givet X, Y, Z

Reflexiv

Augmentation

Transistive

Decomposition

Union

Pseudo-transistive

Vad innebär 1st Normal Form (1NF)

Att attributen är atomära (inga mängder/sets eller sammansatta värden).

Vad är villkoret för att en tabell ska vara i 2nd Normal Form (2NF)?

• Tabellen måste vara i 1NF

• Inga icke-primära attribut Y får bero på en äkta delmängd Z ⊂ X av en kandidatnyckel X (Z → Y ∉ F^+)

Vad är villkoret för att en tabell ska vara i 3rd Normal Form (3NF)?

Tabellen måste vara i 2NF, och alla icke-primära attribut Y måste definieras direkt av en kandidatnyckel (inga transitiva beroenden, d.v.s. om X → Y ∈ F^+ så måste X vara en kandidatnyckel).

Vad innebär Lossless Decomposition (förlustfri dekomposition)?

Att en relation R kan delas upp i deltabeller utan att någon information går förlorad, vilket garanteras av bland annat Heath's Theorem om X → Y ges.

Vilka tre egenskaper kännetecknar en Canonical Cover (minimal cover) G av en mängd funktionella beroenden F?

1. Canonical Form: För varje {X → A} ∈ G är A ett enskilt attribut (|A| = 1).

2. Irreducibility: För varje {X → A} kan X inte reduceras till en äkta delmängd Y ⊂ X.

3. No Redundancy: Ingen funktionell ett-till-ett-regel kan tar bort utan att G förlorar sin ekvivalens med F(+ closure).

Vad innebär det att en mängd funktionella beroenden F är covered (täckt) av en annan mängd E?

E+ ⊨ F, dvs att varje funktionellt beroende i F kan härledas från E+.

Insert Anomaly, Update Anomaly, Deletion Anomaly

• Insert Anomaly (Inmatningsanomali):

  • Man kan inte lägga till information om en entitet utan att samtidigt lägga till en annan.

  • Exempel: Det går inte att registrera en ny författare eller ett nytt förlag i databasen förrän de har kopplats till en specifik bok med ett unikt ISBN.

• Update Anomaly (Uppdateringsanomali):

  • Samma data lagras på flera ställen, vilket gör att en ändring måste utföras på flera rader för att undvika inkonsekvens.

  • Exempel: Om ett förlag byter namn måste namnet uppdateras manuellt på varje rad där en bok utgiven av förlaget förekommer.

• Deletion Anomaly (Borttagningsanomali):

  • När en rad tas bort försvinner oavsiktligt annan värdefull information.

  • Exempel: Om den sista boken av en viss författare raderas från tabellen försvinner även all data om den författaren ur systemet.

Heath’s Theorem

Om en relation R har ett funktionellt beroende X → Y, så är uppdelningen i R1(X U Y) och R2(R — Y) garanterat förlustfri (lossless).