Database Constraints and Normalization

 

Integrity Constraints and Domain Constraints

Integrity Constraints

-Integrity constraints are the rules enforced in the data so as to assure accuracy and consistency of data in a relational database.
- It ensures that the changes made to the database by authorized users do not result in a loss of data consistency. -There are four types of integrity constraints as follows:-
1. Domain Integrity
2. Entity integrity
3. Referential integrity
4. Foreign Key integrity

---

Domain Integrity

-It states the set of values for an attributes must be a valid definition.
-An attribute can be defined with :
data TYPES
Length
Allowance of null value
Default value
Value range
-It ensures that a specific attribute will have a right and proper value.

---

Entity Integrity

-It states that primary keys can not be null.
-As primary key is used to identify individual rows in a table,it cannot be null and must have proper values.

Referential Integrity
-It satisfies integrity constraints between two tables.
-It ,maintains consistency among rows between two tables.
-The rules are as follows:
1. A record from a primary table can not be deleted if matching records exist in a related table.
2. A primary key value in a primary table can not be changed if that record has related records.
3. A foreign key value in a related table that cannot be inserted if it does not exist in primary key of primary table.
4. A null value can be entered in foreign key specifying that the records are unrelated.

---

Foreign Key Integrity

-It contains two constraints .
-Cascade update related field: whenever there is change in primary key of a row in primary table, the foreign keys are updated in the matching rows of related tables.
-Cascade delete related row:whenever there is deletion of a row in primary table,the matching rows are automatically deleted in the related table.

---

Assertions and Triggering

Assertions

-Assertions are the statement that ensures certain conditions must always be true and must remain true, otherwise the database modification is rejected.
-It is defined independent of table.
-It is activated whenever modification of table mentioned in assertion is needed.

Create assertion rich
Check
((Select count(s.sid) from sailors S)
(Select count(B.bid) from Boats B) <100) ;

---

Triggers

-It is an event condition action rules.
-It is activated by some events.
-After activation , it checks the condition.
-If condition is satisfied, the action is performed.
-Triggers can be used to automate various actions in the database,

---

Functional Dependencies

-Functional dependency (FD) is the relationship that exists when one attribute uniquely determines another attribute. .
-Attribute B is functionally dependent on attribute A , denoted by ‘A-B’ if a value of A uniquely identifies a value of B at any instant of time.
-Mathematically , let R be relation schema a C R and B C R the FD α -> β holds on R if for any legal relations R(r) whenever any two tuples t1 and t2 agree on the attributes α , they also agree on the attributes β i.e.

Eg. Consider a relation r (loan_no ,amount) with instances as
1 10000
2 20000
3 10000
4 25000

Here , (loan_no-> amount ) holds because for any two tuples whenever t1[loan_no] = t2 [loan_no] => t1[amount] = t2[amount]

But, (amount -> loan_no) does not hold as for the tuples, the criteria is not satisfied ,
I.e. t1 = (1,10000) and
T3 = (3,10000) t1 [amount] = t3 [amount] = t1 [loan_no] is not equal to t3[loan_no]
In A => B ; A is determinants
B is object determinant

---

Types of FD :

-A FD is trivial , if the object of determinant is a subset of determinant . Mathematically a FD infinity => β is trivial if F belongs to K
E.g Customer name ,loan number => customer name

- A FD is non trivial if the object of determinant is not a subset of determinant ;
E.g (Student_id, student_name) => marks

- Full fd is a situation in which all the attributes oif composite determinant is necessary to identify its object uniquely

- Partial FD is a situation in which the subset of the attributes of composite determinant can identify its object uniquely.

---

Closure of a set of FD

-Consider F as the set of FD , then closure of F ( F+) is defined as a set of FD that are implied by F.
-Axioms :
a) if B ∈ x then x => B ( reflexivity )
b) if x => B then Ya = Yb (augmentation)
c) If x => B and B => Y then α => y
d) If x => B and α => Y then then α => y

---

Closure of attribute sets

-Consider A as a set of attributes and F be set of FD then closure of A under F(A) is the set of attributes that are functionally determined by A under F.
-Algorithm result := A
While (changes to result) do
For each K=> B in F
If includes result then result := result union B
-if A+ contains all attributes of R then α is super key.
-if B belongs to α+ then α => β holds.

---

Q) If R = {A,B,C,D,E,F,G} , F={A=> B, ABCD=>E ,EF =>G } list all possible F+

Members of F+ are :
ACD => E [A=> B and (ACD)B => E]
ABCDF => G [ABCD => E and (F)E => G]

---

Q) Find (AG)+ if R = (A,B,C,G,H,I) and F={A=>B, A=>C, CG=>H,G=> I , B=>H, CG=>I },

result = AG
Result = ABG
Result = ABCG
Result = ABCGH
Result = ABCGHI

---

Canonical Cover

- A canonical cover of F is a minimal set of FD equivalent to F having no redundant dependencies.
- Attributes A is extraneous in α if A belongs to α and F with α => β logically implies (F – { α => β} union {α –A ) => β}

- Algorithm
Repeat
Use union rule to replace in F ; α => β1 , α => β2 => α = β1 β2
Find FD with extraneous attribute and if found delete attribute until F does not change.

---

Testing if attribute is extraneous

1. To test if A belongs to α is extraneous in α
-Compute ({α}-A)+ under f
-({α}-A)+ contains all attributes of β , A is extraneous

2. To test if A belongs to β is extraneous in β.
-Compute α+ under F’ = (F – {α => β }) union {α => {β - A })
-If K+ contains A, A is extraneous .

---

Q) Canonical Cover for R =(A,B,C), F = {A => BC , B=> C ,A => B , AB => C }

F = { A=>BC , B=>C , A=>B, AB => C }

1) A=>BC and A=>B have same LHS attribute so they can be combined using union rule :
Fc = { A=>BC ,B => C, AB => C }

2) Check presence of extraneous attribute in AB => C ;
For A belongs to AB ;
({ AB} –A )+ under F = B+ under F
=BC

Since all attributes of RHS is in {BC} , A is extraneous .
Therefore Fc = { A => BV , B=> C}

3) To check presence of extraneous in A => BC .
For C belongs to BC ; (A)+ under F’ = { B=> C, A=> B} = {ABC}
As A+ contains C , is extraneous .
Therefore Fc = { A=>B , B=> C }

---

Decomposition

Decomposition is the process of decomposing of a relation into a set of relations.
-While decomposing the following properties are desirable :
1. Attribute Preservation
2. Lossless join decomposition.
3. Dependency Preservation.
4. Lack of redundancy

---

Lossless Join Decomposition

-If R is decomposed in R1 and R2 then it is called lossless Join decomposition if R1 R2 = R
- R1 and R2 are lossless decomposition of R , if at least one of the functional dependencies is in F+
R1 intesection R2 => R1
R1 intersection R2 => R2

---

Dependency Preservation

-A decomposition is dependency preserving with respect to F if union if projections of F on each R on each R: is equivalent to F
- F1 union F2 union …….. union Fn ) + = F+

---

Suppose R = (A,B,C,D,E) is decomposed with R1(A,B,C ) and R2(C,D,E) . is it lossless ? Is it dependency preserving? Consider F = { A=> BC, CD=> E, B=>D, E=> A}

R = (A,B,C,D,E)
F = { A=> BC, CD=> E, B=>D, E=> A}
R1 = (A,B,C ) F1 = { A =>BC}
R2 = (C,D,E ) F2 = {CD => E }
(Not dependency preserving)

 

	A	B	C	D	E
R1	α	α	α
R2			α	α	α

(Lossy) - Because no any rows have all α.

 

---

Multi valued and Joined Dependencies

Multivalued Dependencies

- R is the relation schema where α belongsto R and B belongsto R , the α => β denotes multivalues dependency that holds if in any legal relation R® for all pairs for tuples t1 and t2 in r such that t1 [α] = t2 [α] , there exists t3 and t4 such that
T1[α]= T2[α]= T3[α]=T4[α]
T3[β]=T1[β]
t3[R-β] = t2[R – β]
t4[β] = t2[R-β]

- It express a condition among tuples that exists when :
1. more than one many many relation
2. certain attribute become independent of one another
3. their values must appear in all combinations

---

Joined Dependency

A join dependency denoted by J(R1,R2,R3.. Rn) on R specifies a constraint on states r of R such that every legal state r of R is equal to join of its projections on R1, R2 …. Rn

-pi R1® * pi R2® * ……* pi Rn® = r

---

Normal Forms: 1NF, 2NF, 3NF, BCNF and DKNF

Normalization

Database normalization is the process of removing redundant data from tables ensuring data dependencies so as to improve storage efficiency ,data integrity and scalability.

---

Unnormalized Normal Form (UNF)

NO normalization rule are applied.

---

First Normal Form (1 NF)

- A relational schema R is in 1NF if the domains of all attributes of R are atomic.
- Ensure each table has primary key and minimal sets of attributes which uniquely identify a record.
- Eliminate repeating group (attribute that can have more than one value for a primary key)
- Each attribute must be atomic.

---

Second Normal Form (2NF)

- A relation is in 2NF if it is in 1NF and every non key attribute is fully dependent on primary key .
- Remove partial functional dependencies into a new relationship.

---

Third Normal Form (3NF)

-A relation R is said to Be in 3nf id it is in 2nf and every non key attribute is non transitively dependent on primary key .
- R is in 3nf if for all α => B in F+ at least one holds;
Α => β is trivial
Α is super key for R
Each attribute in β – α is contained in candidate key for R
- Remove transitive dependencies into a new relations.

---

Boyce Codd Normal Form (BCNF)

-It involves decompositions involving relations with more than one candidate key , where candidate keys are composite and overlapping,
-A relation R is in BCNF if every determinant is a candidate key ,
-It is a special case of 3NF .
-R is in BCNF if for all α => β in F+ at least one holds;
Α => β is trivial
Α is super key for R

---

BCNF and 3NF

-Relation in BCNF has no information repetition but relation in 3NF has information repetition.
-Decomposition in 3nf is lossless and dependency preserving but decomposition in BCNF is not dependency preserving.

---

Fourth Normal Form (4NF)

- A relation R is in 4nf if for all multivalued dependencies in D + of form α => => β , at least one holds.
α => => β trivial
α is super key for R
Fifth normal form is the form in which the relation R is in 4nf and every join dependency is implied by a candidate key.

---

- A relation R is in 4nf if for all multivalued dependencies in D + of form α => => β , at least one holds. α => => β trivial α is super key for R Fifth normal form is the form in which the relation R is in 4nf and every join dependency is implied by a candidate key. Domain key normal form (DKNF)

-A relation R is said to be in DKNF if every constraint of R is a logical consequence of domain constraints and key constraints.
-It is free from any anomalies.