Transcript Slide 1

DBMS Fundamentals
Dr. E.Grace Mary Kanaga
Associate Professor / CSE
Karunya University
17-09-2014
Database Management
Systems - Placement Training
Agenda
•
•
•
•
•
•
•
Introduction
DDL
DML
DCL
TCL
ER Design
Normalization
17-09-2014
Database Management
Systems - Placement Training
Introduction
Data
Facts and statistics collected together for reference or
analysis
Database
It is an organized collection of data that is organized so
that it can easily be accessed, managed, and updated
Database Systems
Database system is a system to achieve an organized,
store a large number of dynamical associated data,
facilitate for multi-user accessing to computer
hardware, software and data, that it is a computer
system with database technology
17-09-2014
Database Management Systems Placement Training
Introduction
Database Management Systems
•
They are specially designed software applications
that interact with the user, other applications, and the
database itself to capture and analyse data.
• A general-purpose DBMS is a software system
designed to allow the definition, creation, querying,
update, and administration of databases.
Data Model
•
It is a specification describing how a database is
structured and used
17-09-2014
Database Management Systems Placement Training
Data Model - Types
• Flat model: This may not
strictly qualify as a data
model..
• Hierarchical model: In this
model data is organized into a
tree-like structure
• Network model: This model
organizes data using two
fundamental constructs, called
records and sets.
• Relational model: is a
database model based on firstorder predicate logic.
17-09-2014
Database Management Systems Placement Training
Database Management Systems
•
•
•
•
•
MySQL
MariaDB
PostgreSQL
SQLite
Microsoft SQL
Server
• Microsoft Access
• Oracle
• IBM DB2
17-09-2014
•
•
•
•
•
•
•
SAP
HANA
dBASE,
LibreOffice Base
FileMaker Pro
InterSystems Caché
FoxPro
Database Management Systems Placement Training
Database Objects
17-09-2014
Object
Description
Table
Basic unit of storage; composed of rows
and columns
View
Logically represents subsets of data from
one or more tables
Sequence
Numeric value generator
Index
Improves the performance of some queries
Synonym
Gives alternative names to objects
Database Management Systems Placement Training
DDL- Data Definition Language
Statement
Description
CREATE TABLE
Creates a table
ALTER TABLE
Modifies table structures
DROP TABLE
Removes the rows and table structure
RENAME
Changes the name of a table, view,
sequence, or synonym
TRUNCATE
Removes all rows from a table and
releases the storage space
COMMENT
Adds comments to a table or view
17-09-2014
Database Management Systems Placement Training
Naming Rules
Table names and column names:
• Must begin with a letter
• Must be 1–30 characters long
• Must contain only A–Z, a–z, 0–9, _, $,
and #
• Must not duplicate the name of another
object owned by the same user
• Must not be an Oracle server reserved
word
17-09-2014
Database Management Systems Placement Training
The CREATE TABLE Statement
• You must have:
– CREATE TABLE privilege
– A storage area
CREATE TABLE [schema.]table
(column datatype [DEFAULT expr][, ...]);
• You specify:
– Table name
– Column name, column data type, and
column size
17-09-2014
Database Management Systems Placement Training
Tables in the Oracle Database
• User Tables:
– Are a collection of tables created and
maintained by the user
– Contain user information
• Data Dictionary:
– Is a collection of tables created and
maintained by the Oracle Server
– Contain database information
17-09-2014
Database Management Systems Placement Training
Data Types
Data Type
Description
VARCHAR2(size)
Variable-length character data
CHAR(size)
Fixed-length character data
NUMBER(p,s)
Variable-length numeric data
DATE
Date and time values
LONG
Variable-length character data
up to 2 gigabytes
Character data up to 4
gigabytes
CLOB
RAW and LONG RAW
Raw binary data
BLOB
Binary data up to 4 gigabytes
BFILE
Binary data stored in an external
file; up to 4 gigabytes
A 64 base number system representing
the unique address of a row in its table.
ROWID
17-09-2014
Database Management Systems Placement Training
DML COMMANDS
• The acronym DML represents Data Manipulation
Language
• Data Manipulation Language (DML) statements are
used to define the data in the database
• The Data Manipulation Language (DML) is used to
retrieve, insert and modify database information.
• These commands will be used by all database users
during the routine operation of the database
–
–
–
–
17-09-2014
INSERT
SELECT
UPDATE
DELETE
Database Management Systems Placement Training
DML:
• Insert
The INSERT command in SQL is used to add records to an existing table.
Syntax:
INSERT INTO table name(field name1 data type, field name2 data type ……. field name n data type);
EXAMPLE
SQL> insert into stud1(st_name,st_num,st_dob,sub1,sub2,tot) values
('&st_name',&st_num,&st_dob,&sub1,&sub2,&tot);
SQL> /
Enter value for st_name: charles
Enter value for st_num: 1
Enter value for st_dob: '20 may 2000'
Enter value for sub1: 90
Enter value for sub2: 80
Enter value for tot: 170
17-09-2014
Database Management Systems Placement Training
• Update
The UPDATE command can be used to modify
information contained within a table, either in bulk or
individually.
Syntax
1.UPDATE tablename SET fieldname=new value;
2. UPDATE table name SET fieldname=new value where
condition;
EXAMPLE
update emp1 set emp_sal = emp_sal + 500 where
emp_bpay > 5000;
17-09-2014
Database Management Systems Placement Training
DELETE :
• To delete data from the database.
DELETE [FROM] table
[WHERE condition];
SELECT:
• To retrieve the data from the database.
SELECT *|{[DISTINCT] column|expression [alias],...}
FROM table;
SELECT *|{[DISTINCT] column|expression [alias],...}
FROM table
[WHERE condition(s)];
A where clause is used to restrict the rows returned.
17-09-2014
Database Management Systems Placement Training
The select Clause
• The select clause list the attributes desired in the result of
a query
– corresponds to the projection operation of the relational
algebra
• Example: find the names of all branches in the loan
relation:
select branch_name
from loan
• In the relational algebra, the query would be:
branch_name (loan)
• NOTE: SQL names are case insensitive (i.e., you may use
upper- or lower-case letters.)
– E.g. Branch_Name ≡ BRANCH_NAME ≡ branch_name
– Some people use upper case wherever we use bold font.
17-09-2014
Database Management Systems Placement Training
The select Clause (Cont.)
• SQL allows duplicates in relations as well as in query
results.
• To force the elimination of duplicates, insert the
keyword distinct after select.
• Find the names of all branches in the loan relations, and
remove duplicates
select distinct branch_name
from loan
• The keyword all specifies that duplicates not be
removed.
select all branch_name
from loan
17-09-2014
Database Management Systems Placement Training
The select Clause (Cont.)
• An asterisk in the select clause denotes “all
attributes”
select *
from loan
• The select clause can contain arithmetic expressions
involving the operation, +, –, , and /, and operating
on constants or attributes of tuples.
• E.g.:
select loan_number, branch_name,
from loan
17-09-2014
Database Management Systems Placement Training
The where Clause
• The where clause specifies conditions that the result
must satisfy
– Corresponds to the selection predicate of the relational
algebra.
• To find all loan number for loans made at the
Perryridge branch with loan amounts greater than
$1200.
select loan_number
from loan
where branch_name = 'Perryridge' and
amount > 1200
• Comparison results can be combined using the
logical connectives and, or, and not.
17-09-2014
Database Management Systems Placement Training
The from Clause
• The from clause lists the relations involved in the query
– Corresponds to the Cartesian product operation of the
relational algebra.
• Find the Cartesian product borrower X loan
select 
from borrower, loan
 Find the name, loan number and loan amount of all customers
having a loan at the Perryridge branch.
select customer_name, borrower.loan_number, amount
from borrower, loan
where borrower.loan_number = loan.loan_number and
branch_name = 'Perryridge'
17-09-2014
Database Management Systems Placement Training
The Rename Operation
• SQL allows renaming relations and attributes
using the as clause:
old-name as new-name
• E.g. Find the name, loan number and loan
amount of all customers; rename the column
name loan_number as loan_id.
select customer_name, borrower.loan_number as loan_id, amount
from borrower, loan
where borrower.loan_number = loan.loan_number
17-09-2014
Database Management Systems Placement Training
String Operations
• SQL includes a string-matching operator for
comparisons on character strings. The operator
“like” uses patterns that are described using two
special characters:
–
–
percent (%). The % character matches any substring.
underscore (_). The _ character matches any character.
• Find the names of all customers whose street
includes the substring “Main”.
select customer_name
from customer
where customer_street like '% Main%'
• Match the name “Main%”
like 'Main\%' escape '\'
• SQL supports a variety of string operations such as
–
–
–
17-09-2014
concatenation (using “||”)
converting from upper to lower case (and vice versa)
finding string length, extracting substrings, etc.
Database Management Systems Placement Training
Ordering the Display of Tuples
• List in alphabetic order the names of all customers
having a loan in Perryridge branch
select distinct customer_name
from borrower, loan
where borrower loan_number =
loan.loan_number and
branch_name = 'Perryridge'
order by customer_name
• We may specify desc for descending order or asc for
ascending order, for each attribute; ascending order is
the default.
– Example: order by customer_name desc
17-09-2014
Database Management Systems Placement Training
Set Operations
• Find all customers who have a loan, an account, or both:
(select customer_name from depositor)
union
(select customer_name from borrower)
 Find all customers who have both a loan and an account.
(select customer_name from depositor)
intersect
(select customer_name from borrower)
 Find all customers who have an account but no loan.
(select customer_name from depositor)
except
(select customer_name from borrower)
17-09-2014
Database Management Systems Placement Training
DCL
• Grant
• Revoke
17-09-2014
Database Management Systems Placement Training
TCL
• Save Point
• Roll Back
• Commit
17-09-2014
Database Management Systems Placement Training
Normalization
•
•
•
This is the process which allows you to winnow out
redundant data within your database.
This involves restructuring the tables to successively
meeting higher forms of Normalization.
A properly normalized database should have the
following characteristics
–
–
–
–
17-09-2014
Scalar values in each fields
Absence of redundancy.
Minimal use of null values.
Minimal loss of information.
Database Management Systems Placement Training
Levels of Normalization
First Normal Form (1NF)
Second Normal Form (2NF)
Third Normal Form (3NF)
Boyce-Codd Normal Form (BCNF)
Fourth Normal Form (4NF)
Fifth Normal Form (5NF)
Domain Key Normal Form (DKNF)
Redundancy
–
–
–
–
–
–
–
Complexity
•
Levels of normalization based on the amount of
redundancy in the database.
Various levels of normalization are:
Number of Tables
•
Most databases should be 3NF or BCNF in order to avoid the database anomalies.
17-09-2014
Database Management Systems Placement Training
Levels of Normalization
1NF
2NF
3NF
4NF
5NF
DKNF
Each higher level is a subset of the lower level
17-09-2014
Database Management Systems Placement Training
First Normal Form (1NF)
A table is considered to be in 1NF if all the fields contain
only scalar values (as opposed to list of values).
Example (Not 1NF)
ISBN
Title
AuName
AuPhone
PubName
PubPhone
Price
0-321-32132-1
Balloon
Sleepy,
Snoopy,
Grumpy
321-321-1111,
232-234-1234,
665-235-6532
Small House
714-000-0000
$34.00
0-55-123456-9
Main Street
Jones,
Smith
123-333-3333,
654-223-3455
Small House
714-000-0000
$22.95
0-123-45678-0
Ulysses
Joyce
666-666-6666
Alpha Press
999-999-9999
$34.00
1-22-233700-0
Visual
Basic
Roman
444-444-4444
Big House
123-456-7890
$25.00
Author and AuPhone columns are not scalar
17-09-2014
Database Management Systems Placement Training
1NF - Decomposition
1.
2.
3.
Place all items that appear in the repeating group in a
new table
Designate a primary key for each new table produced.
Duplicate in the new table the primary key of the table
from which the repeating group was extracted or vice
versa.
Example (1NF)
ISBN
AuName
AuPhone
0-321-32132-1
Sleepy
321-321-1111
ISBN
Title
PubName
PubPhone
Price
0-321-32132-1
Snoopy
232-234-1234
0-321-32132-1
Balloon
Small House
714-000-0000
$34.00
0-321-32132-1
Grumpy
665-235-6532
0-55-123456-9
Main Street
Small House
714-000-0000
$22.95
0-55-123456-9
Jones
123-333-3333
0-123-45678-0
Ulysses
Alpha Press
999-999-9999
$34.00
0-55-123456-9
Smith
654-223-3455
1-22-233700-0
Visual
Basic
Big House
123-456-7890
$25.00
0-123-45678-0
Joyce
666-666-6666
1-22-233700-0
Roman
444-444-4444
17-09-2014
Database Management Systems Placement Training
Functional Dependencies
1.
If one set of attributes in a table determines another
set of attributes in the table, then the second set of
attributes is said to be functionally dependent on the
first set of attributes.
Example 1
ISBN
Title
Price
0-321-32132-1
Balloon
$34.00
0-55-123456-9
Main Street
$22.95
0-123-45678-0
Ulysses
$34.00
1-22-233700-0
Visual
Basic
$25.00
17-09-2014
Table Scheme: {ISBN, Title, Price}
Functional Dependencies: {ISBN}  {Title}
{ISBN}  {Price}
Database Management Systems Placement Training
Functional Dependencies
Example 2
PubID
PubName
PubPhone
1
Big House
999-999-9999
2
Small House
123-456-7890
3
Alpha Press
111-111-1111
Table Scheme: {PubID, PubName, PubPhone}
Functional Dependencies: {PubId}  {PubPhone}
{PubId}  {PubName}
{PubName, PubPhone}  {PubID}
Example 3
AuID
AuName
AuPhone
1
Sleepy
321-321-1111
2
Snoopy
232-234-1234
3
Grumpy
665-235-6532
4
Jones
123-333-3333
5
Smith
654-223-3455
6
Joyce
666-666-6666
7
Roman
444-444-4444
17-09-2014
Table Scheme: {AuID, AuName, AuPhone}
Functional Dependencies: {AuId}  {AuPhone}
{AuId}  {AuName}
{AuName, AuPhone}  {AuID}
Database Management Systems Placement Training
FD – Example
Database to track reviews of papers submitted to an academic
conference. Prospective authors submit papers for review and
possible acceptance in the published conference proceedings.
Details of the entities
–
–
–
–
Author information includes a unique author number, a name, a
mailing address, and a unique (optional) email address.
Paper information includes the primary author, the paper number,
the title, the abstract, and review status (pending,
accepted,rejected)
Reviewer information includes the reviewer number, the name, the
mailing address, and a unique (optional) email address
A completed review includes the reviewer number, the date, the
paper number, comments to the authors, comments to the
program chairperson, and ratings (overall, originality, correctness,
style, clarity)
17-09-2014
Database Management Systems Placement Training
FD – Example
Functional Dependencies
–
–
–
–
–
–
17-09-2014
AuthNo  AuthName, AuthEmail, AuthAddress
AuthEmail  AuthNo
PaperNo  Primary-AuthNo, Title, Abstract, Status
RevNo  RevName, RevEmail, RevAddress
RevEmail  RevNo
RevNo, PaperNo  AuthComm, Prog-Comm, Date,
Rating1, Rating2, Rating3, Rating4, Rating5
Database Management Systems Placement Training
Second Normal Form (2NF)
For a table to be in 2NF, there are two requirements
–
–
The database is in first normal form
All nonkey attributes in the table must be functionally dependent on the
entire primary key
Note: Remember that we are dealing with non-key attributes
Example 1 (Not 2NF)
Scheme  {Title, PubId, AuId, Price, AuAddress}
1.
2.
3.
4.
5.
17-09-2014
Key  {Title, PubId, AuId}
{Title, PubId, AuID}  {Price}
{AuID}  {AuAddress}
AuAddress does not belong to a key
AuAddress functionally depends on AuId which is a subset of a key
Database Management Systems Placement Training
Second Normal Form (2NF)
Example 2 (Not 2NF)
Scheme  {City, Street, HouseNumber, HouseColor, CityPopulation}
1.
2.
3.
4.
5.
key  {City, Street, HouseNumber}
{City, Street, HouseNumber}  {HouseColor}
{City}  {CityPopulation}
CityPopulation does not belong to any key.
CityPopulation is functionally dependent on the City which is a proper subset of
the key
Example 3 (Not 2NF)
Scheme  {studio, movie, budget, studio_city}
1.
2.
3.
4.
5.
17-09-2014
Key  {studio, movie}
{studio, movie}  {budget}
{studio}  {studio_city}
studio_city is not a part of a key
studio_city functionally depends on studio which is a proper subset of the key
Database Management Systems Placement Training
2NF - Decomposition
1.
2.
3.
If a data item is fully functionally dependent on only a part of the
primary key, move that data item and that part of the primary
key to a new table.
If other data items are functionally dependent on the same part
of the key, place them in the new table also
Make the partial primary key copied from the original table the
primary key for the new table. Place all items that appear in the
repeating group in a new table
Example 1 (Convert to 2NF)
Old Scheme  {Title, PubId, AuId, Price, AuAddress}
New Scheme  {Title, PubId, AuId, Price}
New Scheme  {AuId, AuAddress}
17-09-2014
Database Management Systems Placement Training
2NF - Decomposition
Example 2 (Convert to 2NF)
Old Scheme  {Studio, Movie, Budget, StudioCity}
New Scheme  {Movie, Studio, Budget}
New Scheme  {Studio, City}
Example 3 (Convert to 2NF)
Old Scheme  {City, Street, HouseNumber, HouseColor, CityPopulation}
New Scheme  {City, Street, HouseNumber, HouseColor}
New Scheme  {City, CityPopulation}
17-09-2014
Database Management Systems Placement Training
Third Normal Form (3NF)
This form dictates that all non-key attributes of a table must be functionally
dependent on a candidate key i.e. there can be no interdependencies
among non-key attributes.
For a table to be in 3NF, there are two requirements
–
–
The table should be second normal form
No attribute is transitively dependent on the primary key
Example (Not in 3NF)
Scheme  {Title, PubID, PageCount, Price }
1.
2.
3.
4.
5.
17-09-2014
Key  {Title, PubId}
{Title, PubId}  {PageCount}
{PageCount}  {Price}
Both Price and PageCount depend on a key hence 2NF
Transitively {Title, PubID}  {Price} hence not in 3NF
Database Management Systems Placement Training
Third Normal Form (3NF)
Example 2 (Not in 3NF)
Scheme  {Studio, StudioCity, CityTemp}
1.
2.
3.
4.
5.
6.
Primary Key  {Studio}
{Studio}  {StudioCity}
{StudioCity}  {CityTemp}
{Studio}  {CityTemp}
Both StudioCity and CityTemp depend on the entire key hence 2NF
CityTemp transitively depends on Studio hence violates 3NF
Example 3 (Not in 3NF)
BuildingID
Scheme  {BuildingID, Contractor, Fee}
1.
2.
3.
4.
5.
6.
17-09-2014
100
Primary Key  {BuildingID}
150
{BuildingID}  {Contractor}
200
{Contractor}  {Fee}
250
{BuildingID}  {Fee}
300
Fee transitively depends on the BuildingID
Both Contractor and Fee depend on the entire key hence 2NF
Database Management Systems Placement Training
Contractor
Fee
Randolph
1200
Ingersoll
1100
Randolph
1200
Pitkin
1100
Randolph
1200
3NF - Decomposition
1.
2.
3.
Move all items involved in transitive dependencies to a new
entity.
Identify a primary key for the new entity.
Place the primary key for the new entity as a foreign key on the
original entity.
Example 1 (Convert to 3NF)
Old Scheme  {Title, PubID, PageCount, Price }
New Scheme  {PubID, PageCount, Price}
New Scheme  {Title, PubID, PageCount}
17-09-2014
Database Management Systems Placement Training
3NF - Decomposition
Example 2 (Convert to 3NF)
Old Scheme  {Studio, StudioCity, CityTemp}
New Scheme  {Studio, StudioCity}
New Scheme  {StudioCity, CityTemp}
Example 3 (Convert to 3NF)
Old Scheme  {BuildingID, Contractor, Fee}
New Scheme  {BuildingID, Contractor}
New Scheme  {Contractor, Fee}
17-09-2014
BuildingID
Fee
Contractor
Contractor
100
Randolph
Randolph
1200
150
Ingersoll
Ingersoll
1100
200
Randolph
Pitkin
1100
250
Pitkin
300
Randolph
Database Management Systems Placement Training
Boyce-Codd Normal Form (BCNF)
•
•
•
BCNF does not allow dependencies between attributes that belong to candidate keys.
BCNF is a refinement of the third normal form in which it drops the restriction of a nonkey attribute from the 3rd normal form.
Third normal form and BCNF are not same if the following conditions are true:
–
–
–
The table has two or more candidate keys
At least two of the candidate keys are composed of more than one attribute
The keys are not disjoint i.e. The composite candidate keys share some attributes
Example 1 - Address (Not in BCNF)
Scheme  {City, Street, ZipCode }
1.
Key1  {City, Street }
2.
Key2  {ZipCode, Street}
3.
No non-key attribute hence 3NF
4.
{City, Street}  {ZipCode}
5.
{ZipCode}  {City}
6.
Dependency between attributes belonging to a key
17-09-2014
Database Management Systems Placement Training
Boyce Codd Normal Form (BCNF)
Example 2 - Movie (Not in BCNF)
Scheme  {MovieTitle, MovieID, PersonName, Role, Payment }
1.
2.
3.
4.
5.
Key1  {MovieTitle, PersonName}
Key2  {MovieID, PersonName}
Both role and payment functionally depend on both candidate keys thus 3NF
{MovieID}  {MovieTitle}
Dependency between MovieID & MovieTitle Violates BCNF
Example 3 - Consulting (Not in BCNF)
Scheme  {Client, Problem, Consultant}
1.
2.
3.
4.
5.
6.
17-09-2014
Key1  {Client, Problem}
Key2  {Client, Consultant}
No non-key attribute hence 3NF
{Client, Problem}  {Consultant}
{Client, Consultant}  {Problem}
Dependency between attributess belonging to keys violates BCNF
Database Management Systems Placement Training
BCNF - Decomposition
1.
2.
Place the two candidate primary keys in separate
entities
Place each of the remaining data items in one of the
resulting entities according to its dependency on the
primary key.
Example 1 (Convert to BCNF)
Old Scheme  {City, Street, ZipCode }
New Scheme1  {ZipCode, Street}
New Scheme2  {City, Street}
•
Loss of relation {ZipCode}  {City}
Alternate New Scheme1  {ZipCode, Street }
Alternate New Scheme2  {ZipCode, City}
17-09-2014
Database Management Systems Placement Training
Decomposition – Loss of Information
1.
2.
3.
4.
If decomposition does not cause any loss of information it is
called a lossless decomposition.
If a decomposition does not cause any dependencies to be lost
it is called a dependency-preserving decomposition.
Any table scheme can be decomposed in a lossless way into a
collection of smaller schemas that are in BCNF form. However
the dependency preservation is not guaranteed.
Any table can be decomposed in a lossless way into 3rd normal
form that also preserves the dependencies.
•
3NF may be better than BCNF in some cases
Use your own judgment when decomposing schemas
17-09-2014
Database Management Systems Placement Training
BCNF - Decomposition
Example 2 (Convert to BCNF)
Old Scheme  {MovieTitle, MovieID, PersonName, Role, Payment }
New Scheme  {MovieID, PersonName, Role, Payment}
New Scheme  {MovieTitle, PersonName}
•
Loss of relation {MovieID}  {MovieTitle}
New Scheme  {MovieID, PersonName, Role, Payment}
New Scheme  {MovieID, MovieTitle}
•
We got the {MovieID}  {MovieTitle} relationship back
Example 3 (Convert to BCNF)
Old Scheme  {Client, Problem, Consultant}
New Scheme  {Client, Consultant}
New Scheme  {Client, Problem}
17-09-2014
Database Management Systems Placement Training
Fourth Normal Form (4NF)
•
Fourth normal form eliminates
relationships between columns.
•
To be in Fourth Normal Form,
–
–
independent
many-to-one
a relation must first be in Boyce-Codd Normal Form.
a given relation may not contain more than one multi-valued attribute.
Example (Not in 4NF)
Scheme  {MovieName, ScreeningCity, Genre)
Primary Key: {MovieName, ScreeningCity, Genre)
1.
All columns are a part of the only candidate key, hence BCNF
2.
Many Movies can have the same Genre
3.
Many Cities can have the same movie
Movie
ScreeningCity
Hard Code
Los Angles
4.
Violates 4NF
17-09-2014
Genre
Comedy
Hard Code
New York
Comedy
Bill Durham
Santa Cruz
Drama
Bill Durham
Durham
Drama
New York
Horror
Database Management Systems The Code Warrier
Placement Training
Fourth Normal Form (4NF)
Example 2 (Not in 4NF)
Scheme  {Manager, Child, Employee}
1.
2.
3.
4.
Primary Key  {Manager, Child, Employee}
Each manager can have more than one child
Each manager can supervise more than one employee
4NF Violated
Manager
Child
Employee
Jim
Beth
Alice
Mary
Bob
Jane
Mary
NULL
Adam
Example 3 (Not in 4NF)
Scheme  {Employee, Skill, ForeignLanguage}
1.
2.
3.
4.
17-09-2014
Primary Key  {Employee, Skill, Language }
Each employee can speak multiple languages
Each employee can have multiple skills
Thus violates 4NF
Database Management Systems Placement Training
Employee
Skill
Language
1234
Cooking
French
1234
Cooking
German
1453
Carpentry
Spanish
1453
Cooking
Spanish
2345
Cooking
Spanish
4NF - Decomposition
1.
2.
Move the two multi-valued relations to separate tables
Identify a primary key for each of the new entity.
Example 1 (Convert to 3NF)
Old Scheme  {MovieName, ScreeningCity, Genre}
New Scheme  {MovieName, ScreeningCity}
New Scheme  {MovieName, Genre}
Movie
Genre
Movie
ScreeningCity
Hard Code
Comedy
Hard Code
Los Angles
Bill Durham
Drama
Hard Code
New York
The Code Warrier
Horror
Bill Durham
Santa Cruz
Bill Durham
Durham
The Code Warrier
New York
17-09-2014
Database Management Systems Placement Training
4NF - Decomposition
Example 2 (Convert to 4NF)
Manager
Child
Manager
Employee
Old Scheme  {Manager, Child, Employee}
Jim
Beth
Jim
Alice
New Scheme  {Manager, Child}
Mary
Bob
Mary
Jane
Mary
Adam
New Scheme  {Manager, Employee}
Example 3 (Convert to 4NF)
Old Scheme  {Employee, Skill, ForeignLanguage}
New Scheme  {Employee, Skill}
New Scheme  {Employee, ForeignLanguage}
17-09-2014
Employee
Skill
Employee
Language
1234
Cooking
1234
French
1453
Carpentry
1234
German
1453
Cooking
1453
Spanish
2345
Cooking
2345
Spanish
Database Management Systems Placement Training
Fifth Normal Form (5NF)
•
Fifth normal form is satisfied when all tables are broken
into as many tables as possible in order to avoid
redundancy. Once it is in fifth normal form it cannot be
broken into smaller relations without changing the facts or
the meaning.
17-09-2014
Database Management Systems Placement Training
Domain Key Normal Form (DKNF)
•
The relation is in DKNF when there can be no insertion or
deletion anomalies in the database.
17-09-2014
Database Management Systems Placement Training
Transaction
• The term transaction refers to a collection of
operations that form a single logical unit of
work.
• Logical unit of database processing that
includes one or more access operations (read
-retrieval, write - insert or update, delete).
Eg., Transfer of money from one account to
another is a transaction consisting of two
updates, one to each account.
• Transaction consists of all operations executed
between the begin transaction and end
transaction.
Database Management Systems Placement Training
17-09-2014
Transaction - Example
 E.g. transaction to transfer ₹ 50 from
account A to account B:
Ti:
1.
2.
3.
4.
5.
6.
read(A)
A := A – 50
write(A)
read(B)
B := B + 50
write(B)
Granularity of data - a field, a record , or a whole disk block
(Concepts are independent of granularity)
17-09-2014
Database Management Systems Placement Training
Two Basic Operations of Transaction
Processing
•Read
(X)
Read
•Write
(X)
Write
17-09-2014
Database Management Systems Placement Training
Properties of transaction
17-09-2014
A
•Atomicity
C
•Consistency
I
•Isolation
D
•Durability
Database Management Systems Placement Training
ACID Properties
• Atomicity
Ensures whether all actions of the
transaction are done or incase of failure,
partially done transactions will be undone.
• Consistency
Execution of a transaction in isolation
preserves the consistency of the database.
17-09-2014
Database Management Systems Placement Training
ACID Properties
(cont…)
• Isolation
Isolate the transaction from the effect of
other concurrent executing transaction.
• Durability
Once a transaction is successfully
executed, its effect must persist in the
database
17-09-2014
Database Management Systems Placement Training
Transaction States
17-09-2014
Database Management Systems Placement Training
Transaction States
 Active – the initial state; the transaction stays in this state
while it is executing
 Partially committed – after the final statement has been
executed.
 Failed -- after the discovery that normal execution can no
longer proceed.
 Aborted – after the transaction has been rolled back and the
database restored to its state prior to the start of the
transaction. Two options after it has been aborted:
 restart the transaction
 can be done only if no internal logical error
 kill the transaction
 Committed – after successful completion.
17-09-2014
Database Management Systems Placement Training
Concurrent Executions
 Multiple transactions are allowed to run
concurrently in the system. Advantages are:
 increased processor and disk utilization, leading to
better transaction throughput
 E.g. one transaction can be using the CPU while another is
reading from or writing to the disk
 reduced average response time for transactions: short
transactions need not wait behind long ones.
 Concurrency control schemes – mechanisms to
achieve isolation
 that is, to control the interaction among the
concurrent transactions in order to prevent them from
destroying the consistency of the database
17-09-2014
Database Management Systems Placement Training
Schedules
 Schedule – a sequences of instructions that specify the
chronological order in which instructions of concurrent
transactions are executed
 When transactions are executing concurrently in an interleaved
fashion, the order of execution of operations from the various
transactions forms what is known as a transaction schedule (or
history).
 A transaction that successfully completes its execution will have
a commit instructions as the last statement
 A transaction that fails to successfully complete its execution
will have an abort instruction as the last statement
17-09-2014
Database Management Systems Placement Training
Schedule 1
 Let T1 transfer ₹ 50 from A to B, and T2
transfer 10% of the balance from A to B.
 A serial schedule in which T1 is followed
by T2 :
17-09-2014
Database Management Systems Placement Training
Schedule 2
A serial schedule where T2 is
followed by T1
17-09-2014
Database Management Systems Placement Training
Schedule 3
Let T1 and T2 be the transactions
defined previously. The following
schedule is not a serial schedule,
but it is equivalent to Schedule 1.
In Schedules 1, 2 and 3, the sum A + B is preserved.
17-09-2014
Database Management Systems Placement Training
Schedule 4
The following concurrent
schedule does not preserve
the value of (A + B ).
17-09-2014
Database Management Systems Placement Training
Serializability
 Basic Assumption – Each transaction preserves database
consistency.
 Thus serial execution of a set of transactions preserves database
consistency.
 A (possibly concurrent) schedule is serializable if it is equivalent to a
serial schedule. Different forms of schedule equivalence give rise to
the notions of:
1. conflict serializability
2. view serializability
 Simplified view of transactions
 We ignore operations other than read and write instructions
 We assume that transactions may perform arbitrary computations on
data in local buffers in between reads and writes.
 Our simplified schedules consist of only read and write instructions.
17-09-2014
Database Management Systems Placement Training
Conflicting Instructions
• Instructions li and lj of transactions Ti and Tj respectively,
conflict if and only if there exists some item Q accessed
by both li and lj, and at least one of these instructions
wrote Q.
1. li = read(Q), lj = read(Q). li and lj don’t conflict.
2. li = read(Q), lj = write(Q). They conflict.
3. li = write(Q), lj = read(Q). They conflict
4. li = write(Q), lj = write(Q). They conflict
• Intuitively, a conflict between li and lj forces a (logical)
temporal order between them.
– If li and lj are consecutive in a schedule and they do not
conflict, their results would remain the same even if they
Database Management Systems 17-09-2014
had been interchanged
inTraining
the schedule.
Placement
Conflict Serializability
• If a schedule S can be transformed into
a schedule S´ by a series of swaps of
non-conflicting instructions, we say
that S and S´ are conflict equivalent.
• We say that a schedule S is conflict
serializable if it is conflict equivalent to
a serial schedule
17-09-2014
Database Management Systems Placement Training
Conflict Serializability (Cont.)
• Schedule 3 can be transformed into Schedule 6, a serial schedule
where T2 follows T1, by series of swaps of non-conflicting
instructions.
– Therefore Schedule 3 is conflict serializable.
17-09-2014
Database Management Systems Placement Training
Schedule 3
Schedule 6
View Serializability
 Let S and S´ be two schedules with the same set of
transactions. S and S´ are view equivalent if the following
three conditions are met, for each data item Q,
1. If in schedule S, transaction Ti reads the initial value of Q, then in
schedule S’ also transaction Ti must read the initial value of Q.
2. If in schedule S transaction Ti executes read(Q), and that value
was produced by transaction Tj (if any), then in schedule S’ also
transaction Ti must read the value of Q that was produced by the
same write(Q) operation of transaction Tj .
3. The transaction (if any) that performs the final write(Q) operation
in schedule S must also perform the final write(Q) operation in
schedule S’.
As can be seen, view equivalence is also based purely on reads
and writes alone.
17-09-2014
Database Management Systems Placement Training
View Serializability (Cont.)
 A schedule S is view serializable if it is view equivalent to
a serial schedule.
 Every conflict serializable schedule is also view
serializable.
 Below is a schedule which is view-serializable but not
conflict serializable.
 Every view serializable
schedule that is not conflict
Database Management Systems 17-09-2014
Placement Training
serializable
has blind writes.
Concurrency Control
Need for Concurrency Control
• The Lost Update Problem
– This occurs when two transactions that access the
same database items have their operations
interleaved in a way that makes the value of some
database item incorrect.
• The Temporary Update (or Dirty Read)
Problem
– This occurs when one transaction updates a database
item and then the transaction fails for some reason
– The updated item is accessed by another transaction
before it is changed back to its original value.
17-09-2014
Database Management Systems Placement Training
Concurrency Control
• The Incorrect Summary Problem
– If one transaction is calculating an
aggregate summary function on a number
of records while other transactions are
updating some of these records, the
aggregate function may calculate some
values before they are updated and others
after they are updated.
17-09-2014
Database Management Systems Placement Training
Concurrency Control
 A database must provide a mechanism that will
ensure that all possible schedules are
 either conflict or view serializable, and
 are recoverable and preferably cascadeless
 A policy in which only one transaction can execute
at a time generates serial schedules, but provides a
poor degree of concurrency
 Testing a schedule for serializability after it has
executed is a little too late!
 Goal – to develop concurrency control protocols
that will assure serializability.
17-09-2014
Database Management Systems Placement Training
Levels of Consistency in SQL
 Serializable — default
 Repeatable read — only committed records to
be read, repeated reads of same record must
return same value. However, a transaction may
not be serializable – it may find some records
inserted by a transaction but not find others.
 Read committed — only committed records can
be read, but successive reads of record may
return different (but committed) values.
 Read uncommitted — even uncommitted
records may be read.
17-09-2014
Database Management Systems Placement Training
THANK YOU
17-09-2014
Database Management Systems Placement Training