Post By: Hanan Mannan Contact Number: Pak (+92)-321-59-95-634 -------------------------------------------------------
DBMS Joins
We understand the benefits of Cartesian product of two relation, which gives us all the possible tuples that are paired together. But Cartesian product might not be feasible for huge relations where number of tuples are in thousands and the attributes of both relations are considerable large.
Join is combination of Cartesian product followed by selection process. Join operation pairs two tuples from different relations if and only if the given join condition is satisfied.
Following section should describe briefly about join types:
Theta (θ) join
θ in Theta join is the join condition. Theta joins combines tuples from different relations provided they satisfy the theta condition.
Notation:
R1 ⋈θ R2
R1 and R2 are relations with their attributes (A1, A2, .., An ) and (B1, B2,.. ,Bn) such that no attribute matches that is R1 ∩ R2 = Φ Here θ is condition in form of set of conditions C.
Theta join can use all kinds of comparison operators.
Student
SID
Name
Std
101
Alex
10
102
Maria
11
[Table: Student Relation]
Subjects
Class
Subject
10
Math
10
English
11
Music
11
Sports
[Table: Subjects Relation]
Student_Detail =
STUDENT ⋈Student.Std=Subject.Class SUBJECT
Student_detail
SID
Name
Std
Class
Subject
101
Alex
10
10
Math
101
Alex
10
10
English
102
Maria
11
11
Music
102
Maria
11
11
Sports
[Table: Output of theta join]
Equi-Join
When Theta join uses only equality comparison operator it is said to be Equi-Join. The above example conrresponds to equi-join
Natural Join ( ⋈ )
Natural join does not use any comparison operator. It does not concatenate the way Cartesian product does. Instead, Natural Join can only be performed if the there is at least one common attribute exists between relation. Those attributes must have same name and domain.
Natural join acts on those matching attributes where the values of attributes in both relation is same.
Courses
CID
Course
Dept
CS01
Database
CS
ME01
Mechanics
ME
EE01
Electronics
EE
[Table: Relation Courses]
HoD
Dept
Head
CS
Alex
ME
Maya
EE
Mira
[Table: Relation HoD]
Courses ⋈ HoD
Dept
CID
Course
Head
CS
CS01
Database
Alex
ME
ME01
Mechanics
Maya
EE
EE01
Electronics
Mira
[Table: Relation Courses ⋈ HoD]
Outer Joins
All joins mentioned above, that is Theta Join, Equi Join and Natural Join are called inner-joins. An inner-join process includes only tuples with matching attributes, rest are discarded in resulting relation. There exists methods by which all tuples of any relation are included in the resulting relation.
There are three kinds of outer joins:
Left outer join ( R S )
All tuples of Left relation, R, are included in the resulting relation and if there exists tuples in R without any matching tuple in S then the S-attributes of resulting relation are made NULL.
Left
A
B
100
Database
101
Mechanics
102
Electronics
[Table: Left Relation]
Right
A
B
100
Alex
102
Maya
104
Mira
[Table: Right Relation]
Courses HoD
A
B
C
D
100
Database
100
Alex
101
Mechanics
---
---
102
Electronics
102
Maya
[Table: Left outer join output]
Right outer join: ( R S )
All tuples of the Right relation, S, are included in the resulting relation and if there exists tuples in S without any matching tuple in R then the R-attributes of resulting relation are made NULL.
Courses HoD
A
B
C
D
100
Database
100
Alex
102
Electronics
102
Maya
---
---
104
Mira
[Table: Right outer join output]
Full outer join: ( R S)
All tuples of both participating relations are included in the resulting relation and if there no matching tuples for both relations, their respective unmatched attributes are made NULL.
Post By: Hanan Mannan Contact Number: Pak (+92)-321-59-95-634 -------------------------------------------------------
DBMS Normalization
Functional Dependency
Functional dependency (FD) is set of constraints between two attributes in a relation. Functional dependency says that if two tuples have same values for attributes A1, A2,..., An then those two tuples must have to have same values for attributes B1, B2, ..., Bn.
Functional dependency is represented by arrow sign (→), that is X→Y, where X functionally determines Y. The left hand side attributes determines the values of attributes at right hand side.
Armstrong's Axioms
If F is set of functional dependencies then the closure of F, denoted as F+, is the set of all functional dependencies logically implied by F. Armstrong's Axioms are set of rules, when applied repeatedly generates closure of functional dependencies.
Reflexive rule: If alpha is a set of attributes and beta is_subset_of alpha, then alpha holds beta.
Augmentation rule: if a → b holds and y is attribute set, then ay → by also holds. That is adding attributes in dependencies, does not change the basic dependencies.
Transitivity rule: Same as transitive rule in algebra, if a → b holds and b → c holds then a → c also hold. a → b is called as a functionally determines b.
Trivial Functional Dependency
Trivial: If an FD X → Y holds where Y subset of X, then it is called a trivial FD. Trivial FDs are always hold.
Non-trivial: If an FD X → Y holds where Y is not subset of X, then it is called non-trivial FD.
Completely non-trivial: If an FD X → Y holds where x intersect Y = Φ, is said to be completely non-trivial FD.
Normalization
If a database design is not perfect it may contain anomalies, which are like a bad dream for database itself. Managing a database with anomalies is next to impossible.
Update anomalies: if data items are scattered and are not linked to each other properly, then there may be instances when we try to update one data item that has copies of it scattered at several places, few instances of it get updated properly while few are left with there old values. This leaves database in an inconsistent state.
Deletion anomalies: we tried to delete a record, but parts of it left undeleted because of unawareness, the data is also saved somewhere else.
Insert anomalies: we tried to insert data in a record that does not exist at all.
Normalization is a method to remove all these anomalies and bring database to consistent state and free from any kinds of anomalies.
First Normal Form:
This is defined in the definition of relations (tables) itself. This rule defines that all the attributes in a relation must have atomic domains. Values in atomic domain are indivisible units.
[Image: Unorganized relation]
We re-arrange the relation (table) as below, to convert it to First Normal Form
[Image: Relation in 1NF]
Each attribute must contain only single value from its pre-defined domain.
Second Normal Form:
Before we learn about second normal form, we need to understand the following:
Prime attribute: an attribute, which is part of prime-key, is prime attribute.
Non-prime attribute: an attribute, which is not a part of prime-key, is said to be a non-prime attribute.
Second normal form says, that every non-prime attribute should be fully functionally dependent on prime key attribute. That is, if X → A holds, then there should not be any proper subset Y of X, for that Y → A also holds.
[Image: Relation not in 2NF]
We see here in Student_Project relation that the prime key attributes are Stu_ID and Proj_ID. According to the rule, non-key attributes, i.e. Stu_Name and Proj_Name must be dependent upon both and not on any of the prime key attribute individually. But we find that Stu_Name can be identified by Stu_ID and Proj_Name can be identified by Proj_ID independently. This is called partial dependency, which is not allowed in Second Normal Form.
[Image: Relation in 2NF]
We broke the relation in two as depicted in the above picture. So there exists no partial dependency.
Third Normal Form:
For a relation to be in Third Normal Form, it must be in Second Normal form and the following must satisfy:
No non-prime attribute is transitively dependent on prime key attribute
For any non-trivial functional dependency, X → A, then either
X is a superkey or,
A is prime attribute.
[Image: Relation not in 3NF]
We find that in above depicted Student_detail relation, Stu_ID is key and only prime key attribute. We find that City can be identified by Stu_ID as well as Zip itself. Neither Zip is a superkey nor City is a prime attribute. Additionally, Stu_ID → Zip → City, so there exists transitive dependency.
[Image: Relation in 3NF]
We broke the relation as above depicted two relations to bring it into 3NF.
Boyce-Codd Normal Form:
BCNF is an extension of Third Normal Form in strict way. BCNF states that
For any non-trivial functional dependency, X → A, then X must be a super-key.
In the above depicted picture, Stu_ID is super-key in Student_Detail relation and Zip is super-key in ZipCodes relation. So,
S )
S )
S)
