• Week 07 Thursday
• Relational Design Theory
• Relational Design and Redundancy
• Exercise: Update Anomalies
• Update Anomalies
• Avoiding Update Anomalies
• Notation/Terminology
• Database Design (revisited)
• Functional Dependency
• Identifying Functional Dependencies
• Exercise: Functional Dependencies (1)
• Exercise: Functional Dependencies (2)
• Exercise: Functional Dependencies (2)
• Exercise: Functional Dependencies (3)
• Functional Dependency
• Inference Rules
• Closures
• Exercise: Determining Keys

❖ Week 07 Thursday

In today's lecture ...

• Python/psycopg2,   Relational Design Theory

Things to do ...

• Quiz 4 due by 23:59 Friday 28 October
• Assignment 2 due by 21:00 Friday 11 November  (Week 9)
• Play with the  ass2  database and Python/psycopg2

❖ Relational Design Theory

We know how to express ER data models and SQL schemas

But how do we know that our models/schemas are "good"?

Properties of "good" models/schemas

• accurate ... represent scenario faithfully
• complete ... represent all aspects of a scenario
• minimal ... minimise stored data; no redundancy

Relational design theory addresses the last issue

Relies on the notion of functional dependency

❖ Relational Design Theory (cont)

Functional dependencies

• describe relationships between attributes within  a relation

What we study here:

• basic theory and definition of functional dependencies
• methodology for improving schema designs (normalisation)

The aim of studying this:

• improve understanding of relationships among data
• gain enough formalism to assist practical database design

❖ Relational Design and Redundancy

In database design, redundancy is generally a "bad thing":

• makes it difficult to maintain consistency after updates

Our goal is to reduce redundancy in stored data

• by ensuring that the schema is structured appropriately

But ... redundancy may have some advantages

• e.g. give performance improvements
  (by avoiding joins to collect bits of related data together)

❖ Relational Design and Redundancy (cont)

Consider the following relation defining bank accounts/branches:

accountNo	balance	customer	branch	address	assets
A-101	500	1313131	Downtown	Brooklyn	9000000
A-102	400	1313131	Perryridge	Horseneck	1700000
A-113	600	9876543	Round Hill	Horseneck	8000000
A-201	900	9876543	Brighton	Brooklyn	7100000
A-215	700	1111111	Minus	Horseneck	400000
A-222	700	1111111	Redwood	Palo Alto	2100000
A-305	350	1234567	Round Hill	Horseneck	8000000

Careless updating of this data may introduce inconsistencies.

❖ Exercise: Update Anomalies

Show what happens when the following changes occur:

• add a new account (A-306,100,2424242,Round Hill)
  

• change the address of the Round Hill branch to San Jose
  

• close the account A-201

❖ Update Anomalies

Insertion anomaly:

• when we insert a new record, we need to check that branch data is consistent with existing tuples

Update anomaly:

• if a branch changes address, we need to update all tuples referring to that branch

Deletion anomaly:

• if we remove information about the last account at a branch, all of the branch information disappears

Insertion/update anomalies are avoidable, but need extra DBMS work

❖ Avoiding Update Anomalies

Redundancy in stored data can lead to update anomalies

Functional dependencies allow us to

• reason about relationships between attributes
• identify redundancies (at schema level)

Normalization methods allow us to

• transform a schema to remove redundancy

Note: most algorithms for normalization are non-deterministic

• multiple different correct solutions are possible

❖ Notation/Terminology

Most texts adopt the following terminology:

Relation schemas		upper-case letters, denoting set of all attributes (e.g. R, S, P, Q )
Relation instances		lower-case letter corresponding to schema (e.g. r(R), s(S), p(P), q(Q) )
Tuples		lower-case letters   (e.g. t, t', t1, u, v )
Attributes		upper-case letters from start of alphabet (e.g. A, B, C, D )
Sets of attributes		simple concatenation of attribute names (e.g. X=ABCD, Y=EFG )
Attributes in tuples		tuple[attrSet] (e.g. t[ABCD], t[X])

❖ Database Design (revisited)

To avoid update anomalies, normalization should give:

• a schema with "minimal overlap" between tables
• each table contains a "coherent" collection of data values

Normalization typically involves

• decompose a relation based on FDs
• R → R₁  and R₂, where R₁ ∪ R₂ = R  and  R₁ ∩ R₂ ≠ ∅
• repeat decomposition until no more decomposition is possible

Finally, each R_i  contains info about one entity (e.g. branch, customer, ...)

❖ Database Design (revisited) (cont)

But we already have a design procedure (ER-then-relational)

• and it appears to produce schemas without redundancy

Why do we need another design procedure?

1. ER → Relational does not guarantee no redundancy
   • dependency theory allows us to check designs for residual problems
2. the new procedure gives (semi)automated design
   • determine all of the attributes in the problem domain
   • collect them all together in a "universal relation"
   • provide information about how attributes are related
   • apply normalisation to decompose into non-redundant relations

❖ Functional Dependency

A relation instance r(R) satisfies a dependency X → Y if

• for any t, u ∈ r,   t[X] = u[X]   ⇒   t[Y] = u[Y]

In other words, if two tuples in R agree in their values for the set of attributes X, then they must also agree in their values for the set of attributes Y.

We say that "Y is functionally dependent on X".

Attribute sets X and Y may overlap; trivially true that X → X.

Notes:

• X → Y can also be read as "X determines Y"
• the single arrow → denotes functional dependency
• the double arrow ⇒ denotes logical implication

❖ Identifying Functional Dependencies

Consider an instance r(R) of the relation schema R(ABCDE):

A	B	C	D	E
a1	b1	c1	d1	e1
a2	b1	c2	d2	e1
a3	b2	c1	d1	e1
a4	b2	c2	d2	e1
a5	b3	c3	d1	e1

What dependencies can we observe among its attributes?

❖ Identifying Functional Dependencies (cont)

Since A values are unique, the definition of fd gives:

• A → B,    A → C,    A → D,    A → E
• A → BC,    A → CD,   ...   A → BCDE
• can be summarised as   A → BCDE

Since all E values are the same, it follows that:

• A → E,    B → E,    C → E,    D → E
• in general, cannot be summarised as   ABCD → E
  

❖ Identifying Functional Dependencies (cont)

Other observations:

• combinations of BC are unique, therefore   BC → ADE
• combinations of BD are unique, therefore   BD → ACE
• if C values match, so do D values, therefore   C → D
• however, D values don't determine C values, so   !(D → C)

We could derive many other dependencies, e.g.   AE → BC, ...

In practice, choose a minimal set of fds (basis)

• from which all other fds can be derived
• which captures useful problem-domain information

❖ Exercise: Functional Dependencies (1)

Real estate agents conduct visits to rental properties

• need to record which property, who went, when, results
• each property is assigned a unique code (P#, e.g. P4)
• each staff member has a staff number (S#, e.g. S43)
• staff members use company cars to conduct visits
• a visit occurs at a specific time on a given day
• notes are made on the state of the property after each visit

The company stores all of the associated data in a spreadsheet.

❖ Exercise: Functional Dependencies (1) (cont)

Describe any functional dependencies that exist in this data:

P# | When        | Address    | Notes         | S#  | Name  | CarReg
----+-------------+------------+---------------+------+-------+-------
P4 | 03/06 15:15 | 55 High St | Bathroom leak | S44 | Rob   | ABK754
P1 | 04/06 11:10 | 47 High St | All ok        | S44 | Rob   | ABK754
P4 | 03/07 12:30 | 55 High St | All ok        | S43 | Dave  | ATS123
P1 | 05/07 15:00 | 47 High St | Broken window | S44 | Rob   | ABK754
P1 | 05/07 15:00 | 47 High St | Leaking tap   | S44 | Rob   | ABK754
P2 | 13/07 12:00 | 12 High St | All ok        | S42 | Peter | ATS123
P1 | 10/08 09:00 | 47 High St | Window fixed  | S42 | Peter | ATS123
P3 | 11/08 14:00 | 99 High St | All ok        | S41 | John  | AAA001
P4 | 13/08 10:00 | 55 High St | All ok        | S44 | Rob   | ABK754
P3 | 05/09 11:15 | 99 High St | Bathroom leak | S42 | Peter | ATS123

State assumptions used in determining the fds.

❖ Exercise: Functional Dependencies (2)

Consider this data (possibly from a spreadsheet):

   id   |     name        |   subj   | term |      title      | mark | grade 
--------+-----------------+----------+------+-----------------+------+-------
5123485 | Lillian Seng... | COMP9020 | 17s1 | Foundations ... |      | AF
5123485 | Lillian Seng... | COMP9021 | 17s2 | Principles o... |   46 | FL
5123485 | Lillian Seng... | COMP9020 | 18s1 | Foundations ... |   44 | FL
5123485 | Lillian Seng... | COMP9021 | 18s2 | Principles o... |   46 | FL
5123504 | Yap Huawen      | MATH5960 | 17s1 | Bayesian Inf... |   56 | PS
5123504 | Yap Huawen      | COMP9318 | 17s1 | Data Warehou... |   76 | DN
5123504 | Yap Huawen      | COMP9444 | 17s2 | Neural Netwo... |   53 | PS
5123504 | Yap Huawen      | COMP9814 | 18s1 | Ext Artifici... |      | NF
5123504 | Yap Huawen      | COMP6714 | 18s2 | Info Retriev... |   86 | HD
5123523 | Cindy Nava G... | COMP9313 | 17s1 | Big Data Man... |   55 | PS
5123523 | Cindy Nava G... | COMP9444 | 17s2 | Neural Netwo... |   63 | PS
5123523 | Cindy Nava G... | COMP9417 | 18s1 | Machine Lear... |      | AW
5123523 | Cindy Nava G... | COMP9318 | 19T1 | Data Warehou... |   43 | FL
5123523 | Cindy Nava G... | COMP6714 | 19T3 | Info Retriev... |      | AW
5123523 | Cindy Nava G... | COMP9321 | 20T1 | Data Service... |      | SY

Identify functional dependencies

❖ Exercise: Functional Dependencies (2)

What functional dependencies exist in the following table:

  A  |  B  |  C  |  D
-----+-----+-----+-----
  1  |  a  |  6  |  x
  2  |  b  |  7  |  y
  3  |  c  |  7  |  z
  4  |  d  |  6  |  x
  5  |  a  |  6  |  y
  6  |  b  |  7  |  z
  7  |  c  |  7  |  x
  8  |  d  |  6  |  y

How is this case different to the previous ones?

❖ Exercise: Functional Dependencies (3)

What functional dependencies exist in the following table:

  A  |  B  |  C  |  D
-----+-----+-----+-----
  1  |  a  |  6  |  x
  2  |  b  |  7  |  y
  3  |  c  |  7  |  z
  4  |  d  |  6  |  x
  5  |  a  |  6  |  y
  6  |  b  |  7  |  z
  7  |  c  |  7  |  x
  8  |  d  |  6  |  y

How is this case different to the previous ones?

❖ Functional Dependency

Above, we considered dependency within a relation instance r(R).

More important for design is dependency across all possible instances of the relation (i.e. a schema-based dependency).

This is a simple generalisation of the previous definition:

• for any t, u ∈ any r(R),   t[X] = u[X]   ⇒   t[Y] = u[Y]

Such dependencies capture semantics of problem domain.

E.g. course enrolment example

❖ Functional Dependency (cont)

Can we generalise some ideas about functional dependency?

E.g. are there dependencies that hold for any  relation?

• yes, but they're generally trivial, e.g. Y ⊂ X   ⇒   X → Y

E.g. do some dependencies suggest the existence of others?

• yes, rules of inference allow us to derive dependencies
• allow us to reason about sets of functional dependencies

❖ Inference Rules

Armstrong's rules are general rules of inference on fds.

F1. Reflexivity   e.g.   X → X

F2. Augmentation   e.g.   X → Y  ⇒  XZ → YZ

F3. Transitivity   e.g.   X → Y, Y → Z  ⇒  X → Z

F4. Additivity   e.g.   X → Y, X → Z   ⇒   X → YZ

F5. Projectivity   e.g.   X → YZ   ⇒   X → Y, X → Z

F6. Pseudotransitivity   e.g.   X → Y, YZ → W   ⇒   XZ → W

F1 - F3 are essential; the rest are useful to have

❖ Inference Rules (cont)

Example: determining validity of AB → GH, given:

Derivation:

❖ Closures

Given a set F of fds, how many new fds can we derive?

For a finite set of attributes, there must be a finite set of derivable fds.

Closure = F⁺  = largest collection of dependencies derivable from F

Closures allow us to answer two interesting questions:

• is a particular dependency X → Y derivable from F?
• are two sets of dependencies F and G equivalent?

❖ Closures (cont)

For the question "is X → Y derivable from F?" ...

• compute the closure F⁺; check whether X → Y   ∈   F⁺

For the question "are F and G equivalent?" ...

• compute closures F⁺ and G⁺; check whether they're equal

Unfortunately, closures can be very large, e.g.

R = ABC,     F = { AB → C,   C → B }
F⁺ = { A → A,   AB → A,   AC → A,   AB → B,   BC → B,   ABC → B,  
            C → C,   AC → C,   BC → C,   ABC → C,   AB → AB,   . . . . . . ,
            AB → ABC,   AB → ABC,   C → B,   C → BC,   AC → B,   AC → AB }

❖ Closures (cont)

Algorithms based on F⁺ rapidly become infeasible.

To solve this problem ...

• use closures based on sets of attributes rather than sets of fds.

Given a set X of attributes and a set F of fds, the closure of X (denoted X⁺) is

• the largest set of attributes that can be derived from X using F

We can prove (using additivity) that    (X → Y) ∈ F⁺   iff   Y ⊂ X⁺.

For computation purposes, |X⁺| is bounded by the number of attributes.

❖ Closures (cont)

For the question "is X → Y derivable from F?" ...

• compute the closure X⁺, check whether Y   ⊂   X⁺

For the question "are F and G equivalent?" ...

• for each dependency in G, check whether derivable from F
• for each dependency in F, check whether derivable from G
• if true for all, then F ⇒ G and G ⇒ F which implies F⁺ = G⁺

For the question "what are the keys of R implied by F?" ...

• find subsets K ⊂ R such that K⁺ = R

❖ Exercise: Determining Keys

Determine possible primary keys for each of the following:

1. FD  =  { A → B, C → D, E → FG }
2. FD  =  { A → B, B → C, C → D }
3. FD  =  { A → B, B → C, C → A }
4. FD  =  { AB → C,   C → B }
5. FD  =  { MN → P, NP → Q, Q → R }
6. FD  =  { ABH → C, A → DE, BGH → F, F → ADH, BH → GE }
7. FD  =  { ABH → C, A → D, C → E F → A, E → F, BGH → E }