DATABASE MANAGEMENT SYSTEM

Concept of Normalization

•     Purpose of Normalisation
•     Redundancy and Data Anomalies
•     Functional Dependency
•     Transitive Dependency
•     Stages of Normalisation

Purpose of Normalisation

          1. To avoid redundancy by storing each ‘fact’ within the database only once.

         2. To put data into a form that conforms to relational principles (e.g., single valued attributes, each           relation represents one entity) - no repeating groups.

        3.To put the data into a form that is more able to accurately accommodate change.

        4.To avoid certain updating ‘anomalies’.

        5.To facilitate the enforcement of data constraints.

Redundancy and Data Anomalies

Redundant data is where we have stored the same ‘information’ more than once. i.e., the redundant data could be removed without the loss of information.

Example: We have the following relation that contains staff and department details:

staffNo     job           dept   dname        city

SL10        Salesman   10      Sales           Stratford  

SA51       Manager    20     Accounts      Barking

DS40       Clerk         20     Accounts      Barking

OS45       Clerk         30    Operations    Barking

the redundency in table could lead to following anamolies:

Insert Anomaly: We can’t insert a dept without inserting a member of staff that works in that department

Update Anomaly: We could change the name of the dept that SA51 works in without simultaneously changing the dept that DS40 works in.

Deletion Anomaly: By removing employee SL10 we have removed all information pertaining to the Sales dept.

Functional Dependency

Formal Definition:  Attribute B is functionally dependant upon attribute A (or a collection of attributes) if           a value of A determines a single value of attribute B at any one time.

Formal Notation:  A ® B  This should be read as ‘A determines B’ or ‘B is functionally dependant on A’. A is called the determinant and B is called the object of the determinant.

Example:                                     

staffNo  job           dept   dname                                Functional Dependencies           

SL10     Salesman  10      Sales                                       staffNo ® job

SA51    Manager    20     Accounts                                 staffNo ® dept

DS40    Clerk         20      Accounts                                staffNo ® dname

OS45    Clerk         30      Operations                             dept ® dname
  

Compound Determinants: If more than one attribute is necessary to determine another attribute in an entity, then such a determinant is termed a composite determinant.

                                                                                

Full Functional Dependency: Only of relevance with composite determinants. This is the situation when it is necessary to use all the attributes of the composite determinant to identify its object uniquely.                                                                                 

Example:                                                                              

order#   line#    qty     price                          Full Functional Dependencies

A001     001        10      200                           (Order#, line#) ® qty

A002     001        20      400                          (Order#, line#) ® price

A002     002        20     800

A004     001        15     300 
                                                                      

Partial Functional Dependency: This is the situation that exists if it is necessary to only use a subset of the attributes of the composite determinant to identify its object uniquely                                                                 

Example:

student#   unit#   room    grade                    Full Functional Dependencies

9900100     A01   TH224      2                     (student#, unit#) ® grade

9900010     A01   TH224    14                    

9901011     A02   JS075       3                       Partial Functional Dependencies    

9900001     A01   TH224    16                      unit# ® room

  Repetition of data!

          

Transitive Dependency:A transitive dependency exists when there is an intermediate functional dependency.

Formal Notation:  If A ® B and B ® C, then it can be stated that the following transitive dependency exists: A ® B ® C

Example:

staffNo    job            dept    dname                        Transitive Dependencies

     

SL10    Salesman   10      Sales                              staffNo ® dept

SA51    Manager     20     Accounts                         dept ® dname

DS40     Clerk          20      Accounts

OS45     Clerk          30      Operations                    staffNo ® dept ® dname

here also Repetition of data!

Normalization Achieves This!

remove repeating groups and  avoid redundancy and data anomalies by remoting partial and transitive functional dependencies.

Unnormalised Normal Form (UNF)

Definition: A relation is unnormalised when it has not had any normalisation rules applied to it, and it suffers from various anomalies.

First Normal Form (1NF)

Definition: A relation is in 1NF if, and only if, all its underlying attributes contain atomic values only.

Second Normal Form (2NF)

Definition: A relation is in 2NF if, and only if, it is in 1NF and every non-key attribute is fully dependent on the primary key.

  Remove partial functional dependencies into a new relation

consider the relation 

student( Rollno, Name, CourseNo, CourseName, Deptid, DeptName)

                     here {Rollno,,courseNo,Deptid} is candidate key

if there exist the partial functional dependency like Rollno-->Name  or  Deptid-->DeptName it is not in 2NF

Decomposition

                           student(Rollno,CourseNo,CourseName,Deptid)

                           X1(Rollno,Name)

                           X2(Deptid,DeptName)

Third normal form(3NF)

A relation R is in 3rd normal form if and only if it is in 2NF and every non-key attribute is non-transitively dependent on the primary key.

      Remove transitive functional dependencies into a new relation

consider the relation

                             Shipdetails(Ship,Capacity,Date,Cargo,Value)    with following functional dependency

 Ship,Date-->Cargo,Capacity

 Cargo-->Value  relation is not in 3NF 

Decomposition

                             Shipdetails(Ship,Capacity,Date,Cargo)

                             X1(Cargo,Value)

A relation in 3NF does not have any anamolies but it still have redundency.

Boyce-Codd Normal Form (BCNF) 

         A more restricted version of 3NF (known as Boyce-Codd Normal Form) requires that the determinant of every functional dependency in a relation be a superkey - for every FD: X => Y, X is a superkey

Consider the following relation:

STU-MAJ-ADV (Student-Id, Major, Advisor)

Advisor --> Major                  , but Advisor is not a superkey

Decomposition

STU-ADV (Student-Id, Advisor)

ADV-MAJ (Advisor, Major)

4th Normal Form

A Boyce Codd normal form relation is in fourth normal form if

(a)there is no multi value dependency in the relation or

(b)there are multi value dependency but the attributes, which are multi valued dependent on a specific attribute, are independent each other.

consider the following relation 

Employee (Eid, Languages, Skills) 

Eid --->> Languages  Eid --->> Skills
Languages and Skills are independent.

Decomposition

Emplyee_Language(Eid, Languages)

Emplyee_Language(Eid, Skills)

What is a Transaction?

n A logical unit of work on a database

n An entire program

n A portion of a program

n A single command

n The entire series of steps necessary to accomplish a logical unit of work

n Successful transactions change the database from one CONSISTENT STATE to another

  (One where all data integrity constraints are satisfied)

Example of a Transaction

n Updating a Record

n Locate the Record on Disk

n Bring record into Buffer

n Update Data in the Buffer

n Writing Data Back to Disk

ACID Properties of a Transaction

n Atomic – All or Nothing

  All parts of the transaction must be completed and committed or it must be aborted and rolled back

n Consistency

  The consistency property ensures that any transaction will bring the database from one valid state to another. Any data written to the database must be valid according to all defined rules, including but not limited to constraints, cascades, triggers, and any combination thereof.

n Isolation

  The final effects of multiple simultaneous transactions must be the same as if they were executed one right after the other .

n Durability

  If a transaction has been committed, the DBMS must ensure that its effects are permanently recorded in the database (even if the system crashes)

Transaction Management with SQL

n SQL Statements à Commit / Rollback

n When a transaction sequence is initiated it must continue through all succeeding SQL statements until:

!A Commit Statement is Reached

!A Rollback Statement is Reached

!The End of the Program is Reached (Commit)

!The Program  is Abnormally Terminated (Rollback)

Transaction Log

n Keeps track of all transactions that update the database

n Record for the beginning of the transaction

n Type of operation (insert / update / delete)

n Names of objects/tables affected by the transaction

n Before and After Values for Updated Fields

n Pointers to Previous and Next Transaction Log Entries for the same transaction

n The Ending of the Transaction (Commit)

n Used for recovery in case of a Rollback

Concurrency Control

n Coordination of simultaneous transaction execution in a multiprocessing database system

n Ensure transaction serializability in a multi-user database

n Lack of Concurrency Control can create data integrity and consistency problems:

n Lost Updates

n Uncommitted Data

n inconsistent Retrievals

Serial Execution of Transactions

n Serial Execution of transaction means that the transactions are performed one after another.

n No interaction between transactions  - No Concurrency Control Problems

n Serial Execution will never leave the database in an inconsistent state à Every Serial Execution is considered correct (Even if a different order would cause different results)

Serializability

n If 2 Transactions are only reading data items – They do not conflict à Order is unimportant

n If 2 Transactions operate (Read/Write) on Separate Data Items

  – They do not conflict à Order is unimportant

n If 1 Transaction Writes to a Data Item and Another Reads or Writes to the Same Data Item à The Order of Execution IS Important

The Scheduler

n Special DBMS Program to establish the order of operations in which concurrent transactions are executes

n Interleaves the execution of database operations to ensure:

             Serializability

             Isolation of Transactions

n Bases its actions on Concurrency Control Algorithms (Locking / Time Stamping)

n Ensures the CPU is used efficiently (Scheduling Methods)

n Facilitates Data Isolation à Ensure that 2 transactions do not update the same data at the same time

Concurrency Control Algorithms

n Locking

     A Transaction “locks” a database object to prevent another object from modifying the object

n Time-Stamping

                Assign a global unique time stamp to each transaction

n Optimistic

                Assumption that most database operations do not conflict

Locking

n Lock guarantees exclusive use of data item to current transaction

n Prevents reading Inconsistent Data

n Lock Manager is responsible for assigning and policing the locks used by the transaction

Locking Granularity

Indicates the level of lock use

n Database Level – Entire Database is Locked

n Table Level – Entire Table is Locked

n Page Level – Locks an Entire Diskpage

       (Most Frequently Used)

n Row Level – Locks Single Row of Table

n Field Level – Locks a Single Attribute of a Single Row (Rarely Done)

Types of Locks:  

n Binary Locks – Lock with 2 States

n Locked – No other transaction can use that object

n Unlocked – Any transaction can lock and use object

         All Transactions require a Lock and Unlock Operation for Each

          Object Accessed (Handled by DBMS)

n Eliminates Lost Updates

n Too Restrictive to Yield Optimal Concurrency Conditions

Shared / Exclusive Locks:Indicates the Nature of the Lock

n Shared Lock – Concurrent Transactions are granted READ access on the basis of a     common lock


n    Exclusive Lock – Access is reserved for the transaction that locked the object

n 3 States:  Unlocked, Shared (Read), Exclusive (Write)

n More Efficient Data Access Solution

n More Overhead for Lock Manager

n Type of lock needed must be known

n 3 Operations: 

nRead_Lock – Check to see the type of lock

nWrite_Lock – Issue a Lock

nUnlock – Release a Lock

n Allow Upgrading / Downgrading of Locks

Problems with Locking

n Transaction Schedule May Not be Serializable

n Can be solved with 2-Phase Locking

n May Cause Deadlocks

n A deadlock is caused when 2 transactions wait for each other to unlock data

Two Phase Locking

n Defines how transactions Acquire and Relinquish Locks

!Growing Phase – The transaction acquires all locks (doesn’t unlock any data)

!Shrinking Phase – The transaction releases locks (doesn’t lock any additional data)

n Transactions acquire all locks it needs until it reaches locked point

n When locked, data is modified and locks are released

Deadlocks

n Occur when 2 transactions exist in the following mode:

      T1 = access data item X and Y

      T2 = Access data items Y and X

          If T1 does not unlock Y, T2 cannot begin

          If T2 does not unlock X, T1 cannot continue

     T1 & T2 wait indefinitely for each other to unlock data

n Deadlocks are only possible if a transactions wants an Exclusive Lock 


(No Deadlocks on Shared Locks)

Controlling Deadlocks

n Prevention – A transaction requesting a new lock is aborted if there is the 


            possibility of a deadlock – Transaction is rolled back, Locks are released, 


            Transaction is rescheduled

n Detection – Periodically test the database for deadlocks.  If a deadlock is found, 


             abort / rollback one of the transactions

n Avoidance – Requires a transaction to obtain all locks needed before it can 


             execute – requires locks to be obtained in succession

Time Stamping

n Creates a specific order in which the transactions are processed by the DBMS

n 2 Main Properties

!Uniqueness – Assumes that no equal time stamp value can exist (ensures serializability of the transactions)

!Monotonicity – Ensures that time stamp values always increases

n All operations within the same transaction have the same time stamp

n f Transactions conflict, one is rolled back and rescheduled

n Each value in Database requires 2 Additional Fields:  Last Time Read / Last Time Updated

n Increases Memory Need and Processing Overhead

Time Stamping Schemes

n Wait /  Die Scheme
  The older transaction will wait 

  The younger transaction will be rolled back

n Wound / Wait Scheme

  The older transaction will preempt (wound)

  the younger transaction and roll it back

  The younger transaction waits for the older

  transaction to release the locks

n Without time-out values, Deadlocks may be created

Database Recovery

n Restore a database from a given state to a previous consistent state

n Atomic Transaction Property (All or None)

n Backup Levels:

n Full Backup

n Differential Backup

n Transaction Log Backup

n Database / System Failures:

n Software (O.S., DBMS, Application Programs, Viruses)

n Hardware (Memory Chips, Disk Crashes, Bad Sectors)

n Programming Exemption (Application Program rollbacks)

n Transaction (Aborting transactions due to deadlock detection)

n External (Fire, Flood, etc)

Transaction Recovery

n Recover Database by using data in the Transaction Log

n Write-Ahead-Log – Transaction logs need to be written before any database data is updated

n Redundant Transaction Logs – Several copies of log on different devices

n Database Buffers – Buffers are used to increase processing time on updates instead of accessing data on disk

n Database Checkpoints – Process of writing all updated buffers to disk à While this is taking place, all other requests are not executes

n Scheduled several times per hour

n Checkpoints are registered in the transaction log