update anomalies:
insertion anomalies
deletion anomalies
modification anomalize
functional dependency: describles the relationship between attributes in a relation. for example, if A and B are attribute of reltion R, B is functionally dependent on A (denoted A->B), if each value of A is associated with eactly one value of B (A and B may each consist of one or more attributes.)
B is functionally dependent on B
A functionally determines B
functional dependency is specified as a constraint between the attributes.
determinant: refers to the attribute, or group of attributes, on the left_hand side of the arrow of a functional dependency.
full functional dependency: indicates that if A and B are attributes of a relation, B is fully functionally dependent on A if B is functionally dependent on A, but not on any proper subset of A.
partially dependency: if there is some attribute that can be removed from A and yet the dependency still holds.
there are two kind of functional dependency:
one-to-one relationship: full functional dependency
many-to-one relationship: partially dependecy
transitive dependency: a condition where A, B and C are attributes of a relation such that if A->B and B->C, then C is transitively dependent on A via B
the main purpose of identifying a set of functional dependencies for a relation is to specify the set of intergrity constraints that must hold on a relation.
hence, we see that an essential characteristic for a candidate key of relation is that the attribute of a determinant either individually or working together must be able to functionally determine all the other attribute in the relation.
the concepts of functional dependencies and keys are central to the process of normalization.
normalization is a formal technique for analyzing relations based on their primary key(or candidate keys) and functional dependencies.
UNF: a table that contains one or more repeating groups
1NF: a relation in which the intersection of each row and column contains one and only one value.
2NF: a relation that is in 1NF and every non_cabdidate_key attribute is fully functionally dependent on the candidate key.
if a partial dependency exists, we remove the partially dependent attributes from the relation by placing them in a new relation along with a copy of their determinant.
3NF: a relation that is in 1NF and 2NF and in which no non-candidate-key attribute is candidate dependent on the primary key.
if a transitive dependency exists, we remove the transitively dependent attributes from the relation by placing the attributes in a new relation along with a copy of the determinant.
redendancy is often caused by a functional dependency. each normal form has fewer FDs than the last. since FDs represent redundancy, each normal form has less redundancy than the last.
properties of FDs
the primary key FDs any set of attributes in that relation. same for candidate key.
any set of attributes is FD on itself.
relues for FDs
reflexivity: if B is a subset of A then: A->B
augmentation: if A->B then: A U C -> B U C
transitivity: if A->B and B->C then A->C
removing FDs:
suppose we have a relation R with scheme S and the FD A->B where A^B ={}
let C = S - (A U B): all other attributes not in A and B
it turns out that we can split R into two parts: R1, with scheme C U A ; R2, with scheme A U B
the orginal relation can be recovered as the natural join of R1 and R2: R=R1 NATURAL JOIN R2.
self-determination: A->A
Decomposition: if A->B,C, then A->B and A->C
Union: if A->B and A->C, then A->B,C
Composition: if A->B and C->D then A,C->B,D
a set of functional dependency X is minimal if it satisfy the following conditions:
every dependency in X has a single attribute on its right-hand side.
We can not replace any dependency A->B in X with dependency C->B, where C is a proper subset of A, and still have a set of dependencies that is equivalent to X
we cannot remove any dependency from X and still have a set of dependencies that is equivalent to x.
transitive FDs
a FD, A->C is a transitive FD, if there is some set B such that A->B and B->C are non-trivial FDs.
A->B non-trivial means: B is not a subset of A
to normalise a relation, we used projection. if R(A,B,C) satisfies A->B then we can project it on A,B and A,C without losing information.
when is decomposition is not lossless: no FD
BCNF: a relation in BCNF if for every FD A->B either B is contained in A(the FD is trivial), or A contains a candidate key of the relation. in other words: every determinant in a non-trivial dependency is a (super) key. If there is only one cadidate key then 3NF and BCNF are the same one.
normalisation to 3NF is always lossless and dependency preserving.
normalisation to BCNF is lossless, may not preserve dependency.
Wednesday, 9 May 2007
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment