DBMS

Normalization

Posted on Updated on

Boyce-Code Normal Form (BCNF)

  • A relationship is said to be in BCNF if it is already in 3NF and the left hand side of every dependency is a candidate key.
  • A relation which is in 3NF is almost always in BCNF. These could be same situation when a 3NF relation may not be in BCNF the following conditions are found true.
  1. The candidate keys are composite.
  2. There are more than one candidate keys in the relation.
  3. There are some common attributes in the relation
Professor Code Department Head of Dept. Percent Time
P1 Physics Ghosh 50
P1 Mathematics Krishnan 50
P2 Chemistry Rao 25
P2 Physics Ghosh 75
P3 Mathematics Krishnan 100

Consider, as an example, the above relation. It is assumed that:

  1. A professor can work in more than one department
  2. The percentage of the time he spends in each department is given.
  3. Each department has only one Head of Department.
  4. The relation diagram for the above relation is given as the following:

 

Untitled

The given relation is in 3NF. Observe, however, that the names of Dept. and Head of Dept. are duplicated. Further, if Professor P2 resigns, rows 3 and 4 are deleted. We lose the information that Rao is the Head of Department of Chemistry.

The normalization of the relation is done by creating a new relation for Dept. and Head of Dept. and deleting Head of Dept. form the given relation. The normalized relations are shown in the following.

Professor Code Department Percent Time
P1 Physics 50
P1 Mathematics 50
P2 Chemistry 25
P2 Physics 75
P3 Mathematics 100

 

Department Head of Dept.
Physics Ghosh
Mathematics Krishnan
Chemistry Rao

See the dependency diagrams for these new relations.

y1

 

 

 

 

 

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Advertisements

Normalization

Posted on Updated on

NORMALIZATION

  • While designing a database out of an entity–relationship model, the main problem existing in that “raw” database is redundancy.
  • Redundancy is storing the same data item in more one place. A redundancy creates several problems like the following:
  1. Extra storage space: storing the same data in many places takes large amount of disk space.
  2. Entering same data more than once during data insertion.
  3. Deleting data from more than one place during deletion.
  4. Modifying data in more than one place.
  5. Anomalies may occur in the database if insertion, deletion, modification etc are no done properly. It creates inconsistency and unreliability in the database.
  • To solve this problem, the “raw” database needs to be normalized. This is a step by step process of removing different kinds of redundancy and anomaly at each step.
  • At each step a specific rule is followed to remove specific kind of impurity in order to give the database a slim and clean look.

Un-Normalized Form (UNF)

  • If a table contains non-atomic values at each row, it is said to be in UNF. Anatomic value is something that cannot be further decomposed. A non-atomic value, as the name suggests, can be further decomposed and simplified.
  • Consider the following table:

Emp-Id

Emp-Name

Month

Sales

Bank-Id

Bank-Name

E01

AA

Jan

1000

B01

SBI

   

Feb

1200

   
   

Mar

850

   

E02

BB

Jan

2200

B02

UTI

   

Feb

2500

   

E03

CC

Jan

1700

B01

SBI

   

Feb

1800

   
   

Mar

1850

   
   

Apr

1725

   
  • In the sample table above, there are multiple occurrences of rows under each key Emp-Id. Although considered to be the primary key, Emp-Id cannot give us the unique identification facility for any single row.
  • Further, each primary key points to a variable length record (3 for E01, 2 for E02 and 4 for E03).

First Normal Form (1NF)

  • A relation is said to be in 1NF if it contains no non-atomic values and each row can provide a unique combination of values.
  • The above table in UNF can be processed to create the following table in 1NF.

Emp-Id

Emp-Name

Month

Sales

Bank-Id

Bank-Name

E01

AA

Jan

1000

B01

SBI

E01

AA

Feb

1200

B01

SBI

E01

AA

Mar

850

B01

SBI

E02

BB

Jan

2200

B02

UTI

E02

BB

Feb

2500

B02

UTI

E03

CC

Jan

1700

B01

SBI

E03

CC

Feb

1800

B01

SBI

E03

CC

Mar

1850

B01

SBI

E03

CC

Apr

1725

B01

SBI

  • As you can see now, each row contains unique combination of values.
  • Unlike in UNF, this relation contains only atomic values, i.e. the rows cannot be further decomposed, so the relation is now in 1NF.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

DBMS Concurrency Control

Posted on

USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

 

  • In a multiprogramming environment where more than one transactions can be concurrently executed, there exists a need of protocols to control the concurrency of transaction to ensure atomicity and isolation properties of transactions.
  • Concurrency control protocols, which ensure serializability of transactions, are most desirable. Concurrency control protocols can be broadly divided into two categories:
  • Lock based protocols
  • Time stamp based protocols

 

Lock based protocols

  • Database systems, which are equipped with lock-based protocols, use mechanism by which any transaction cannot read or write data until it acquires appropriate lock on it first. Locks are of two kinds:
  • Binary Locks: a lock on data item can be in two states; it is either locked or unlocked.
  • Shared/exclusive: this type of locking mechanism differentiates lock based on their uses. If a lock is acquired on a data item to perform a write operation, it is exclusive lock. Because allowing more than one transactions to write on same data item would lead the database into an inconsistent state. Read locks are shared because no data value is being changed.

There are four types lock protocols available:

  • Simplistic

Simplistic lock based protocols allow transaction to obtain lock on every object before ‘write’ operation is performed. As soon as ‘write’ has been done, transactions may unlock the data item.

  • Pre-claiming

In this protocol, a transactions evaluations its operations and creates a list of data items on which it needs locks. Before starting the execution, transaction requests the system for all locks it needs beforehand. If all the locks are granted, the transaction executes and releases all the locks when all its operations are over. Else if all the locks are not granted, the transaction rolls back and waits until all locks are granted.

11

  • Two Phase Locking – 2PL

This locking protocol is divides transaction execution phase into three parts. In the first part, when transaction starts executing, transaction seeks grant for locks it needs as it executes. Second part is where the transaction acquires all locks and no other lock is required. Transaction keeps executing its operation. As soon as the transaction releases its first lock, the third phase starts. In this phase a transaction cannot demand for any lock but only releases the acquired locks.

22

Two phase locking has two phases, one is growing; where all locks are being acquired by transaction and second one is shrinking, where locks held by the transaction are being released.

To claim an exclusive (write) lock, a transaction must first acquire a shared (read) lock and then upgrade it to exclusive lock.

  • Strict Two Phase Locking

The first phase of Strict-2PL is same as 2PL. After acquiring all locks in the first phase, transaction continues to execute normally. But in contrast to 2PL, Strict-2PL does not release lock as soon as it is no more required, but it holds all locks until commit state arrives. Strict-2PL releases all locks at once at commit point.

33

Strict-2PL does not have cascading abort as 2PL does.

Time stamp based protocols

The most commonly used concurrency protocol is time-stamp based protocol. This protocol uses either system time or logical counter to be used as a time-stamp.

Lock based protocols manage the order between conflicting pairs among transaction at the time of execution whereas time-stamp based protocols start working as soon as transaction is created.

Every transaction has a time-stamp associated with it and the ordering is determined by the age of the transaction. A transaction created at 0002 clock time would be older than all other transaction, which come after it. For example, any transaction ‘y’ entering the system at 0004 is two seconds younger and priority may be given to the older one.

In addition, every data item is given the latest read and write-timestamp. This lets the system know, when was last read and write operation made on the data item.

Time-stamp ordering protocol

The timestamp-ordering protocol ensures serializability among transaction in their conflicting read and write operations. This is the responsibility of the protocol system that the conflicting pair of tasks should be executed according to the timestamp values of the transactions.

  • Time-stamp of Transaction Ti is denoted as TS(Ti).
  • Read time-stamp of data-item X is denoted by R-timestamp(X).
  • Write time-stamp of data-item X is denoted by W-timestamp(X).

Timestamp ordering protocol works as follows:

  • If a transaction Ti issues read(X) operation:
    • If TS(Ti) < W-timestamp(X)
      • Operation rejected.
    • If TS(Ti) >= W-timestamp(X)
      • Operation executed.
    • All data-item Timestamps updated.
  • If a transaction Ti issues write(X) operation:
    • If TS(Ti) < R-timestamp(X)
      • Operation rejected.
    • If TS(Ti) < W-timestamp(X)
      • Operation rejected and Ti rolled back.
    • Otherwise, operation executed.

Thomas’ Write rule:

This rule states that in case of:

  • If TS(Ti) < W-timestamp(X)
  •  
  • Operation rejected and Ti rolled back. Timestamp ordering rules can be modified to make the schedule view serializable. Instead of making Ti rolled back, the ‘write’ operation itself is ignored.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

 

Candidate Key

Posted on

USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

Candidate Key:

  • Consider a relation R on a set of n attributes, then a candidate key K is set of one or more fields if it satisfies following properties

(i) Uniqueness: K uniquely identifies each tuple (record) i.e. no two tuples can have same value of K

(ii) Non-redundancy: K is non redundant, i.e. no proper subset of K has uniqueness property.

Example: In the following relation -Student (name, father-name, course, enrollment-no, grade)

Candidate key assuming they give and unique identification

{Name, father-name}, {Enroll-number}

Non candidate key

{Name, enrollment no} violates property 2

{Course} violates property 1

  • Types of Attributes:

(a) Prime Attribute: A set of attributes that participates in the candidate key.

(b) Non Prime Attribute: A set of attributes that do not participate in the candidate key

For example:  Student (name, father- name, enroll-number, grade) Where key be enroll-number then

Prime attribute: enrollment-number

Non prime attribute: name, father-name, course, grade

Primary Key:

  •  A designated candidate key is primary key.
  • It has following properties

(i)  It is fully defined i.e. no unknown values.

(ii)  It cannot be null.

  • Example: Assume that candidate key for student is enrollment number. Therefore enrollment number satisfies that every student must have enrollment number, it should be prime attribute and other name, course, father-name, and grades are non attribute then in relation
  • Student (enrollment number, name, father-name, course, grade)
  • Enrollment number is candidate key. Hence, enrollment number is primary key

Alternate Key:

  • The candidate key which is not chosen as primary key is known as alternate key. In student table, father name is also candidate key but it is not chosen as primary key. Therefore it is alternate key and it can be NULL.

Super Key:

  • Collection of attributes which is uniquely identified but may not be minimal.
  • For  example,  in  student  relation  enrollment  number  and  name  together  can  be  uniquely identified but it is not minimal

 

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Fully Functional Dependency (FFD)

Posted on Updated on

USE-FULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

FULLY FUNCTIONAL DEPENDENCE (FFD)

  • Fully Functional Dependence (FFD) is defined, as Attribute Y is FFD  on attribute” X, if it is FD on X and not FD on any proper subset of X.
  • For example, in relation Supplier, different cities may have the same status. It may be possible that cities like Amritsar, Jalandhar may have the same status 10.
  • So, the City is not FD on Status. But, the combination of Sno, Status can give only one

corresponding City, because Sno” is unique. Thus,

(Sno, Status) -> City

  • It  means  city  is  FD  on  composite  attribute  (Sno,  Status)  however  City  is  not  fully

functional dependent on this composite attribute, which is explained below:

(Sno, Status) -> City

X   Y

  • Here  Y  is  FD  on  X,  but  X  has  two  proper  subsets  Sno  and  Status;  city  is·  FD  .on  one proper subset .of X i.e. Sno Sno -> City
  • According to ‘FFD definition Y must not be FD .on any proper subset of X, but here City is FD in one subset .of X i.e. Sno, so City is not FFD on (Sno, Status)
  •  Consider another case of SP table:

Here, Qty is FD on combination of Sna, Pno.

(Sno, Pno)   ->   Qty

X      Y

Here,  X  has  two  proper  subsets  Sno  and  Pna. Qty  is  not  FD  on  Sno,  because  one  Sna  can supply  mare  than  .one  quantity.  Qty  is  also  not  FD  on  Pno,  because  .one  Pna  may  be supplied many times by different suppliers with different .or same quantities. So, Qty is FFD and composite attribute of (Sno, Pno) -> Qty.

OTHER FUNCTIONAL DEPENDENCIES

  • There are same rather types of functional dependencies, which play a vital role during the process .of normalization of data are

i)  Candidate Functional Dependency -A candidate functional dependency is a functional dependency that includes all attributes of the table. It should also be noted that a well-fanned dependency diagram must have at least one candidate functional dependency, and that there can be more than .one candidate functional dependency for a given dependency diagram.

ii) Primary Functional Dependency A primary functional dependency is a candidate functional dependency that is selected to determine the primary key. The determinant of the primary functional dependency is the primary key of the relational database table. Each dependency diagram must have one and only on primary functional dependency.  If a relational  database  table  has  .only  .one candidate  functional  dependency,  then  it  automatically  becomes  the  primary  functional dependency. Once the primary key has been determined, there will be three possible types of functional dependencies:

iii) Partial functional dependency – is a functional dependency where the determinant consists of key attributes, but not the entire primary key, and the determined consists of

non-key attributes.

iv) Transitive functional dependency is a functional dependency where the determinant consists of non-key attributes and the determined also consists of non-key attributes.

v) Boyce-Codd functional dependency is a functional dependency where the determinant consists of non-key attributes and the determined consists of key attributes.

vi) Multi-Value Dependency (MVD) occurs when two or more independent multi valued facts about the same attribute occur within the same table. It means that if in a relation R having A, Band C as attributes, B and Care multi-value facts about A, which is represented as A ->->B and A ->->C ,then multi value dependency exist only if B and C are independent on each other.

vii) Join Dependency exists if a relation R is equal to the join of the projections X Z. where

X, Y, Z projections of R.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

Functional Dependency

Posted on Updated on

USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

 

·         In the process of efficiently storing data, and eliminating redundancy, tables in a database are designed and created to be in one of five possible normal forms.  Each normal form contains and enforces the rules of the previous form, and, in turn, applies some stricter rules on the design of tables.·         A set of tables in a database are initially said to be in 0 normal form. First Normal Form:

  • Tables are said to be in first normal form when:-
  • The table has a primary key.-
  • No single attribute (column) has multiple values.-
  • The non-key attributes (columns) depend on the primary key.
  • Some examples of placing a table in first normal form are:

2

In first normal form the table : –

4

 

Second Normal Form:

  • Tables are said to be in second normal form when:
  • o   The tables meet the criteria for first normal form.
  • If the primary key is a composite of attributes (contains multiple columns), the non key attributes (columns) must depend on the whole key.
  • Third Normal Form:
  •  Tables are said to be in third normal form when:
  • o   The tables meet the criteria for second normal form.
  • o   Each non-key attribute in a row does not depend on the entry in another key column. Fourth
  • Normal Form:
  • Tables are said to be in fourth normal form when:
  • o  The table meets the criteria for third normal form.
  •  Situations where non-key attributes depend on the key column exclusive of other non-key columns are eliminated. Fifth Normal
  • Form:
  • Tables are said to be in fifth normal form when:
  • o The table meets the criteria for fourth normal form.
  • o The table consists of a key attribute and a non-key attribute only.

 

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

 

Functional Dependency

Posted on

USEFULL FOR FYBSC (IT) & TYBSC (CS) STUDENTS

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.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com