Week 3 Flashcards
What is the functional dependency theory?
It quantifies the degree of “goodness”.
X uniquely determines Y holds if whenever two tuples have the same value for X, they must have the same value for Y.
Definition: for any two tuples t1 and t2 in the relation R:
if t1[X]=t2[X] then t1[Y] = t2[Y]
What is the Normalization Theory?
It is for transforming a relational schema into a set of “good” and “efficient” relations.
What is the Boyce-Codd Normal Form (BCNF)?
We can transform any relation into this.
What metrics are used to judge whether we are dealing with a good relational schema?
1) goodness - whether the attributes (e.g. FK/PK) for a “good” relation
2) quantify the degree of goodness
3) What pitfalls exist?
4) efficiency in insert/delete/update operations
5) convey as much info as possible minimising redundancy (minimise repetition of data)
What are the four guidelines for a good design?
1) the attributes of a relation should make sense (and reflect the context of entities!)
2) avoid redundant tuples: it can be costly for storage, we might have inconsistency
3) Relations should have as few NULL values as possible - avoids wasting storage.
4) Design relations to avoid fictitious tuples after join - i.e. tuples that weren’t there before.
What is the definition of the join algorithm?
For each tuple q in Q, join with each tuple p in P iff q.Plocation=p.Plocation.
Result: r=(p,q).
Challenge: once p and q have been split into sub relations, we need to be careful not to create fictitious tuples when rejoining back.
Functional Dependency Lemma: if K is a candidate key, then…
K functionally determines all attributes in relation R, i.e.
FD: K -> {R}
What is the transitive characteristic of functional dependency?
If X–> Y (i.e X functionally determines Y) and Y–> Z, then X–> Z
If we have functional dependencies, can we derive the candidate key(s) of a relation?
yes. Use transitive characteristics of functional dependencies to figure out the candidate keys.
What is the theory of normalisation?
Progressive decomposition of unsatisfactory relations by breaking up their attributes into smaller “good” relations.
What is a prime attribute?
An attribute that belongs to some candidate key of the relation.
What is a non-prime attribute?
It’s not a prime attribute, i.e. it is not a member of any candidate key
What is the first normal form?
The domain Di of each attribute Ai in a relation R refers only to atomic (simple/indivisible) values.
1NF disallows:
- nested attributes
- multivalued attributes: you have to introduce new tuples. Not a good relation though because you’ll get lots of duplicates.
What is the second normal form?
Assume that X is the primary key.
Definition: full functional dependency X on Y means that if we remove any prime attribute A from the primary key X, then:
X{A} is not a FD on Y.
“Full” FD means that we need both primary keys in the composite PK.
“Partial” FD means that we can take one of the PKs and it will determine the attribute Y.
Defn of 2NF: a relation R is in 2NF if every non-prime attribute A in R is fully functionally dependent on the primary key of R.
How do we move from 1NF to 2NF?
We need to remove all prime attributes from the primary key, which cause partial dependencies.
Methodology:
1) Identify all the partial FDs in the original relation.
2) For each partial FD, create a new relation such that all non-prime attributes in there are fully functionally dependent on the new primary key:
i.e. the prime attribute in the original relation causing partial FDs.
3) The relation will be 2NF.
