Wednesday, 9 May 2007

normalization

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.

Physical DB Issues

LECTURE_13

E/R modelling helps find the requirements of a database
Normalisation helps to refine a design by removing data redundancy
Physical design Concerned with storing and accessing the data

RAID - redundant array of independent (inexpensive) disks
Storing information across more than one physical disk
Speed - can access more than one disk
Robustness - if one disk fails it is OK

RAID Level 0 : Files are split across several disks
For a system with n disks, each file is split into n parts, one part stored on each disk
Improves speed, but no redundancy

RAID Level 1: As RAID 0 but with redundancy
Files are split over multiple disks
Each disk is mirrored
For n disks, split files into n/2 parts, each stored on 2 disks
Improves speed, has redundancy(in two disks), but needs lots of disks

Parity Checking: for a set of data in binary form we count the number of 1s for each bit across the data. If this is even the parity is 0, if odd then it is 1. We can use parity checking to reduce the number of disks ---------????????how to reduce the number of disk
Recovery With Parity: If one of our pieces of data is lost we can recover it.

RAID Level 3: Data is striped over disks, and a parity disk for redundancy
For n disks, we split the data in n-1 parts
Each part is stored on a disk
The final disk stores parity information for recovery

Indexes:
Types of indexes
Primary or clustered indexes affect the order that the data is stored in a file
Secondary indexes give a look-up table into the file
Only one primary index, but many secondary ones

Choosing Indexes: only have one primary index. The most frequently looked-up value is often the best choice. Some DBMSs assume the primary key is the primary index, as it is usually used to refer to rows
Don’t create too many indexes: They can speed up queries, but they slow down inserts, updates and deletes. Whenever the data is changed, the index may need to change

Creating Indexes:

Query Processing:

Three main stages

Parsing and translation - the query is put into an internal form

relational operators: PRODUCT,SELECTION, PROJECTION,

Optimisation - changes are made for efficiency
Evaluation - the optimised query is applied to the DB

----------P31??????????????????, why 15 operantions