MEKDELAAMBA UNIVERSITY

COLLEGE OF COMPUTATIONAL AND NATURAL SCIENCE

DEPARTMENT OF COMPUTER SCIENCE

Data Base Management System Course Module

(CoSc-M2061)

Module Preface
This resource module is designed and developed in support of the concept and practical applications of
the Database System Curriculum. It provides learning resources and teaching ideas. This module has
two parts, part one discusses the concept of fundamentals of database systems, and part two deals with
advanced database systems. Dear students, in chapter one you have been studied Data, information,
information System Data Management approaches Components of a Database System and Database
Management System (DBMS).

In chapter two, Database Models and Record-based Data Models have been studied. In chapter three,
you have been studied Database Modeling Using the Entity-Relationship (ER) Database Model.

In chapter three, Database Modeling Using the Entity-Relationship (ER) Database Model; Properties of
Relational Databases - Basic Concepts in Relational Database; Building Blocks of the Relational
Database Model; Types of Attributes, Entity versus Attributes, Degree of a Relationship, and about
Cardinality of a Relationship. In the end, Relational Views and entity-relationship diagrams are briefly
discussed.

Chapter Four is about Database Design; like three levels of Database Design and Conceptual Database
Design; The Entity-Relationship (E-R) Model and how to design E-R Diagram.

Chapter Five is discussed all about the Domains, Attributes, Tuples, and Relations; and Functional
Dependency and its analysis. Finally, it discusses Normalization and Normal Forms; like First Normal
Form (1NF), Second Normal Form (2NF), and Third Normal Form (3NF).

I
Chapter Six, discuss all Advanced SQL and Query optimization and its introduction. And also about
Data Manipulation Language, Assertion, Views, Stored Procedures, SQL queries, and Relational
Algebra, Translating SQL queries to Relational Algebra, Query Processing, and Optimization, Query
Processing, Approaches to Query Optimization, Transformation Rules for Relational Algebra, Sequence
for Applying Transformation Rules.

Chapter Seven, about overview of Concurrency Control and Transactions Processing, Transaction
processing system, State of a Transaction, Ways of Transaction Execution, Problems Associated with
Concurrent Transaction Processing, Concurrency Control Techniques, Granularity of data items.

Chapter Eight, is all about Transactions and Recovery, Database Recovery Techniques, Recovery
Techniques for Inconsistent Database State.

In chapter Nine, Distributed Database Systems, Data Distribution Strategies, Functions of a DDBMS,
Issues in DDBMS How is data stored in DDBMS?, Homogeneous and Heterogeneous Distributed
Databases, Advantages and disadvantages of DDBMS, Why DDBMS/Advantages, Disadvantages of
DDBMS, Query Processing and Transaction Management in DDBMS Query Processing.

Chapter Ten, all about Introduction to Object-Oriented Database Systems Object Orientation, Object
Orientation, OO Contribution areas, Evolution of OO Concepts, Object-oriented Concepts, Object
Classification, Characteristics of OO Data Model, OO Data Model has the following characteristics,
OODBMS, OO, and Database Design and OODBMS Advantages are discussed.

In chapter Eleven, Database Administration and Security, Security Issues and general considerations,
RAID technology (Redundant Array of Independent Disks), Security at different Levels of Data, Role of
DBA in Database Security, and Approaches to Database Security are discussed.

II
Table of Contents
Module Preface.............................................................................................................................................. I
PART ONE.................................................................................................................................................. IX
FUNDAMENTALS OF DATABASE SYSTEM ....................................................................................... IX
Chapter One .................................................................................................................................................. 1
1. Introduction .......................................................................................................................................... 1
1.1. Data, Information, information System ........................................................................................ 1
1.2. Information System and Organization, database system .............................................................. 1
1.3. Data Management approaches ...................................................................................................... 2
1.4. Components of a Database System .............................................................................................. 8
1.5. Database Management System (DBMS) .................................................................................... 12
1.5.1. Components of DBMS Environment ................................................................................. 13
1.6. Database Development Life Cycle ............................................................................................. 14
1.7. Database Systems Architecture .................................................................................................. 16
1.8. Defines DBS schemas at three levels: ........................................................................................ 20
Review exercises one ................................................................................................................................. 22
Chapter- TWO ............................................................................................................................................ 23
2. Database Model .................................................................................................................................. 23
2.1. Record-based Data Models......................................................................................................... 23
Review exercise two ................................................................................................................................... 29
Chapter Three ............................................................................................................................................. 30

III
3. Database Modelling Using the Entity-Relationship (ER) Database Model ....................................... 30
3.1. Properties of Relational Databases - Basic Concepts in Relational Database ............................ 30
3.2. Building Blocks of the Relational Database Model ................................................................... 30
3.2.1. Types of Attributes ............................................................................................................. 31
3.2.2. Entity versus Attributes ...................................................................................................... 32
3.2.3. Degree of a Relationship .................................................................................................... 33
3.2.4. Cardinality of a Relationship .............................................................................................. 33
3.3. Relational Views ........................................................................................................................ 35
3.4. ENTITY - RELATIONSHIP DIAGRAMS ............................................................................... 37
Review exercise Three ............................................................................................................................... 39
Chapter Four ............................................................................................................................................... 40
4. Database Design ..................................................................................................................................... 40
4.1. The Three levels of Database Design .............................................................................................. 41
4.2. Conceptual Database Design ........................................................................................................... 42
4.2.1. The Entity Relationship (E-R) Model ...................................................................................... 43
4.2.2. Developing an E-R Diagram .................................................................................................... 43
Review Exercise Four................................................................................................................................. 56
Chapter Five ............................................................................................................................................... 57
5.1. Domains, Attributes, Tuples, and Relations .................................................................................... 58
5.2. Functional Dependency ................................................................................................................... 59
5.2.1. Functional Dependency analysis .............................................................................................. 62
5.3. Normalization and Normal Forms ................................................................................................... 64
5.3.1 First Normal Form (1NF) .......................................................................................................... 65
5.3.2. Second Normal Form (2NF) ..................................................................................................... 66
5.3.3. Third Normal Form (3NF) ........................................................................................................ 67
Review Exercise Five ................................................................................................................................. 68
PART TWO ................................................................................................................................................ 69
ADVANCED DATABASE SYSTEM....................................................................................................... 69
Chapter six .................................................................................................................................................. 70
Advanced SQL and Query optimization .................................................................................................... 70
6. Introduction ........................................................................................................................................ 70
6.1. Data Manipulation Language .......................................................................................................... 72
6.2. Assertion ......................................................................................................................................... 72

IV
 6.3. Views ............................................................................................................................................... 72
6.4. Stored Procedures ............................................................................................................................ 73
6.5. SQL queries and Relational Algebra ............................................................................................... 74
6.5.1. Relational Algebra .................................................................................................................... 74
6.5.2. Translating SQL queries to Relational Algebra........................................................................ 76
6.2. Query Processing and Optimization ................................................................................................ 77
6.2.1. Query Processing ...................................................................................................................... 77
6.2.2. Approaches to Query Optimization .......................................................................................... 81
6.2.3. Transformation Rules for Relational Algebra .......................................................................... 81
6.2.4. Sequence for Applying Transformation Rules ......................................................................... 83
Review Exercise six ................................................................................................................................... 92
Chapter- Seven ........................................................................................................................................... 93
Concurrency Control and Transactions Processing .................................................................................... 93
7.1. Transaction processing system ........................................................................................................ 93
7.1.1. State of a Transaction ............................................................................................................... 95
7.1.2. Ways of Transaction Execution................................................................................................ 96
7.2. Problems Associated with Concurrent Transaction Processing ...................................................... 98
7.2.1. Concurrency Control Techniques ........................................................................................... 100
7.3. Granularity of data items ............................................................................................................... 105
Review Exercise Seven ............................................................................................................................ 105
Chapter - Eight ......................................................................................................................................... 107
Database Recovery ................................................................................................................................... 107
8.1. Transactions and Recovery ............................................................................................................ 109
8.2. Database Recovery Techniques ..................................................................................................... 111
8.2.1. Recovery Techniques for Inconsistent Database State ........................................................... 112
Review Exercise Eight ............................................................................................................................. 113
Chapter – Nine.......................................................................................................................................... 114
Distributed Database Systems .................................................................................................................. 114
9.1. Data Distribution Strategies .......................................................................................................... 114
9.2. Functions of a DDBMS ................................................................................................................. 116
9.3. Issues in DDBMS How is data stored in DDBMS? ...................................................................... 116
9.4. Homogeneous and Heterogeneous Distributed Databases ............................................................ 119
9.5. Advantages and disadvantages of DDBMS................................................................................... 120

V
 9.5.1. Why DDBMS/Advantages ..................................................................................................... 120
9.5.2. Disadvantages of DDBMS ..................................................................................................... 120
9.6. Query Processing and Transaction Management in DDBMS Query Processing .......................... 121
Review Exercise Nine .............................................................................................................................. 124
Chapter – Ten ........................................................................................................................................... 125
Introduction to Object-Oriented Database Systems Object Orientation................................................... 125
10.1. Object Orientation ....................................................................................................................... 126
10.2. OO Contribution areas ................................................................................................................. 126
10.3. Evolution of OO Concepts .......................................................................................................... 126
10.4. Object oriented Concepts ............................................................................................................ 127
10.4.1 Object Classification.............................................................................................................. 132
10.5. Characteristics of OO Data Model .............................................................................................. 132
OO Data Model has the following characteristics ............................................................................... 132
10.5. OODBMS .................................................................................................................................... 133
10.5.1 OO and Database Design....................................................................................................... 133
10.5.2 OODBMS Advantages .......................................................................................................... 134
Review Exercise Ten ................................................................................................................................ 134
Chapter - Eleven ....................................................................................................................................... 136
Database Administration and Security ..................................................................................................... 136
11.1 Security Issues and general considerations .................................................................................. 139
11.2. RAID technology (Redundant Array of Independent Disks) ..................................................... 142
11.3. Security at different Levels of Data ............................................................................................. 143
11.4. Role of DBA in Database Security .............................................................................................. 145
11.5. Approaches to Database Security ................................................................................................ 145
Review Exercise Eleven ........................................................................................................................... 146
References ................................................................................................................................................ 147

VI
 Table of Figures

Figure 1 data base approach modele ...................................................................................................................................7

Figure 2 Three-level ANSI-SPARC Architecture of a Database System ..........................................................................17
Figure 3 ANSI-SPARC Architecture and Database Design Phases ..................................................................................17
Figure 4 Differences between Three Levels of ANSI-SPARC Architecture ....................................................................20
Figure 5 hierarchical data model .......................................................................................................................................24
Figure 6 Network Data Model ...........................................................................................................................................26
Figure 7 terminologies in database ....................................................................................................................................28
Figure 8 levels of database design .....................................................................................................................................41
Figure 9 query processing .................................................................................................................................................79
Figure 10 states of transaction ..........................................................................................................................................96
Figure 13 centralized and Distributed database ...............................................................................................................114
Figure 14 horizontal fragmentation .................................................................................................................................117
Figure 15 horizontal fragmentation .................................................................................................................................118
Figure 16 representation of objects .................................................................................................................................128
Figure 17 representation of object and method ...............................................................................................................129
Figure 18 mwessaging process in redal worled events....................................................................................................130
Figure 19 class assigning techniques ...............................................................................................................................131
Figure 20 OO Data Model ...............................................................................................................................................133

VII
 List of tables
Table 1 locking thechnique .............................................................................................................................................101
Table 2 Transaction records ............................................................................................................................................111
Table 3 OO vs. E-R Model Components.........................................................................................................................133

VIII
 PART ONE
FUNDAMENTALS OF DATABASE SYSTEM

IX
X
 Chapter One
1. Introduction
1.1. Data, Information, information System
Data: The term 'DATA' can be defined as the value of an attribute of an entity. It is a collection
of raw facts, figures and concepts. Data cannot be used for decision making unless it is processed
or organized in useful form.
Information: A processed data is meaningful to the user. It is useful for decision-making.
An information system (IS) is a set of interrelated elements or components that collect (input),
manipulate (process), and disseminate (output) data and information and provide a feedback
mechanism to meet an objective.
In information systems:
 Input is the activity of gathering and capturing raw data
 Processing involves converting or transforming data into useful outputs.
 Output involves producing useful information, usually in the form of documents and reports.
 In information systems, feedback is output that is used to make changes to input or
processing activities.
1.2. Information System and Organization, database system
Information System does not exist without organization. That is, organization of data is
necessary if data is voluminous. Information System is a support system for the organizational
activity to achieve a certain goal.
A database system is basically a computerized record keeping system. Users of the database can
perform a variety of operations. Such as:

Adding new data to empty file

Adding new data to existing file
Retrieving data from existing file
Modifying data to existing file
Deleting data from existing file
Searching for target information

1
 1.3. Data Management approaches
Data management passes through the different levels of development along with the
development in technology and services. These levels could be best described by categorizing
the levels into three levels or types of development/approach. Even though there is an advantage
and a problem overcomes at each new data handling approach/level, all methods or approaches
of data management are in use to some extent. The major three approaches/levels are discussed
as follows:
1. Manual Approach
In the manual data handling approach, data storage and retrieval follows the primitive and
traditional way of data/information handling where cards and paper are used for the purpose.
Typing the data on paper and put in a file cabinet. The data storage and retrieval will be
performed using human labour. This approach Works well if the number of items to be stored is
small.

Limitations of the Manual approach

o Prone to error
o Data loss: due to damaged papers or unable to locate it.
o Redundancy: multiple copies of the same data within the organization.
o Inconsistency: Modifications are not reflected on all multiple copies
o Difficult to update, retrieve, integrate
o You have the data but it is difficult to compile the information
o Limited to small size information
o Cross referencing is difficult
An alternative approach of data handling is a computerized way of dealing with the information.
The computerized approach could also be either decentralized or centralized base on where the
data resides in the system.
2. File based Approach
After the introduction of computer for data processing to the business community, the need to
use the device for data storage and processing increase. File based data handling approaches
were an early attempt to computerize the manual filing system. There were, and still are, several
computer applications with file based processing used for the purpose of data handling. It is a
collection of application programs that performs services for the end users. In such systems,

2
every application program that provides service to end users defines and manage its own data.
Such systems have number of programs for each of the different applications in the organization.
Moreover, this approach is the decentralized computerized data handling method.
Limitations of the File Based approach
As business application become more complex and demanding more flexible and reliable data
handling methods, the shortcomings of the file-based system became evident. These
shortcomings include, but not limited to:
Separation/Isolation of data
When data is isolated in separate files, it is difficult to access data that should be available. This
is because; there is no concept of relationship between files. Therefore, we need to create a
temporary file for the participating files.
Duplication of data (Redundancy)
This is concerning with storage of similar information in multiple files.
The following are some of the disadvantage of redundancy:
 It costs time and money to enter the data
 It takes up additional storage space (memory space)
 Inconsistency: this is loss of data integrity. For instance, if modification in the child table
is unable to be reflected on the parent table.
Data Dependence
Changes to an existing structure are difficult to make. Example: change in the size of Student
Name (from 20 characters to 30 characters) requires a new program to convert student file to a
new format. The new program opens original student file, open a temporary file, read records
from original student file and write to the temporary file, delete the original student file and
finally rename the temporary file as student file. It is time consuming and Prone to error.

Incompatible file formats

The structure of file is dependent on the application programs. Incompatibility of files makes
them difficult to process jointly. Example: consider two files with in the same enterprise but in
different departments, or in different branches: If the first file is constructed using COBOL and
the second file is written using C++, then there will be a problem of integrity.

3. Database Approach
What is a Database?

3
A database is a collection of related data in an organized way. Most of the time, organization is
in tabular form. E.g. book database

The organization of the database becomes necessary when the data is voluminous. Otherwise,
managing data will be very difficult. An organization must have accurate and reliable data for
effective decision-making. To this end, the organization maintains records on the various facets
maintaining relationships among them. Such related data are called a database. Generally, a
database is an organized collection of related information. The organized information or database
serves as a base from which desired information can be retrieved or decision made by further
recognizing or processing the data. People use several databases in their day-to-day life.
Dictionary, Telephone directory, Library catalog, etc are example for databases where the entries
are arranged according to alphabetical or classified order.
E.g. A Manufacturing Company with product data
A Bank with account data

A Hospital with patients

A University with Students

A government with planning data

What is a database system?
It is a computerized record keeping system, which stores related data in an organized way. The
overall purpose of a database system is to store information and to allow users to add, delete,
retrieve, search, query and update that information upon request. The information concerned can
be anything that is deemed to be of significance to the individual or organization the system is
intended to serve. That is, needed to assist in the general process of running the business of that
individual or organization. A database system is an integrated collection of related files, along
with details of the interpretation of the data contained therein. Database system is nothing more
than a computer-based record keeping system i.e. a system whose overall purpose is to record
and maintain information/data.
Thus in database approach:

4
 Database is just a computerized record keeping system or a kind of electronic filing cabinet.
 Database is a repository for collection of computerized data files.
 Database is a shared collection of logically related data designed to meet the information
needs of an organization. Since it is a shared corporate resource, the database is integrated
with minimum amount of or no duplication.
 Database is a collection of logically related data where these logically related data comprises:
entities, attributes, relationships, and business rules of an organization's information.
 In addition to containing data required by an organization, database also contains a
description of the data, which called as “Metadata” or “Data Dictionary” or “Systems
Catalogue”, or “Data about Data”.
 Since a database contains information about the data (metadata), it is called a self-descriptive
collection on integrated records.
 The purpose of a database is to store information and to allow users to retrieve and update
that information on demand.
 Database is designed once and used simultaneously by many users.
 Unlike the traditional file, based approach in database approach there is program data
independence. That is the separation of the data definition from the application. Thus the
application is not affected by changes made in the data structure and file organization.
 Each database application will perform the combination of creating database, reading,
updating and deleting data.

The advantages of a database approach over the traditional and paper-based methods of record
keeping will include the following:

Compactness: no need for possibly voluminous paper files.

Speed: the machine can retrieve and change data faster than a human can. In particular, ad hoc,
spur-of-the-moment queries

(“Do we have more red screws than blue ones?”) can be answered quickly without any need for
time consuming manual or visual searches.
Accuracy: timely, accurate and up-to-date information is available on demand at any time.
The foregoing benefits apply with even more force in a multi-user environment where the
database is likely to be much larger and much more complex than in the single user case. In a

5
multi-user environment the database system provides the enterprise with centralized control of its
data. The centralized approach has the following advantages:
Data can be shared: two or more users can access and use same data instead of storing data in
redundant manner for each user.
Redundancy can be reduced: in non-database or non-centralized systems, each application or
department keeps its own private files. The files may hold common data elements that exist as
part of the enterprises data. This will lead to considerable redundancy in stored data, with
resultant waste in storage space. For example, a personnel application and an education records
application might both own a file that includes department information for employees. Note that,
this is not to say we should eliminate all redundancies. Sometimes there are sound reasons for
maintaining several copies of the same data.
Inconsistency can (to some extent) avoided: If there are a number of files, which store similar
data, elements among other sorts of data then when a change is made to a particular data (among
the common ones) this change need to be done throughout the system where there is such data
stored. This is not, often, the case. Some of the data might be updated and others left as they are
which results in inconsistent information about the same phenomena.
Standards can be enforced: Standardizing data representation is particularly desirable as an aid
to data interchange or migration of data between systems. Likewise, data naming and
documentation standards are also very desirable as they facilitate data sharing and
understandability.
Security restrictions can be applied: since the data is stored in, one place/area all accesses to
the data can be regulated by the system through some defined rules built into the system. The
system ensures that the only means of access to the database is through proper channels.
Different rules can be established for each type of access (retrieve, insert, delete, etc.) to each of
information to the database.
Integrity can be maintained The problem of integrity is the problem of ensuring the data in the
database is accurate. Inconsistency between two entries that represent the same “fact” is an
example of lack of integrity. It is more serious in a multi-user environment where one user may
enter bad data and other users may go on working on the updated data as if it were a correct one.
Conflicting requirements can be balanced: knowing the overall requirements of the enterprise
the Database Administrator (DBA) can structure the system so as to provide an overall service
that is best for the enterprise. For example, a representation can be chosen for the data in storage

6
that gives fast access for the most important applications (possibly at the cost of poorer
performance for certain other applications).
Transaction support can be provided: basic demands of any transaction support systems are
implanted in a full scale DBMS.
Improved decision support: the database will provide information useful for decision making.
Less labor: unlike the other data handling methods, data maintenance will not demand much
resource
Centralized information control: since relevant data in the organization will be stored at one
repository, it can be controlled and managed at the central level
Limitations and risk of Database Approa
o Introduction of new professional and specialized personnel.
o Complexity in designing and managing data
o The cost and risk during conversion from the old to the new system
o High cost to be incurred to develop and maintain the system
o Complex backup and recovery services from the users perspective
o Reduced performance due to centralization and data independency
o High impact on the system when failure occurs to the central system.
Note: Database System (DBS) contains:

The Database + The DBMS + Application Programs (what users interact with)

Figure 1 data base approach modele

7
 1.4. Components of a Database System
A database system involves four major components, namely, data, hardware, software and users
and designers of database. A brief discussion will follow on each of these components.
Data: The actual data stored in the database system may be stored as a single database or
distributed in many distinct files and treated as one. Is the system a single-user or multi-user
one? How are we going to achieve the utmost possible performance concerning the data storage
and maintenance? What other benefits or drawbacks do we expect as the result of placement or
structure of the database?. These and similar issues might be concerned with the way the data
stored in the system.
Hardware: This portion of the system consists of secondary storage media (disks, tapes and
optical media) that are used to hold the stored data and associated device controllers (hard disk
controller, etc.); and the processor(s) and associated main memory that are used to support the
execution of the database system software.

Software: This is the software. Database Management System (DBMS) that is responsible for
the overall management of communications between the user and the database. It is found
between the data and the users, which, in other words, means the data is entirely covered or
shielded by the DBMS software. The DBMS provides facilities for operating on the database.
This is the most important software component in the overall system that allows the user to
interact with the data.

Users and Designers of Database: As people are one of the components in DBS environment,
there are group of roles played by different stakeholders of the designing and operation of a
database system.
Database Administrator (DBA)
 Responsible to oversee, control and manage the database resources (the database itself, the
DBMS and other related software)
 Authorizing access to the database
 Coordinating and monitoring the use of the database
 Responsible for determining and acquiring hardware and software resources
 Accountable for problems like poor security, poor performance of the system
 Involves in all steps of database development

8
We can have further classifications of this role in big organizations having huge amount of data
and user requirement.
Data Administrator (DA): is responsible on management of data resources. It involves in
database planning, development, maintenance of standards policies and procedures at the
conceptual and logical design phases.
Database Administrator (DBA): is more technically oriented role. It is responsible for the
physical realization of the database and involved in physical design, implementation, security
and integrity control of the database.
Database Administrator a person that is responsible for all technical operations or details of the
database system. DBA is the user that controls the enterprises data resource. The functions of the
DBA include the following.
Defining the conceptual schema: Will directly participate or help on the process of identifying
the content of the database, i.e., what information is to be held in the database and create the
corresponding conceptual schema using the conceptual DDL.
Defining the internal schema: The DBA must also decide how the data is to be represented in
the stored database and then create the corresponding storage structure definition (the internal
schema) using the internal DDL (including associated mapping between the internal and
conceptual schema).
Liaising with users: By communicating with users the DBA will ensure that the data they
require is available, and to write (or help users write) the necessary external schemas using the
applicable external DDL. Other functions include consulting on application design, providing
technical education, assisting with problem determination and resolution, and similar system
related professional services.
Defining security and integrity rules: Since security and integrity rules are part of the
conceptual schema, the conceptual DDL should include facilities for specifying such rules.
Defining backup and recovery procedures: In the event of damage to any portion of a
database, caused by human error or failure in the hardware or operating system, it is essential to
be able to repair the data concerned with the minimum of delay and with as little effect as
possible on the rest of the system. The DBA should define and implement appropriate backup
and recovery scheme.

9
Monitoring performance and responding to changing requirements: Periodic performance
analysis should be done by the DBA and based on the results obtained propose for improved
systems and or do the modifications on the existing data definitions
Database Designer (DBD)
Identifies the data to be stored and choose the appropriate structures to represent and store the
data.
Should understand the user requirement and should choose how the user views the database.
Involve on the design phase before the implementation of the database system.
We have two distinctions of database designers, one involving in the logical and conceptual
design and another involving in physical design.
Logical and Conceptual DBD
Identifies data (entity, attributes and relationship) relevant to the organization
Identifies constraints on each data
Understand data and business rules in the organization
Sees the database independent of any data model at conceptual level and consider one specific
data model at logical design phase.
Physical DBD
Take logical design specification as input and decide how it should be physically realized.
Map the logical data model on the specified DBMS with respect to tables and integrity
constraints. (DBMS dependent designing)
Select specific storage structure and access path to the database
Design security measures required on the database
Application Programmer and Systems Analyst
System analyst determines the user requirement and how the user wants to view the database.
The application programmer implements these specifications as programs; code, test, debug,
document and maintain the application program.
Determines the interface on how to retrieve, insert, update and delete data in the database.
The application could use any high level programming language according to the availability, the
facility and the required service.
Application programmers who are responsible for writing application programs that use the
database using some programming language such as COBOL, Pascal, or a programming
language built-in to the DBMS.

10
End-users: These are those people who are engaged on processing different types of operations
on the database system. Users are workers, whose job requires accessing the database frequently
for various purpose. There are different group of users in this category.
Naïve Users:
Sizable proportion of users
Unaware of the DBMS
Only access the database based on their access level and demand
Use standard and pre-specified types of queries.
Sophisticated Users
Are users familiar with the structure of the Database and facilities of the DBMS.
 Have complex requirements
 Have higher level queries
 Are most of the time engineers, scientists, business analysts, etc
Casual Users
Users who access the database occasionally.
Need different information from the database each time.
Use sophisticated database queries to satisfy their needs.
Are most of the time middle to high level managers.
Generally, End users are those that interact with the system from online workstations or
terminals that use an application program developed by application programmers or those that
query the system through an interface provided by the DBMS.
These users can be again classified as “Actors on the Scene” and “Workers Behind the Scene”.
Actors On the Scene:
Data Administrator
Database Administrator
Database Designer
End Users
Workers Behind the Scene
DBMS designers and implementers: who design and implement different DBMS software.
Tool Developers are experts who develop software packages that facilitates database system
designing and use. Prototype, simulation, code generator developers could be an example.
Independent software vendors could also be categorized in this group.

11
Operators and Maintenance Personnel are system administrators who are responsible for
actually running and maintaining the hardware and software of the database system and the
information technology facilities.
1.5. Database Management System (DBMS)
'Database management technology' and the resulting software are known as 'database
management system' (DBMS) which they manage a computer stored database or collection of
data.
A database management system (DBMS) is a software system that allows access to data
contained in a database. The objective of the DBMS is to provide a convenient and effective
method of defining, storing and retrieving the information contained in the database. The DBMS
interfaces with the application programs, so that multiple applications and users can use the data
contained in the database. In addition, the DBMS exerts centralized control of the database,
prevents fraudulent or unauthorized users from accessing the data, and ensures the privacy of the
data.
Database Management System (DBMS) is the tool for creating and managing the large amounts
of data efficiently and allowing it to persist for a long periods of time. Hence DBMS is a general-
purpose software that facilities the processes of defining, constructing, manipulating, and sharing
database.
 Defining: involves specifying data types, structure and constraints.
 Constructing: is the process of storing the data into a storage media.
 Manipulating: is retrieving and updating data from and into the storage.
 Sharing: allows multiple users to access data.
A DBMS is software that enables users to define, create, maintain and control access to the
database. Example: Ms Access, FoxPro, SQL Server, MySQL, Oracle.
The phrase “Database System” is used to colloquially refer to database and database
management system (DBMS).
 Database Management System (DBMS) is a Software package used for providing
EFFICIENT, CONVENIENT and SAFE MULTI-USER (many people/programs accessing
same database, or even same data, simultaneously) storage of and access to MASSIVE
amounts of PERSISTENT (data outlives programs that operate on it) data.
 A DBMS also provides a systematic method for creating, updating, storing, retrieving data in
a database.

12
 DBMS also provides the service of controlling data access, enforcing data integrity,
managing concurrency control, and recovery. Having this in mind, a full scale DBMS should
at least have the following services to provide to the user.
1. Data storage, retrieval and update in the database
2. A user accessible catalogue
3. Transaction support service: ALL or NONE transaction, which minimize data
inconsistency.
4. Concurrency Control Services: access and update on the database by different
users simultaneously should be implemented correctly.
5. Recovery Services: a mechanism for recovering the database after a failure must be
available.
6. Authorization Services (Security): must support the implementation of access and
authorization service to database administrator and users.
7. Support for Data Communication: should provide the facility to integrate with data
transfer software or data communication managers.
8. Integrity Services: rules about data and the change that took place on the data,
correctness and consistency of stored data, and quality of data based on business
constraints.
9. Services to promote data independency between the data and the application
1.5.1. Components of DBMS Environment
A DBMS is software package used to design, manage, and maintain databases. Each DBMS
should have facilities to define the database, manipulate the content of the database and control
the database. These facilities will help the designer, the user as well as the database administrator
to discharge their responsibility in designing, using and managing the database. It provides the
following facilities:
 Data Definition Language (DDL):
o Language used to define each data element required by the organization.
o Commands for setting up schema or the intension of database
o These commands are used to setup a database, create, delete and alter table with the
facility of handling constraints
o Allows DBA or user to describe and name entitles, attributes and relationships required
for the application.

13
 o Specification notation for defining the database schema
 Data Manipulation Language (DML):
o Is a core command used by end-users and programmers to store, delete, and upate the
data in the database e.g. SQL
o Provides basic data manipulation operations on data held in the database.
o Language for manipulating the data organized by the appropriate data model
 Data Query Language (DQL):
o Language for accessing or retrieving the data organized by the appropriate data model
o Since the required data or Query by the user will be extracted using this type of language,
it is also called "Query Language"
o Procedural DQL: user specifies what data is required and how to get the data.
o Non-Procedural DQL: user specifies what data is required but not how it is to be
retrieved
 Data Dictionary (DD):
o Due to the fact that a database is a self describing system, this tool, Data Dictionary, is
used to store and organize information about the data stored in the database.
 Data Control Language (DCL):
o Database is a shared resource that demands control of data access and usage. The
database administrator should have the facility to control the overall operation of the
system.
o Data Control Languages are commands that will help the Database Administrator to
control the database.
o The commands include grant or revoke privileges to access the database or particular
object within the database and to store or remove database transactions
1.6. Database Development Life Cycle
As it is one component in most information system development tasks, there are several steps in
developing a database system. Here more emphasis is given to the design phases of the database
system development life cycle. The major steps in database system development are;
1. Planning: that is identifying information gap in an organization and propose a database
solution to solve the problem.

14
2. Analysis: that concentrates more on fact finding about the problem or the opportunity.
Feasibility analysis, requirement determination and structuring, and selection of best
design method are also performed at this phase.
3. Design: in database system development more emphasis is given to this phase. The phase
is further divided into three sub-phases.
A. Conceptual Design: concise description of the data, data type, relationship
between data and constraints on the data.
 There is no implementation or physical detail consideration.
 Used to elicit and structure all information requirements.
B. Logical Design: a higher level conceptual abstraction with selected specific
database model to implement the data structure.
 It is particular DBMS independent and with no other physical
considerations.
C. Physical Design: physical implementation of the upper level design of the
database with respect to internal storage and file structure of the database for the
selected DBMS.
 To develop all technology and organizational specification.
4. Implementation: the testing and deployment of the designed database for use.
5. Operation and Support: administering and maintaining the operation of the database
system and providing support to users.
Basic Concepts

 Database Design: The activity of specifying the schema of a database in a given data
model
 Database Schema: The structure of a database that:
o Captures data types, relationships and constraints in data
o Is independent of any application program
o Changes infrequently
 Data Model:
o A set of primitives for defining the structure of a database.
o A set of operations for specifying retrieval and updates on a database
o Examples: Relational, Hierarchical, Networked, Object-Oriented
 Database Instance or State: The actual data contained in a database at a given time.

15
 1.7. Database Systems Architecture
There may be several types of architectures of database systems. However, the following
architecture (ANSI/SPARC) is applicable to most modern database systems. External level,
Conceptual level and Internal level.
 All users should be able to access same data. This is important since the database is
having a shared data feature where all the data is stored in one location and all users
will have their own customized way of interacting with the data.
 A user's view is unaffected or immune to changes made in other views. Since the
requirement of one user is independent of the other, a change made in one user’s view
should not affect other users.
 Users should not need to know physical database storage details. As there are naïve
users of the system, hardware level or physical details should be a black-box for such
users.
 DBA should be able to change database storage structures without affecting the users'
views. A change in file organization, access method should not affect the structure of
the data which in turn will have no effect on the users.
 Internal structure of database should be unaffected by changes to physical aspects of
storage.
 DBA should be able to change conceptual structure of database without affecting all
users. In any database system, the DBA will have the privilege to change the structure
of the database, like adding tables, adding and deleting an attribute, changing the
specification of the objects in the database.
All the above and much other functionality are possible due to the three level ANSI-SPARC
Database System Architectures.

16
Figure 2 Three-level ANSI-SPARC Architecture of a Database System
ANSI-SPARC Architecture and Database Design Phases

Figure 3 ANSI-SPARC Architecture and Database Design Phases

The Database System Architecture is consists of the three levels: External level, conceptual
level, Internal level.
External Level:

17
The external level is the one closest to the users, i.e., it is the one concerned with the way the
data is viewed by individual users. An external view is the content of the database as seen by
some particular user (i.e., to that user the database is similar to the view he is
working/accessing).
Each external view is defined by a means of an external schema, which consists basically of
definitions of each of the various external record types in that external view. The external
schema is written using the external DDL portion of the user’s data sub language.
External level is users' view of the database. Describes that part of database that is relevant to a
particular user. Different users have their own customized view of the database independent of
other users.
Conceptual Level:
o The conceptual level is found in between the other two. It is a representation of the entire
information content of the database including the relations with one another and security and
integrity rules, etc.
o It is the view of the data as it really is or by its entirety rather than as users are forced to see it
by the constraints of (for example) the particular language or hardware they might be using.
o The conceptual view is defined by means of the conceptual schema, which is written using
another DDL, the conceptual DDL of the data sublanguage in use. If data independence is to
be achieved, then those conceptual DDL must not involve any considerations of storage
structure or access technique. Thus there must be no reference in the conceptual schema to
stored field representations, stored record sequence, indexing, hashing addressing, pointers or
any other storage and access details.
o The conceptual schema includes a great many additional features, such as the security and
integrity rules.
Conceptual level is community view of the database. Describes what data is
stored in database and relationships among the data.
Internal Level:
Is the one closest to the physical storage, i.e., it is concerned with the way the data is physically
stored.
o Is a low-level representation of the entire database?
The internal view is described by means of the internal schema, which not only defines the
various stored record types but also specifies what indexes exist, how stored fields are

18
represented, what physical sequence the stored records are in, and so on. The internal schema is
written using yet another DDL-the internal DDL.
There will be many distinct external views, each consisting of a more or less abstract
representation of some portion of the total database, and there will be precisely one conceptual
view, consisting of a similarly abstract representation of the database in its entirety. Note that
most users will not be interested in the total database, but only in some restricted portion of it.
Likewise, there will be precisely one internal view, representing the total database as physically
stored. The following example will clarify the levels to some extent.
At the conceptual level, the database contains information concerning an entity type called
employee. Each individual employee occurrence has an employee_number (six characters), a
department_number (four characters), and a salary (five decimal digits).
At the internal level, employees are represented by a stored record type called stored_emp,
twenty bytes long. Stored_emp contains four stored fields: a six byte prefix (presumably
containing control information such as flags or pointers), and three data fields corresponding to
the three properties of employees. In addition, stored_emp records are indexed on the empno
field by an index called empx, whose definition is not shown. The Pascal user has an external
view of the database in which employee is represented by a Pascal record containing two fields
(department numbers are of no interest to this user and therefore been omitted from the view).
The record type is defined according to the syntax and declaration rules in Pascal.
Similarly, the COBOL user has an external view in which each employee is represented by a
COBOL record containing two fields (this time salary is not needed by this user and omitted).
The record type is defined according to COBOL rules.
Notice that: the corresponding objects can have different names at each level. The employee
number is referred to as empno in the Pascal view, as emp# in the internal view and as
employee_number in the conceptual view. In general, to define the correspondence between the
conceptual view and the internal view; and the conceptual view and the external view we need an
operation called mapping. The mappings are important, for example, fields can have different
data types, field and record names can be changed, and several conceptual fields can be
combined into a single external field, and so on.
Internal level is the physical representation of the database on the computer. Describes how the
data is stored in the database.

19
The following example can be taken as an illustration for the difference between the three levels
in the ANSI-SPARC database system Architecture. Where:
 The first level is concerned about the group of users and their respective data requirement
independent of the other.
 The second level is describing the whole content of the database where one piece of
information will be represented once.
 The third level

Figure 4 Differences between Three Levels of ANSI-SPARC Architecture

1.8. Defines DBS schemas at three levels:

Internal schema: at the internal level to describe physical storage structures and access
paths. Typically uses a physical data model.
Conceptual schema: it is at the conceptual level to describe the structure and constraints for
the whole database for a community of users. Uses a conceptual or an implementation data
model.
External schema: it is at the external level to describe the various user views. Usually uses
the same data model as the conceptual level.
Data Independence
Define as the ability (immunity) of applications to change storage structure and access technique
without modifying the main application.
In older systems, the way in which the data is organized in secondary storage, and the technique
for accessing it, are both dictated by the requirements of the application under consideration, and

20
moreover that knowledge of that data organization and that access technique is built into the
application logic and code. In such type of systems it is impossible to change the storage
structures (how the data is physically stored) or access technique (how it is accessed) without
affecting the application. The applications mentioned are simply programs that are designed to
specific tasks where every knowledge of the data structure and the access mechanism is also
defined within itself.
In database systems, it would be extremely undesirable to allow applications to be data
dependent. Major reasons are:
Different applications will need different views of the same data. Suppose, we have an employee
data stored with (employee_id, employee_name, employee_salary, and employee_address, etc.
data items), one user may need only to use the employee_name and employee_salary data items
whereas another user require only the employee_name and employee_address data items. For
data dependent applications, such needs will entail the change of the main application with
creation of two different copies of the same application, as it would be applied by both users.
The Database Administrator (DBA) must have the freedom to change the storage structure or
access technique in response to changing requirements, without having to modify existing
applications. For example, new kinds of data might be added to the database, new standards
might be adopted; new types of storage devices might become available, and so on.
Logical Data Independence:
 Refers to immunity of external schemas to changes in conceptual schema.
 Conceptual schema changes e.g. addition or removal of entities should not require
changes to external schema or rewrites of application programs.
 The capacity to change the conceptual schema without having to change the external
schemas and their application programs.
Physical Data Independence
 The ability to modify the physical schema without changing the logical schema.
 Applications depend on the logical schema.
 In general, the interfaces between the various levels and components should be well
defined so that changes in some parts do not seriously influence others.
 The capacity to change the internal schema without having to change the conceptual
schema
 Refers to immunity of conceptual schema to changes in the internal schema

21
  Internal schema changes e.g. using different file organizations, storage structures/devices
should not require change to conceptual or external schemas.

Review exercises one

Chapter 1

1. Differentiate between data and information.

2. What are the three basic data management approaches with their drawbacks?
3. Discuss in detail about Database system components.
4. Briefly, explain about Database Development life cycle.
5. Design the database system using three basic database levels.

22
 Chapter- TWO
2. Database Model
A database model is a conceptual description of how the database works. It describes how the
data elements are stored in the database and how the data is presented to the user and
programmer for access; and the relationship between different items in the database.
A specific DBS has its own specific Data Definition Language, but this type of language is too
low level to describe the data requirements of an organization in a way that is readily
understandable by a variety of users. We need a higher-level language. Such a higher-level is
called database model.
Database Model is a set of concepts to describe the structure of a database, and certain
constraints that the database should obey.
A database model is a description of the way that data is stored in a database. Database model
helps to understand the relationship between entities and to create the most effective structure to
hold data.
Database Model is a collection of tools or concepts for describing:
 Data
 Data relationships
 Data semantics
 Data constraints
The main purpose of database model is to represent the data in an understandable way.
Categories of database models include:
 Object-based
 Record-based
 Physical
2.1. Record-based Data Models
Consist of a number of fixed format records. Each record type defines a fixed number of fields,
Each field is typically of a fixed [Link] following are examples of this database model
category.
 Hierarchical Database Model
 Network Database Model
 Relational Database Model
1. Hierarchical Model

23
In this model, the data is organized in a tree structure that originates from a root, and each class
of data resides at different levels along a particular branch of the root. The data structure at each
class level is called a node. There is always a single root node which is usually owned by the
system or DBMS. Each of the pointers in the root then will point to (child) nodes there by
depicting a parent-child sort of relationship. Searches are done by traversing the tree up and
down with known search algorithms and modules supplied by the DBMS or may, for special
cases, be designed by the application programmer. The initial structure of the database must be
defined by the application programmer when the database is created. From this point on, the
parent-children structure can’t be changed without redesigning the whole structure.
Generally, Hierarchical database model is:
 The simplest database model
 Record type is referred to as node or segment
 The top node is the root node
 Nodes are arranged in a hierarchical structure as sort of upside-down tree
 A parent node can have more than one child node
 A child node can only have one parent node
 The relationship between parent and child is one-to-many and one-to-one
 Relation is established by creating physical link between stored records (each is stored
with a predefined access path to other records)
 To add new record type or relationship, the database must be redefined and then stored in
a new form.

Department

Employee Job

Time Card Activity

Figure 5 hierarchical data model

Advantages of Hierarchical Database Model:

24
  Hierarchical Model is simple to construct and operate on.
 Corresponds to a number of natural hierarchically organized domains-e.g., assemblies
in manufacturing, personnel organization in companies.
 Language is simple; uses constructs like GET, GET UNIQUE, GET NEXT, GET
NEXT WITHIN PARENT etc.
Disadvantages of Hierarchical Database Model:

 Navigational and procedural nature of processing.

 Database is visualized as a linear arrangement of records.
 Little scope for "query optimization".
2. Network Model

The network is a conceptual description of databases where many-to-many (multiple parent-

children) relationships exist. To make this model easier to understand, the relationships between
the different data items are commonly referred to as sets to distinguish them from the strictly
parent-child relationships defined by the HDBM.

The network model uses pointers to map the relationships between the different data items. The
flexibility of the NDB model is in showing many-to-many relationships is its greatest strength,
though the flexibility comes at a price (the interrelationships between the different data sets
become extremely complex and difficult to map).

Like the HDBM, NDBMs can very quickly be searched, especially through the use of index
pointers that lead directly to the first item in a set being searched. The NDBM suffers from the
same structural problem as the HDBM; the initial design of the database is arbitrary, and once its
setup, any changes to the different sets require the programmer to create an entirely new
structure. The dual problems of duplicated data and inflexible structure led to the development of
a database model that minimizes both problems by making relationships between the different
data items the foundation for how the database is structure.

Generally, Network database model is

 Allows record types to have more than one parent unlike hierarchical
 A network database models sees records as set members
 Each set has an owner and one or more members

25
  Allows/supports many to many relationship between entities
 Like hierarchical model network model is a collection of physically linked records.
 Allow member records to have more than one owner

Department Job

Employee
Activity

Time Card

Figure 6 Network Data Model

Advantages of Network Data Model:

 Network Model is able to model complex relationships and represents semantics of

add or delete on the relationships.
 Can handle most situations for modeling using record types and relationship types.
 Language is navigational; uses constructs like FIND, FIND member, FIND owner,
FIND NEXT within set, GET etc. Programmers can do optimal navigation through
the database.

26
Disadvantages of Network Data Model:

 Navigational and procedural nature of processing.

 Database contains a complex array of pointers that thread through a set of records.
 Little scope for automated "query optimization”.
3. Relational Database Model

The relational database model is a way of looking at data- that is, it is a prescription for a way of
representing data (namely, by means of tables), and a prescription for a way of manipulating
such data (by means of operators). More precisely, the relational database model is concerned
with three aspects of data: data structure (objects), data integrity, and data manipulation
(operators).

The primary purpose behind the relational database model is the preservation of data integrity.
To be considered truly relational, a DBMS must completely prevent access to the data by any
means other than queries handled by the DBMS itself. While the relational model does not
specify how the data is stored on the disk, the preservation of data integrity implies that the data
must be stored in a format that prevents it from being accessed from outside the DBMS that
created it.
The relational model also requires that the data be accessed through programs that don’t rely on
the position of the data in the database. This is in direct contrast to the other database models,
where the program has to follow a series of pointers to the data it wants. A program querying a
relational database simply asks for the data it wants, and it is up to the DBMS to do the necessary
searches and provide the answer. Searches can be speed up by creating an index on one or more
columns in a table; however, the DBMS controls and uses the index. The user has only to ask the
DBMS to create the index, and it will be maintained and used automatically from that point on.
The relational database model has a number of advantages over the other models. The most
important is its complete flexibility in describing the relationships between the various data
items. Once the tables are created and relationships defined then users can query the database on
any of the individual columns in a table or on the relationships between the different tables.

Changing the structure of the database objects is as simple as adding or deleting columns in a
table. Creating new tables, deleting old tables etc. are also very simple. The major tasks that the
designers of a relational database has to make concerns the definitions of the tables and their
relationships in the database.

27
Generally, Relational database model is

 Developed by Dr. Edgar Frank Codd in 1970 (famous paper, 'A Relational Model for
Large Shared Data Banks').
 Terminologies originates from the branch of mathematics called set theory and
relation.
 Can define more flexible and complex relationship.
 Viewed as a collection of tables called “Relations” equivalent to collection of record
types.
 Relation: Two dimensional table.
 Stores information or data in the form of tables  rows and columns.
 A row of the table is called tuple equivalent to record.
 A column of a table is called attribute equivalent to fields.
 Data value is the value of the Attribute.
 Records are related by the data stored jointly in the fields of records in two tables or
files. The related tables contain information that creates the relation.
 The tables seem to be independent but are related somehow.
 No physical consideration of the storage is required by the user.
 Many tables are merged together to come up with a new virtual view of the
relationship.

Figure 7 terminologies in database

Alternative terminologies

Relation Table File

Tuple Row Record

Attribute Column Field

 The rows represent records (collections of information about separate items).

 The columns represent fields (particular attributes of a record).

28
  Conducts searches by using data in specified columns of one table to find additional data
in another table.
 In conducting searches, a relational database model matches information from a field in
one table with information in a corresponding field of another table to produce a third
table that combines requested data from both tables.

Review exercise two

Chapter 2

1. Define database model and list down different aspects that it considers.
2. Explain different classification of database models and their characteristics.
3. Consider University database, then try to represent it, using different database models.

29
 Chapter Three
3. Database Modelling Using the Entity-Relationship
(ER) Database Model
3.1. Properties of Relational Databases - Basic Concepts in Relational
Database
 Each row of a table is uniquely identified by a primary key (can be composed of one
or more columns).
 Each tuple in a relation must be unique.
 Group of columns, that uniquely identifies a row in a table is called a candidate key.
 Entity integrity rule of the model states that no component of the primary key may
contain a NULL value.
 A column or combination of columns that matches the primary key of another table is
called a foreign key. This key is used to cross-reference tables.
 The referential integrity rule of the model states that, for every foreign key value in a
table there must be a corresponding primary key value in another table in the database
or it should be NULL.
 All tables are logical entities.
 A table is either a base tables (named relations) or views (Unnamed Relations).
 Only base tables are physically stores.
 Views are derived from base tables with SQL instructions like:
[select .. from .. where .. order by].
 Relational database is the collection of tables.
 Each entity in one table.
 Attributes are fields (columns) in table.
 Order of rows and columns is immaterial or irrelevant.
 Entries with repeating groups are said to be un-normalized.
 Entries are single-valued.
 Each column (field or attribute) has a distinct name.
All values in a column represent the same attribute and have the same data format.

3.2. Building Blocks of the Relational Database Model

The building blocks of the relational database model are:

30
  Entities: Real world physical or logical object.
 Attributes: Properties used to describe each Entity or real world object.
 Relationship: The association between the real world objects (i.e Entities.)
 Constraints: Rules that should be obeyed or followed while manipulating the data.
1. ENTITIES: The entities (persons, places, things etc.) which the organization has to deal
with. Relations can also describe relationships. The name given to an entity should always be
a singular noun descriptive of each item to be stored in it. E.g.: student, NOT students. Every
relation has a schema, which describes the columns, or fields, the relation itself corresponds
to our familiar notion of a table: A relation is a collection of tuples, each of which contains
values for a fixed number of attributes.
Existence Dependency: The dependence of an entity on the existence of one or more
entities.
Weak entity : An entity that can not exist without the entity with which it has a
relationship – it is indicated by a double rectangle.
2. ATTRIBUTES - The items of information which characterize and describe these entities.
Attributes are pieces of information about entities. The analysis must of course identify those
which are actually relevant to the proposed application. Attributes will give rise to recorded
items of data in the database. At this level we need to know such things as:
 Attribute name: Should be explanatory words or phrases.
 The domain: from which attribute values are taken (A domain is a set of values
from which attribute values may be taken.) Each attribute has values taken from
a domain. For example, the domain of Name is string and that for salary is real.
 Whether the attribute is part of the entity identifier (attributes which just describe
an entity and those which help to identify it uniquely).
 Whether it is permanent or time-varying (which attributes may change their
values over time).
 Whether it is required or optional for the entity (whose values will sometimes be
unknown or irrelevant).

3.2.1. Types of Attributes

(1) Simple (atomic) Vs Composite attributes
 Simple : Contains a single value (not divided into sub parts)
E.g. Age, gender,etc.

31
  Composite: Divided into sub parts (composed of other attributes).
E.g. Name, address,etc.
(2) Single-valued Vs multi-valued attributes
 Single-valued : Have only single value (the value may change but has only one
value at one time).
E.g. Name, Sex, Id. No. color_of_eyes, etc.
 Multi-Valued: Have more than one value.
E.g. Address, dependent-name, Person may have several college
degrees, etc.
(3) Stored vs. Derived Attributes
 Stored : not possible to derive or compute.
E.g. Name, Address, etc.
 Derived: The value may be derived (computed) from the values of other
attributes.
E.g. Age (current year – year of birth).
Length of employment (current date- start date).
Profit (earning-cost).
G.P.A (grade point/credit hours).
(4) Null Values
 NULL applies to attributes which are not applicable or which do not have values.
 You may enter the value NA (meaning not applicable).
 Value of a key attribute cannot be null.
Default value - Assumed value if no explicit value.
3.2.2. Entity versus Attributes
When designing the conceptual specification of the database, one should pay attention to the
distinction between an Entity and an Attribute.

@ Consider designing a database of employees for an organization:

@ Should address be an attribute of Employees or an entity (connected to Employees by a

relationship)?
 If we have several addresses per employee, address must be an entity (attributes
cannot be set-valued/multi valued).

32
  If the structure (city, Woreda, Kebele, etc) is important, e.g. want to retrieve
employees in a given city, address must be modeled as an entity (attribute values
are atomic).

3. RELATIONSHIPS :The relationships between entities which exist and must be taken into
account when processing information. In any business processing one object may be
associated with another object due to some event. Such kind of association is what we call a
relationship between entity objects.
 One external event or process may affect several related entities.
 Related entities require setting of links from one part of the database to another.
 A relationship should be named by a word or phrase which explains its function.
 Role names are different from the names of entities forming the relationship: one
entity may take on many roles, the same role may be played by different entities.
 For each relationship, one can talk about the number of entities and the number of
tuples participating in the association. These two concepts are called degree and
cardinality of a relationship respectively.
3.2.3. Degree of a Relationship
Degree of relationship is an important point about a relationship which concerns how many
entities are participate in it. The number of entities participating in a relationship is called the
degree of the relationship. Among the Degrees of relationship, the following are the basic:
 Unary/recursive relationship: Tuples/records of a Single entity are related with each
other.
 Binary relationships: Tuples/records of two entities are associated in a relationship.
 Ternary relationship: Tuples/records of three different entities are associated.
 And a generalized one: n-nary relationship: Tuples from arbitrary number of entity sets
are participating in a relationship.

3.2.4. Cardinality of a Relationship

Another important concept about relationship is the number of instances/tuples that can be
associated with a single instance from one entity in a single relationship. The number of
instances participating or associated with a single instance from an entity in a relationship is
called the cardinality of the relationship. The major cardinalities of a relationship are:
 One-to-one: one tuple is associated with only one other tuple.

33
 o E.g. Building -to- Location  as a single building will be located in a single location
and as a single location will only accommodate a single Building.
 One-to-many: one tuple can be associated with many other tuples, but not the reverse.
o E.g. Department-to-Student  as one department can have multiple students.
 Many-to-one: many tuples are associated with one tuple but not the reverse.
o E.g. Employee–to-Department: as many employees belong to a single department.
 Many-to-many: one tuple is associated with many other tuples and from the other side, with
a different role name one tuple will be associated with many tuples.
o E.g. Student–to-Course as a student can take many courses and a single course can
be attended by many students.
4. Relational Constraints/Integrity Rules
Relational Integrity:
 Domain integrity: No value of the attribute should be beyond the allowable limits.
 Entity integrity: In a base relation, no attribute of a Primary Key can assume a value
of NULL.
 Referential integrity: If a Foreign Key exists in a relation, either the Foreign Key
value must match a Candidate Key value in its home relation or the Foreign Key
value must be NULL.
 Enterprise integrity: Additional rules specified by the users or database
administrators of a database are incorporated.
Keys and constraints If tuples are need to be unique in the database, and then we need to make
each tuple distinct. To do this we need to have relational keys that uniquely identify each
relation.

A super key : A super key also know as super set is then a set of one or more attributes that in
group (collectively) can identify an entity uniquely from the entity set.

Example: Consider the “EMPLOYEES” entity set, then

- “EmpId”, “EmpId, Name”, “NationalId”, “NationalId, BDate”, … are super keys

- “Name”, “BDate” are NOT super keys

Super Key: an attribute or set of attributes that uniquely identifies a tuple within a relation.

Note: If K is a super set (super key) then a set consisting of K is also a super set.
34
The more interesting super set is the minimal super set that is referred to as the candidate key.

The candidate key is the sufficient and the necessary set of attributes to distinguish an entity set.

Example: In the “EMPLOYEES” entity set

- “EmpId”, “NationalId”, “Name, BDate” (assuming that there is no coincidence that employees
with the same name may born on the same day) … are candidate keys.

The designer of the database is the one that makes the choice of the candidate keys for
implementation, but the choice has to be made carefully. Primary key is a term used to refer to
the candidate key that is selected by the designer for implementation.

Candidate Key: an attribute or set of attributes that uniquely identifies individual occurrences of
an entity type or tuple within a relation.

A candidate key has two properties:

1. Uniqueness
2. Irreducibility
Candidate Key: a super key such that no proper subset of that collection is a Super Key within
the relation.

Composite key: A candidate key that consists of two or more attributes.

Primary key: the candidate key that is selected to identify tuples uniquely within the relation.
The entire set of attributes in a relation can be considered as a primary case in a
worst case.

In another way, an entity type may have one or more possible candidate keys, one of which is
selected to be a primary key.
Foreign key: an attribute, or set of attributes, within one relation that matches the candidate key
of some relation. A foreign key is a link between different relations to create the
view or the unnamed relation.

3.3. Relational Views

Relations are perceived as a table from the users’ perspective. Actually, there are two kinds of
relation in relational database. The two categories or types of relations are Base (Named) and

35
View (Unnamed) Relations. The basic difference is on how the relation is created, used and
updated:
1. Base Relation: It is a named relation corresponding to an entity in the conceptual schema,
whose tuples are physically stored in the database.
2. View (Unnamed Relation): A View is the dynamic result of one or more relational
operations operating on the base relations to produce another virtual relation that does not
actually exist as presented. So a view is virtually derived relation that does not
necessarily exist in the database but can be produced upon request by a particular user at
the time of request. The virtual table or relation can be created from single or different
relations by extracting some attributes and records with or without conditions.
Purpose of a view

 Hides unnecessary information from users: since only part of the base relation (Some
collection of attributes, not necessarily all) are to be included in the virtual table.
 Provide powerful flexibility and security: since unnecessary information will be hidden
from the user there will be some sort of data security.
 Provide customized view of the database for users: each users are going to be interfaced
with their own preferred data set and format by making use of the Views.
 A view of one base relation can be updated.
 Update on views derived from various relations is not allowed since it may violate the
integrity of the database.
 Update on view with aggregation and summary is not allowed. Since aggregation and
summary results are computed from a base relation and does not exist actually.
Schemas and Instances

When a database is designed using a relational data model, all the data is represented in a form of
a table. In such definitions and representation, there are two basic components of the database.
The two components are the definition of the relation or the table and the actual data stored in
each table. The data definition is what we call the Schema or the skeleton of the database and the
relations with some information at some point in time is the Instance or the flesh of the database.
Schemas

Schema describes how data is to be structured, defined at setup/design time (also called
"metadata"). Since it is used during the database development phase, there is rare tendency of

36
changing the schema unless there is a need for system maintenance which demands change to the
definition of a relation.
 Database Schema (Intension): specifies name of relation and the collection of the
attributes (specifically the Name of attributes).
 refer to a description of database (or intention)
 specified during database design
 should not be changed unless during maintenance
 Schema Diagrams: convention to display some aspect of a schema visually.
 Schema Construct: refers to each object in the schema (e.g. STUDENT)
E.g.: STUNEDT (FName,LName,Id,Year,Dept,Sex)
Instances
Instance: is the collection of data in the database at a particular point of time (snap-shot).
 Also called State or Snap Shot or Extension of the database.
 Refers to the actual data in the database at a specific point in time.
 State of database is changed any time we add, delete or update an item.
 Valid state: the state that satisfies the structure and constraints specified in the schema
and is enforced by DBMS.
Since instance is actual data of database at some point in time, changes rapidly. To define a new
database, we specify its database schema to the DBMS (database is empty). Database is
initialized when we first load it with data.

3.4. ENTITY - RELATIONSHIP DIAGRAMS

As one important aspect of E-R modeling, database designers represent their data model by E-R
diagrams. These diagrams enable designers and users to express their understanding of what the
planned database is intended to do and how it might work, and to communicate about the
database through a common language. Each organization that uses E-R diagrams must adopt a
specific style for representing the various components.
Graphical Representations in ER Diagramming
 Entity is represented by a rectangle containing the name of the entity.

Strong Entity

Weak Entity
 Connected entities are called relationship participants

37
  Attributes are represented by ovals and are connected to the entity by a line.

Oval
Ovals Ovals Ovals s
Oval
s
Multi-valued Composite Oval
Attribute
s
 A derived attribute is indicated by a dotted line. (……..) Attribute
Attribute
Ovals
 Primary Keys are underlined. Key
 Relationships are represented by Diamond shaped symbols
 Weak Relationship is a relationship between Weak and Strong Entities.
 Strong Relationship is a relationship between two strong Entities.

Strong Relationship Weak Relationship

An entity-relationship model (ERM) is a model that provides a high-level description of a

conceptual data model. Data modeling that provides a graphical notation for representing such
data models in the form of entity-relationship diagrams (ERD).

The whole purpose of ER modeling is to create an accurate reflection of the real world in a
database. The ER model doesn’t actually give us a database description. It gives us an
intermediate step from which it is easy to define a database.

The E-R data model is based on a perception of a real world that consists of a set of basic objects
called entities, and of relationships among these objects. It was developed to facilitate database
design by allowing the specification of an enterprise schema, which represents the overall logical
structure of a database.

The E-R data model is one of several semantic data models; the semantic aspect of the model lies
in the attempt to represent the meaning of the data. The E-R model is extremely useful in

38
mapping the meanings and interactions of real-world enterprises onto a conceptual scheme.
Because of this utility, many database design tools draw on concepts from the E-R model.

A data model in which information stored in the database is viewed as sets of entities and sets of
relationships among entities. There are three basic notions that the ER Model employs: entity
sets, relationships, and attributes.

Review exercise Three

Chapter 3

1. What are the basic building blocks of relational database?

2. List and define each type of attributes.
3. What is the difference between database schema and database instance?

39
 Chapter Four
4. Database Design
Database design is the process of coming up with different kinds of specification for the data to
be stored in the database. The database design part is one of the middle phases we have in
information systems development (DBS) where the system uses a database approach. Design is
the part on which we would be engaged to describe how the data should be perceived at different
levels and finally how it is going to be stored in a computer system.
Information System with Database application (DBS development life cycles)consists of several
tasks which include:
 Planning of Information systems Design
 Requirements Analysis
 Design (Conceptual, Logical and Physical Design)
 Tuning
 Implementation
 Operation and Support
From these different phases, the prime interest of a database system development will be the
design part which is again sub divided into other three sub-phases. These sub-phases are:
1. Conceptual Database Design
2. Logical Design Database, and
3. Physical Database Design
In general, one has to go back and forth between these tasks to refine a database design, and
decisions in one task can influence the choices in another task. In developing a good design, one
should answer such questions as:
 What are the relevant Entities for the Organization
 What are the important features of each Entity
 What are the important Relationships
 What are the important queries from the user
 What are the other requirements of the Organization and the Users

40
4.1. The Three levels of Database Design

Conceptual Design

Logical Design

Physical Design
Figure 8 levels of database design
1. Conceptual Database Design
Conceptual design is the process of constructing a model of the information used in an
enterprise, independent of any physical considerations.

 It is the source of information for the logical design phase.

 Mostly uses an Entity Relationship Model to describe the data at this level.
 After the completion of Conceptual Design one has to go for refinement of the schema,
which is verification of Entities, Attributes, and Relationships.
2. Logical Database Design
Logical design is the process of constructing a model of the information used in an enterprise
based on a specific database model (e.g. Relational, Hierarchical or Network or Object), but
independent of a particular DBMS and other physical considerations.
Normalization process
– Collection of Rules to be maintained.
– Discover new entities in the process.
– Revise attributes based on the rules and the discovered Entities.
3. Physical Database Design
Physical design is the process of producing a description of the implementation of the database
on secondary storage. -- defines specific storage or access methods used by database.

o Describes the storage structures and access methods used to achieve efficient access to
the data.
o Tailored to a specific DBMS system -- Characteristics are function of DBMS and
operating systems.

41
 o Includes estimate of storage space.

NOTE:
In conceptual data model/Design
o Identify what are the entities/entity types
o Identify what are the attributes: - the information about entities and relationship should we store
in the database.
o Identify relationship types
o Identify what are the constraints/business rules that hold?
o Draw entity-relationship diagram:- representing the database in the ER model using pictorial
representation called ER diagram
o Review the conceptual data model with user
In logical data model/Design
o Map the conceptual model to a logical model
o Mapping entities and relationships in ER-Diagram into tables
-Translate ER-diagram with constraints
o Derive relations from the logical data model
o Validate model using normalization
o Validate model against user transactions
o Draw entity-relationship diagram
o Define integrity constraints
o Check for future growth

NB: Startng from this we are going to design database using the relational database model.

4.2. Conceptual Database Design

Conceptual design revolves around discovering and analyzing organizational and user data
requirements. The important activities are to identify

o Entities
o Attributes
o Relationships
o Constraints
And based on these components develop the ER model using

42
  ER diagrams
4.2.1. The Entity Relationship (E-R) Model
An entity-relationship (E-R) data model is a high-level conceptual model that describes data as
entities, attributes, and relationships. The E-R model is represented by E-R diagrams that show,
how data will be represented and organized in the various components of the final database.
However, the model diagrams do not specify the actual data, or even exactly how it is stored.
The users and applications will create the data content and the database management system will
create the database to store the content.
Entity-Relationship modeling is used to represent conceptual view of the database. The main
components of ER Modeling are:
 Entities: They Correspond to entire table, not row and Represented by Rectangle
 Attributes: Represent the property used to describe an entity or a relationship and
Represented by Oval
 Relationships: Represent the association that exist between entities and Represented by
Diamond
 Constraints: Represent the constraint in the data
Before working on the conceptual design of the database, one has to know and answer the
following basic questions.
What are the entities and relationships in the enterprise?
What information about these entities and relationships should we store in the
database?
What are the integrity constraints that hold? Constraints on each data with respect to
update, retrieval and store.
Represent this information pictorially in ER diagrams, then map ER diagram into a
relational schema.
4.2.2. Developing an E-R Diagram
Designing conceptual model for the database is not a one linear process but an iterative activity
where the design is refined again and again. To identify the entities, attributes, relationships,
and constraints on the data, there are different set of methods used during the analysis phase.
These include information gathered by.
 Interviewing end users individually and in a group
 Questionnaire survey
 Direct observation

43
  Examining different documents
The basic E-R model is graphically depicted and presented for review. The process is repeated until
the end users and designers agree that the E-R diagram is a fair representation of the organization’s
activities and functions. Checking for Redundant Relationships in the ER Diagram. Relationships
between entities indicate access from one entity to another - it is therefore possible to access one
entity occurrence from another entity occurrence even if there are other entities and relationships that
separate them - this is often referred to as Navigation' of the ER diagram. The last phase in ER
modeling is validating an ER Model against requirement of the user.
Example 1: Build an E-R Diagram for the following information:
A student record management system will have the following two basic data object categories
with their own features or properties: Students will have an Id, Name, Dept, Age, GPA and
Course will have an Id, Name, Credit Hours. Whenever a student enroll in a course in a specific
Academic Year and Semester, the Student will have a grade for the course.

Name Dept DoB Id Name Credit

Id Gpa
Students Course
s

Age

Enrolled_In Semester
Academic
Year

Grade

Example 2: Build an ER Diagram for the following information:

A Personnel record management system will have the following two basic data object categories
with their own features or properties: Employee will have an Id, Name, DoB, Age, Tel and
Department will have an Id, Name, Location. Whenever an Employee is assigned in one
Department, the duration of his stay in the respective department should be registered.
Structural Constraints on Relationship

44
1. Constraints on Relationship/Multiplicity/ Cardinality Constraints: Multiplicity constraint is the
number or range of possible occurrence of an entity type/relation that may relate to a single
occurrence/tuple of an entity type/relation through a particular relationship. Mostly used to insure
appropriate enterprise constraints.
One-to-one relationship:
 A customer is associated with at most one loan via the relationship borrower.A loan is associated
with at most one customer via borrower.

E.g.: Relationship Manages between STAFF and BRANCH.

The multiplicity of the relationship is:
 One branch can only have one manager.
 One employee could manage either one or no branches.

1..1 Manages 0..1

Employee Branch

One-To-Many Relationships
 In the one-to-many relationship a loan is associated with at most one customer via borrower, a
customer is associated with several (including 0) loans via borrower.

E.g.: Relationship Leads between STAFF and PROJECT

45
 The multiplicity of the relationship is:

 One staff may Lead one or more project(s)

 One project is Lead by one staff

1..1 Leads 0..*

Employee Project

Many-To-Many Relationship

 A customer is associated with several (possibly 0) loans via borrower. A loan is associated with
several (possibly 0) customers via borrower.

E.g.: Relationship Teaches between INSTRUCTOR and COURSE

The multiplicity of the relationship

 One Instructor Teaches one or more Course(s)

 One Course Thought by Zero or more Instructor(s)

0..* Teaches 1..*

Instructor Course

2. Participation of an Entity Set in a Relationship Set=Particpation constraints

Participation constraint of a relationship is involved in identifying and setting the mandatory or
optional feature of an entity occurrence to take a role in a relationship. There are two distinct
participation constraints with this respect, namely: Total Participation and Partial Participation.

46
 1. Total participation: every tuple in the entity or relation participates in at least one
relationship by taking a role. This means, every tuple in a relation will be attached with at
least one other tuple. The entity with total participation in a relationship will be
connected to the relationship using a double line.
2. Partial participation: some tuple in the entity or relation may not participate in the
relationship. This means, there is at least one tuple from that Relation not taking any role
in that specific relationship. The entity with partial participation in a relationship will be
connected to the relationship using a single line.
E.g. 1: Participation of EMPLOYEE in “belongs to” relationship with
DEPARTMENT is total since every employee should belong to a department.
Participation of DEPARTMENT in “belongs to” relationship with EMPLOYEE is
total since every department should have more than one employee.

Employee Belongs To Department

E.g. 2: Participation of employee in “manages” relationship with Department, is

partial participation since not all employees are managers. Participation of department
in “Manages” relationship with employee is total since every department should have
a manager.

Problem in Employee Manages Department

ER
Modeling

The Entity-Relationship Model is a conceptual data model that views the real world as consisting
of entities and relationships. The model visually represents these concepts by the Entity-
Relationship diagram. The basic constructs of the ER model are entities, relationships, and
attributes. Entities are concepts, real or abstract, about which information is collected.
Relationships are associations between the entities. Attributes are properties which describe the
entities.

47
While designing the ER model one could face a problem on the design which is called a
connection traps. Connection traps are problems arising from misinterpreting certain
relationships.

There are two types of connection traps;

1. Fan trap:
Occurs where a model represents a relationship between entity types, but the pathway
between certain entity occurrences is ambiguous.

May exist where two or more one-to-many (1:M) relationships fan out from an entity.
The problem could be avoided by restructuring the model so that there would be no 1:M
relationships fanning out from a singe entity and all the semantics of the relationship is
preserved.

Example:

1..* Works
EMPLOYEE BRANCH 1..1 IsAssigned CAR
1..1
1..*
For
Semantics description of the problem;

Emp1 Bra1 Car1

Emp2 Bra2 Car2

Emp3 Bra3 Car3

Emp4 Bra4 Car4

Emp5 Car5

Emp6 Car6
Problem: Which car (Car1 or Car3 or Car5) is used by Employee 6. Emp6 working in Branch 1
Emp7 Car7
(Bra1). Thus from this ER Model one cannot tell which car is used by which staff since a branch
can have more than one car and also a branch is populated by more than one employee. Thus we
need to restructure the model to avoid the connection trap.

48
To avoid the Fan Trap problem we can go for restructuring of the E-R Model. This will result in
the following E-R Model.

1..1 Has 1..* 1..* Used By 1..*

BRANCH CAR EMPLOYEE

Semantics description of the problem;

Car1
Bra1 Emp1
Car2
Bra2 Emp2
Car3
Bra3 Emp3
Car4
Bra4 Emp4
Car5
Emp5
3. Chasm Trap: Car6
Emp6
Occurs where a model suggests the existence of a relationship between entity types, but
Car7
the path way does not exist between certain entity occurrences. Emp7
It may exist when there are one or more relationships with a minimum multiplicity on
cardinality of zero forming part of the pathway between related entities.
Example:

1..1 Has 1..* 0..1 Manages 0..*

BRANCH EMPLOYEE PROJECT

If we have a set of projects that are not active currently then we cannot assign a project manager
for these projects. So there are project with no project manager making the participation to have
a minimum value of zero.
Problem:
How can we identify which BRANCH is responsible for which PROJECT? We know that
whether the PROJECT is active or not there is a responsible BRANCH. But which branch is a
question to be answered, and since we have a minimum participation of zero between employee
and PROJECT we can’t identify the BRANCH responsible for each PROJECT.

49
The solution for this Chasm Trap problem is to add another relationship between the extreme
entities (Branch and Project).

1..1 Has 1..* 0..1 Manages 0..*

BRANCH EMPLOYEE PROJECT

1..1 Responsible for 1..*

Enhanced E-R (E-ER) Model

Object-oriented extensions to E-R model. EER is important when we have a relationship
between two entities and the participation is partial between entity occurrences. In such cases
EER is used to reduce the complexity in participation and relationship complexity. ER diagrams
consider entity types to be primitive objects. EER diagrams allow refinements within the
structures of entity types.
EER Concepts: In this part we will discuss the following basic EER concepts.
Generalization Attribute Inheritance
Specialization Constraints on specialization and
Sub classes generalization
Super classes
Generalization
Generalization occurs when two or more entities represent categories of the same real-world
object. Generalization is the process of defining a more general entity type from a set of more
specialized entity types. A generalization hierarchy is a form of abstraction that specifies that
two or more entities that share common attributes can be generalized into a higher level
entity type. Generalization is considered as bottom-up definition of entities. Generalization
hierarchy depicts relationship between higher level super class and lower level subclass.
Generalization hierarchies can be nested. That is, a subtype of one hierarchy can be a
supertype of another. The level of nesting is limited only by the constraint of simplicity.

Example: Account is a generalized form for Saving and Current Accounts.

50
Specialization
Specialization is the result of subset of a higher level entity set to form a lower level entity set.
The specialized entities will have additional set of attributes (distinguishing characteristics) that
distinguish them from the generalized entity. Is considered as Top-Down definition of entities.
Specialization process is the inverse of the Generalization process. Identify the distinguishing
features of some entity occurrences, and specialize them into different subclasses.
Reasons for Specialization are:
 Attributes only partially applying to superclasses.
 Relationship types only partially applicable to the superclass.
In many cases, an entity type has numerous sub-groupings of its entities that are meaningful and
need to be represented explicitly. This need requires the representation of each subgroup in the
ER model. The generalized entity is a superclass and the set of specialized entities will be
subclasses for that specific Superclass.
Example: Saving Accounts and Current Accounts are Specialized entities for the generalized
entity Accounts. Manager, Sales, Secretary: are specialized employees.
Subclass/Subtype
An entity type whose tuples have attributes that distinguish its members from tuples of the
generalized or Super class entities. When one generalized Super class has various subgroups with
distinguishing features and these subgroups are represented by specialized form, the groups are
called subclasses. Subclasses can be either mutually exclusive (disjoint) or overlapping
(inclusive). A single subclass may inherit attributes from two distinct super classes. A mutually
exclusive category/subclass is when an entity instance can be in only one of the subclasses. E.g.:
An EMPLOYEE can either be SALARIED or PART-TIMER but not both.

146
An overlapping category/subclass is when an entity instance may be in two or more subclasses.
E.g.: A person who works for a university can be both employee and a student at the same time.
Superclass /Supertype
An entity type whose tuples share common attributes. Attributes that are shared by all entity
occurrences (including the identifier) are associated with the supertype. Superclass /Supertype Is
the generalized entity.
Relationship Between Superclass and Subclass
The relationship between a superclass and any of its subclasses is called a superclass/subclass or
class/subclass relationship. An instance can not only be a member of a subclass. i.e. Every
instance of a subclass is also an instance in the Superclass. A member of a subclass is
represented as a distinct database object, a distinct record that is related via the key attribute to its
super-class entity. An entity cannot exist in the database merely by being a member of a
subclass; it must also be a member of the super-class. An entity occurrence of a sub class not
necessarily should belong to any of the subclasses unless there is full participation in the
specialization. A member of a subclass is represented as a distinct database object, a distinct
record that is related via the key attribute to its super-class entity. The relationship between a
subclass and a Superclass is an “IS A” or “IS PART OF” type.
 Subclass IS PART OF Superclass
 Manager IS AN Employee

All subclasses or specialized entity sets should be connected with the superclass using a line to a
circle where there is a subset symbol indicating the direction of subclass/superclass relationship.

We can also have subclasses of a subclass forming a hierarchy of specialization. Superclass

attributes are shared by all subclasses f that superclass. Subclass attributes are unique for the
subclass.
Attribute Inheritance

146
An entity that is a member of a subclass inherits all the attributes of the entity as a member of the
superclass. The entity also inherits all the relationships in which the superclass participates. An
entity may have more than one subclass categories. All entities/subclasses of a generalized entity
or superclass share a common unique identifier attribute (primary key). i.e. The primary key of
the superclass and subclasses are always identical.

Consider the EMPLOYEE supertype entity shown above. This entity can have several different
subtype entities (for example: HOURLY and SALARIED), each with distinct properties not
shared by other subtypes. But whether the employee is Hourly or Salaried, same attributes
(EmployeeId, Name, and DateHired) are shared. The Supertype EMPLOYEE stores all
properties that subclasses have in common. And HOURLY employees have the unique attribute
Wage (hourly wage rate), while SALARIED employees have two unique attributes, StockOption
and Salary.
Constraints on specialization and generalization
Completeness Constraint.
The Completeness Constraint addresses the issue of whether or not an occurrence of a Superclass
must also have a corresponding Subclass occurrence. The completeness constraint requires that
all instances of the subtype be represented in the supertype. The Total Specialization Rule
specifies that an entity occurrence should at least be a member of one of the subclasses. Total
Participation of superclass instances on subclasses is diagrammed with a double line from the
Supertype to the circle as shown below. E.g.: If we have Extention and regular as subclasses of a
superclass student, then it is mandatory that each student to be either Extention or regular
student. Thus the participation of instances of student in Extention and regular subclasses will be
total.

146
The Partial Specialization Rule specifies that it is not necessary for all entity occurrences in the
superclass to be a member of one of the subclasses. Here we have an optional participation on
the specialization. Partial Participation of superclass instances on subclasses is diagrammed with
a single line from the Supertype to the circle. E.g.: If we have Manager and Secretary as
subclasses of a superclass Employee, then it is not the case that all employees are either
manager or secretary. Thus the participation of instances of employee in manager and secretary
subclasses will be partial.
Disjointness Constraints
Specifies the rule whether one entity occurrence can be a member of more than one subclasses.
i.e. it is a type of business rule that deals with the situation where an entity occurrence of a
Superclass may also have more than one Subclass occurrence. The Disjoint Rule restricts one
entity occurrence of a superclass to be a member of only one of the subclasses. Example: a
Employee can either be salaried or part-timer, but not the both at the same time. The Overlap
Rule allows one entity occurrence to be a member f more than one subclass. Example:
Employee working at the university can be both a Student and an employee at the same time.
This is diagrammed by placing either the letter "d" for disjoint or "o" for overlapping inside the
circle on the Generalization Hierarchy portion of the E-R diagram.
The two types of constraints on generalization and specialization (Disjointness and
Completeness constraints) are not dependent on one another. That is, being disjoint will not
favour whether the tuples in the superclass should have Total or Partial participation for that
specific specialization.
From the two types of constraints we can have four possible constraints
@ Disjoint AND Total
@ Disjoint AND Partial
@ Overlapping AND Total
@ Overlapping AND Partial

146
 Review Exercise Four
Chapter 4

1. Design Human resource management system using ER database model and indicate
all possible participation among entities.
2. Do you think ER model has drawback? If so, please specify it.
3. Differentiate among specialization, generalization, super class and subclass.

146
 Chapter Five
Relational Database design
Databases and database systems have become an essential component of everyday life in
modern society. In the course of a day, most of us encounter several activities that involve some
interaction with a database. For example, if we go to the bank to deposit or withdraw funds, if we
make a hotel or airline reservation, if we access a computerized library catalog to search for a
bibliographic item, or if we buy some item-such as a book, toy, or computer-from an Internet
vendor through its Web page, chances are that our activities will involve someone or some
computer program accessing a database. Even purchasing items from a supermarket nowadays in
many cases involves an automatic update of the database that keeps the inventory of supermarket
items.
These interactions are examples of what we may call traditional database applications, in which
most of the information that is stored and accessed is either textual or numeric. In the past few
years, advances in technology have been leading for exciting new applications of database
systems. Multimedia databases can now store pictures, video clips, and sound messages.
Geographic information systems (GIS) can store and analyze maps, weather data, and satellite
images. Data warehouses and online analytical processing (OLAP) systems are used in many
companies to extract and analyze useful information from very large databases for decision
making. Real-time and active database technology is used in controlling industrial and
manufacturing processes. And database search techniques are being applied to the World Wide
Web to improve the search for information that is needed by users browsing the Internet.
The relational model represents the database as a collection of relations. Informally, each relation
resembles a table of values or, twosome extent, a "flat" file of records. However, there are
important differences between relations and files. When a relation is thought of as a table of
values, each row in the table represents a collection of related data values. In the relational
model, each row in the table represents a fact that typically corresponds to a real-world entity or
relationship. The table name and column names are used to help in interpreting the meaning of
the values in each row. All values in a column are of the same data type. In the formal relational
model terminology, a row is called a tuple, a column header is called an attribute, and the table is
called a relation. The data type describing the types of values that can appear in each column is
represented by a domain of possible values.

146
5.1. Domains, Attributes, Tuples, and Relations
A domain D is a set of atomic values. By atomic we mean that each value in the domain is indivisible
as far as the relational model is concerned. A common method of specifying a domain is to specify a
data type from which the data values forming the domain are drawn. It is also useful to specify a
name for the domain, to help in interpreting its values. Some examples of domains:
 USA_phone_numbers: The set of ten-digit phone numbers valid in the United States.
 Social_securiry_numbers: The set of valid nine-digit social security numbers.
 Names: The set of character strings that represent names of persons.
The preceding is called logical definitions of domains. A data type or format is also specified for
each domain. For example, the data type for the domain USA_phone_numbers can be declared as a
character string of the form (ddd)ddd-dddd, where each d is a numeric (decimal) digit and the first
three digits form a valid telephone area code.
A domain is thus given a name, data type, and format. Additional information for interpreting the
values of a domain can also be given; for example, a numeric domain such as Person weights should
have the units of measurement, such as pounds or kilograms. A relation schema R, denoted by R(A 1,
A2, ... , An) is made up of a relation name R and a list of attributes A1,A2, ..., An. Each attribute Ai is
the name of a role played by some domain D in the relation schema R. D is called the domain of A i
and is denoted by do m(A). A relation schema is used to describe a relation; R is called the name of
this relation. The degree (or arity) of a relation is the number of attributes n of its relation schema.
An example of a relation schema for a relation of degree seven, which describes university students,
is the following:
STUDENT(Name, SSN, HomePhone, Address, OfficePhone, Age, GPA)
Using the data type of each attribute, the definition is sometimes written as:
STUDENT(Name: string, SSN: string, HomePhone: string, Address: string, OfficePhone:
string, Age: integer, GPA: real)
Conceptual data models use concepts such as entities, attributes, and relationships. An entity
represents a real-world object or concept, such as an employee or a project that is described in
the database. An attribute represents some property of interest that further describes an entity,
such as the employee's name or salary. A relationship among two or more entities represents an
association among two or more entities, for example, a works-on relationship between an
employee and a project.
Cardinality ratio: specifies the maximum number of relationship instances that an entity can
participate in.

146
e.g. Works-For relationship between Department and Employee has 1:N cardinality ratio
Works-On relationship between Employee and Project has M:N cardinality ratio
Manages relationship between Employee and Department has 1:1 cardinality ratio
Example, from University database

Students Name studentNumber class major

Aster 12 A CS
Maru 13 B CS

Course CourseName CourseNumber crieditHour Department

Introduction to computer science Cosc123 3 CS
Data structure Cosc344 4 CS
District Mathematics Math101 4 math
Database Cosc354 3 CS
A relation (or relation state) r of the relation schema R(A1 , A2, ... , An) also denoted by r(R), is
a set of n-tuples r = {t1 , t2, ... , tn}. Each n-tuple t is an ordered list of nvalues t = <v1, V2, ...
,vn>, where each value Vi,1 <= i <=n, is an element of dom(A) or isa special null value.

5.2. Functional Dependency

A functional dependency is a constraint between two sets of attributes from the database.
Suppose that our relational database schema has n attributes A1, A2,… ,An; let us think of the
whole database as being described by a single universal relation schema R ={A1, A2, ... ,An}·
we use this concept only in developing the formal theory of data dependencies. A functional

146
specifies a constraint on the possible tuples that can form a relation state r of R. The constraint is
that, for any two tuples t1 and t2 in r that have t1[X] = t2[X], they must also have t1[Y] = t2[y] .
This means that the values of the Y component of a tuple in r depend on, or are determined by,
the values of the X component; alternatively, the values of the X component of a tuple uniquely
(or functionally) determine the values of the Y component. We also say that there is a functional
dependency from X to Y, or that Y is functionally dependent on X. The abbreviation for
functional dependency is FD or f.d. The set of attributes X is called the left-hand side of the FD,
and Y is called the right-hand side. Thus, X functionally determines Y in a relation schema R if,
and only if, whenever two tuples of r(R) agree on their X-value, they must necessarily agree on
their Y-value.
Note the following:
A functional dependency is a property of the semantics or meaning of the attributes. The
database designers will use their understanding of the semantics of the attributes of R-that is,
how they relate to one another-to specify the functional dependencies that should hold on all
relation states (extensions) r of R. the main use of functional dependencies is to describe further
a relation schema R by specifying constraints on its attributes that must hold at all times.
Consider the relation schema EMP_PROj from the semantics of the attributes, we know that the
following functional dependencies should hold:
a. SSN → ENAME
b. PNUMBER → {PNAME, PLOCATION}
C. {SSN, PNUMBER}→HOURS

These functional dependencies specify that (a) the value of an employee's social security number
(SSN) uniquely determines the employee name (ENAME),
(b) the value of project’s number (PNUMBER) uniquely determines the project name (PNAME)
and location(PLOCATION), and
(c) a combination of SSN and PNUMBER values uniquely determines the number of hours the
employee currently works on the project per week (HOURS).Alternatively, we say that ENAME
is functionally determined by (orfunctionally dependenton) SSN, or "given a value of SSN, we
know the value of ENAME," and so on. A functional dependency is a property of the relation
schema R, not of a particular legal relation state r of R. Hence, an FD cannot be inferred
automatically from a given relation extension r but must be defined explicitly by someone who

146
knows the semantics of the attributes of R. We denote by F the set of functional dependencies
that are specified on relation schema R.
The set of all functional dependencies that include F as well as all dependencies that can be
inferred from F is called the closure of F: it is denoted by F+

Additionally we can infer from F are

 SSN->{Dname,DmgrSSN}
 SSN->SSN
 Dnumber->Dname
Most important type of constraint used to improve designs systematically is a unique-value
constraint called functional dependency.

Title Year Length Film type Studio name Star name

Start wars 1997 124 color fox Carrie fisher
Start wars 1997 124 color fox Mark Hamill
Start wars 1997 124 color fox Harrison
Ford
For example, consider the above relation and we can drive the following functional dependency
Title, year length, filmtype, studioname
This FD says that if two tuples have the same value in their title and year components then these two
tuples must have the same values in their length, filmtype, and studioname components.
Title, year, starname doesn’t hold, and it is not a functional dependency i.e. given a movie it is
entirely possible that there is more than one star for the movie listed in our database.
Keys of Relations
We say a set of one or more attributes {A1,A2,…,An} is a key for a relation R if:
1. Those attributes functionally determine all other attributes of the relation (i.e. because
relations are sets, it is impossible for two distinct tuples of R to agree on all of A1,A2,…An )

2. No proper subsets of {A1,A2,…,An} functionally determines all other attributes of R, i.e. a

key must be minimal.
FD is an assertion about the schema of a relation, not about a particular instance

146
e.g. title and Film_type doesn‟t hold in the above relation (even if for every tuple in this
particular instance of the relation movies it happens that any two tuples agreeing on title also
agree on film_type)
5.2.1. Functional Dependency analysis
Functional dependencies can be used to determine keys of a relation. If a particular attribute or
set of attributes determines all other attributes of a relation, we say that attribute or set of
attributes is a Key.
Closure of Attributes
Given a relation, functional dependencies and set o
B. denoted by A+ or {A1,A2,…,An}+
 It is finding entire set of attributes determined by attributes A1,…An.
 To find the closure of a set of attributes {A1,A2,…An}+
 start with the attribute set {A1,….An, C,D,… }
 then insert the attribute if there exists any functional dependency
e.g. if A->CD insert C and D to the closure set
 Repeat until no change
Closure example
Given the relation with the following schema
Student(SSN,Sname,Address,Hscode,Hsname,Hscity,GPA,Priority)and if the following
functional dependencies hold
SSn->Sname,Address,GPA
GPA->priority
Hscode->Hsname,Hscity
{SSN,Hscode}+ = {SSN,Hscode,Sname,address,GPA,Priority,Hsname,Hscity}
If we find {SSN}+ only it doesn’t determine all the attributes and hence it can’t be a key. But
together SSN and Hs code can be a key because they determine all the attributes. Compute A+
and if it equals all attributes then A is Key.
The appearance an attribute in the left, middle or right hand side of a functional dependency
determines that weather that attribute can be a key or not. i.e.
- An attribute that appears in the left hand side (LHS) of a functional dependency can be a key or
part of a key

146
- An attribute that appears in the right hand side (RHS) of a functional dependency cannot be a
key or part of a key
- An attribute that appears in the middle of a functional dependency may or may not be a key or
part of a key
Examples
1. IF a relation R(A,B,C) and functional dependency F= {A->B,B->C} is given then we can have
left, middle, and right hand side attributes as follows
L M R
A B C
We can find A+ ={A,B,C} therefore, A is a Key for this relation
2. If a relation R(A,B,C,D) and functional dependency F= {AB->C,C->B,C->D} is given then to
determine the key of this relation we can put the attributes to the left, middle, and right form and
find the closure of each. If the closure of a particular attribute contains all attributes, then that
attribute or a set of attribute will be a key.
L M R
A B,C D
Find closures
A+={A} AB+ = {ABCD} AC+ = {ACBD} therefore, from this the Key for the given relation is
{ABC}
3. If a relation R(A,B,C) and functional dependency F= {A->B,B->C,C->A} is given then to
determine the key of this relation we can put the attributes to the left, middle, and right form and
find the closure of each. If the closure of a particular attribute contains all attributes, then that
attribute or a set of attribute will be a key.
L M R
A,B,C
Find closures
A+={A,B,C} B+ = {B,C,A} C+ = {CAB} therefore, from this the Key for the given relation is
{ABC}
[Link] covers
It is used to eliminate redundant functional dependencies from left hand side, and it is a way of
revising FDs so that they are more efficient. It should be done in very complicated databases. Its
aim is to find a minimal set of dependencies as being a set of dependencies in a standard or
canonical form with no redundancies.
Steps to find minimal covers

146
1. First you should have singleton Right hand side
2. No extraneous (undesired) Left hand side attributes
3. No redundant functional dependencies
Example: if a relation R(ABCDE) and a functional dependency F={AD,BCAD ,CB,
EA, ED } is given then find the minimal covers of the given FD.
- Singleton RHS
F={AD,BCA ,BCD,CB, EA, ED }
- Find and remove any extraneous attributes from LHS
First let’s try BCA, to eliminate either B or C from LHS we should find the B+ and the C+, if
for example B+ contains C then we can eliminate C from LHS otherwise we can‟t and the same
is true for eliminating B from LHS.
Now find B+={B} so we can’t eliminate the C from LHS, and then find C+={CBAD}
- Since C closure (C+) contains B we can eliminate the B
Therefore, the FD, BCA, will become CA, then make this change immediately in the set of
functional dependencies
Next, consider the FD, BCD then find B+={B} so we can’t eliminate C and C+={CABD}
- Since C closure (C+) contains B we can eliminate the B. therefore, the FD, BCD will become
CD
- The given set of FD after the extraneous attributes removed becomes
F={AD,CA ,CD,CB, EA, ED }
- Now find whether there is any redundant FDs or not, to do this check each and every functional
dependency.
- Check first AD, to determine this FD is redundant or not find A+ and if A+ contains D then
we can get rid of D i.e. we don’t need AD
Find A+={A} – no way to remove D, so keep this FD
- Check CA, find C+={CDB} – doesn’t include A, so keep this FD
- Check CD, find C+={CADB} – since C+ contains D, we can eliminate CD FD
- Check CB, find C+={CAD} – doesn’t include B, so keep this FD
- Check EA, find E+={ED} – doesn’t include A, so keep this FD
- Check ED, find E+={EAD} – since E+ contains D, we can eliminate ED FD
Therefore, the minimal cover for F={AD,BCAD ,CB, EA, ED } becomes
F={AD,CA ,CB, EA}

5.3. Normalization and Normal Forms

Many problems arise from redundancy can be addressed by replacing a relation with a collection of
smaller relations. Normalization process takes a relation schema through a series of tests to certify
whether it satisfies a certain normal form.

146
Normalization is a process of analyzing a given relation schema based on their FDs and primary keys
to achieve the desirable properties of minimizing redundancy and minimizing the insertion, deletion
and update anomalies.
Normal form of a relation refers to the highest normal form condition that it meets.

5.3.1 First Normal Form (1NF)

It is now considered to be part of the formal definition of a relation in the basic relational model. It
states that the domain of an attribute must include only atomic (simple, indivisible) values and the
value of any attribute in a tuple must be a single value from the domain of that attribute.
- It was defined to disallow multi valued and composite attributes
Example consider a relational schema Department(Dno,Dname,Dmgrssn,Dlocation)the attribute
Dlocation may has more than one value, there for this relation is not in 1NF

Therefore, it should be normalized to 1NF, there are different techniques to do this

1. Expand the key so that there will be a separate tuple in the original department location for
each location of a department with the primary key {Dno, Dlocation} together, but this
introduces redundancy.

Now this is in 1NF with redundancy

146
2. Remove the attribute Dlocation that violates 1NF and place it in a separate relation
Dept_location along with the Primary Key, the primary key for this new relation will be the
combination {Dno,Dlocation}

Now this is in 1NF and this method is the best method to normalize a relation to 1NF
3. If a maximum number of values is known for the attribute – for example if our department
locations are only three i.e. Dlocation1, Dlocation2, Dlocation3, replace Dlocation attribute with
these three atomic attributes.

This is now also in 1NF but it introduces null values

5.3.2. Second Normal Form (2NF)

It is based on full functional dependency. A full functional dependency XY is a full FD if removal
of any attribute A from X means that the dependency doesn‟t hold any more. For example consider
the following FD {SSN,Pnumber}Hours –is a full dependency (neither SSNHours nor
Pnumber Hours holds) A functional dependency XY is a partial dependency if some attribute

Aϵ X can be removed from X and the dependency still holds. For example
{SSN,Pnumber}Ename -is a partial dependency because SSNEname
holds. A relational schema R is in second normal form if every nonprime attribute A in R is fully
functional dependent on the primary key of R. for example the schema Emp-Proj shown below is not
in second normal form.

Emp-Proj

146
This is not in second normal form and can be normalized in to a number of 2NF relations in
which nonprime attributes are associated only with the part of the primary key on which they are
fully functionally dependent.

5.3.3. Third Normal Form (3NF)

schema R is a transitive dependency if there is a set of attributes Z that is neither a candidate key
nor a subset of any key of R, and both XZ and ZY hold. A relation schema R is in 3NF if it
satisfies 2NF and no nonprime attribute of R is transitively dependent on the primary key.

This is in 2NF since no partial dependency on a key exists, but it is not in 3NF because of the
transitive dependency of DmgrSSN and Dname on SSN via Dnumber. SSNDmgrSSN is transitive
because both SSNDnumber and DnumberDmgrSSN hold and Dnumber is neither a key nor a
subset of the key.

146
Generally, we want to design our relation schemas so that they have neither partial nor transitive
dependencies, because these cause the update anomalies problem.
5.3.4. Boyce – coded Normal Form
- Every relation in BCNF is also in 3NF

- Boyce – coded normal form states that a relation schema R is in BCNF if whenever a functional
dependency XA holds in R, then X is a supper key of R.

Review Exercise Five

Chapter 5

1. What is functional dependence and explain with example?

2. What does it mean normalization? List 3 basic normalization processes.
3. When we say third normalization is violated, support your answer with appropriate
example?

146
 PART TWO
ADVANCED DATABASE SYSTEM

146
 Chapter six
Advanced SQL and Query optimization
6. Introduction
SQL (Structured Query Language) is both Data definition language (DDL) and Data
manipulation language (DML). It has facilities for defining views on the database, for specifying
security and authorization, for defining integrity constraints, and for specifying integrity
constraints.
Data Definition Language – the main sql command for data definition is CREATE statement,
which can be used to create Schemas, tables, domains as well as other constructs such as views,
assertions, and triggers.
CREATE table Employee(Fnamevarchar (15) not null,
Lnamevarchar(15) Not Null,
SSN Char(9) Not Null,
Bdate Date,
Sex Char,
Dno INT Not Null,
Primary Key (SSN),
Foreign Key (Dno) References Department (Dnumber));
CREATE Domain SSN_TYPE as Char(9), after this you can use SSN_TYPE in place of
Char(9).
Specifying Constraints
We can specify different constraints that will be applied on the attributes to have or not to have a
certain value, the following are some examples of attribute constraints:-
 NOT NULL – this specifies the attribute value should not be null.
 Default – this enables to give default value for that attribute if an explicit value is not
provided.
 Check – used for restricting domain values
e.g. Dnumber INT NOT NULL CHECK (Dnumber>0 and Dnumber<21); this restricts Dnumber
to integer numbers between 1 and 20.
Check constraint can be used with the create statement to put restrictions on that particular
domain, for example
CREATE Domain D_NUM as integer CHECK (D_NUM>0 and D_NUM<21), this means
whenever you use D_NUM it will be an integer type and always contains numbers between 1
and 20.
- Primary Key – used to identify each record uniquely
Foreign Key – used to create relationship between two or more relations, and while specifying
this constraint you can use important commands that can keep the referential integrity when a
particular relation that is related with other relation is updates or deleted. Thus are ON DELETE
and ON UPDATE

146
ON DELETE SET DEFAULT - if the value is deleted in the primary relation set default value
ON UPDATE CASCADE – if the value in the primary relation is updated or changed repeat the
same change to all related relations with that relation.
The SELECT – FROM- WHERE – SQL Statement
The general format for this statement is:
SELECT <Attribute List>
FROM <table List>
WHERE <Condition>
For example,
SELECT Bdate, Address
From Employee
Where Fname = “John‟ and Lname=‟mulat‟
This requires only Employee relation listed in the From clause and selects the Employee tuples
that satisfy the condition, then projects the results on Bdate and address attributes.
In relational Algebra this can be rewritten as
Π Bdate, Address (σFname=‟John‟ and Lname=‟Smith‟(Employee))
- If a query uses a single relation is similar to a SELECT-PROJECT pair of relational algebra
SELECT Fname, Lname, Address
From Employee, Department
Where Dname = „Research‟ and Dnumber=Dno
- This is similar to a SELECT-PROJECT-JOIN sequence of relational algebra.
The condition Dname=‟research‟ is a selection condition and corresponds to a select
operation in relational algebra.
The condition Dnumber=Dno is a join condition
Write a SELECT query to retrieve all employees in department 5 whose salary is between
$15000 and $20000.
SELECT * From Employee
Where (salary between, 15000 and 20000) and Dno=5;
Or salary >=15000 and salary <=20000
Nested Queries
Some queries require that existing values in the database be fetched and then used in a
comparison condition; this can be done using nested queries.

146
For example, to retrieve the name of each employee who has a dependent with the same first
name and same sex as the employee.
SELECT [Link],[Link]
From Employee AS E
Where [Link] IN( SELECT ESSN
From Department
Where [Link]=Dependent_Name
And [Link] =SEX);

6.1. Data Manipulation Language

Sql Statements used as Data manipulation are the INSERT, UPDATE, DELETE statements and
so on.
To delete an employee record whose last name is brown.
DELETE from employee
Where Lname=‟Brown‟
To change Project location and Dnum whose project number is 10.
UPDATE Project Set Plocation=‟Bellaire‟, Dnum=5 Where Pnumber =10;

6.2. Assertion
An assertion is used to specify general constraints using the create assertion statement. For
example, to specify the constraint that “the salary of an employee must not be greater than the
salary of the manager of the department that the employee works for”
CREATE assertion Salary_constraint
CHECK (NOT Exists
( SELECT *
From Employee E, Employee M, Department D
Where [Link]>[Link] And
[Link]=[Link] And
[Link]=[Link]));

6.3. Views
It is a virtual table that is derived from other tables. A view is obtained from previously defined
tables called base tables whose tuples are physically stored in the database. This may limit the
possible update operations that can be applied on views, but not on querying a view. It is a way

146
of specifying a table that we need to reference frequently. It is specified using CREATE view
statement
CREATE view Works_ON1
As SELECT Fname, Lname, Pname, Hours
From Employee, Project, works-on
Where SSN=ESSN and Pno=Pnumber
We can create a view by specifying new attribute names
CREATE view Dept-Info(DeptName, NumofEmp, Total_Sal)
As SELECT Dname, Count(*),Sum(Salary)
From Department, Employee
Where Dnumber=Dno
Group by Dname
We can specify SQL queries on a view in the same way we specify queries involving base tables.
SELECT Fname,Lname
From Works_ON1
Where Pname=‟ProjectX‟
This can be written to retrieve the last and first names of all employees who work on projectX.
The main advantage of view is to simplify the specification of certain queries. The view becomes
up to date when we modify tuples in the base table. The view can also be dropped, if we don’t
need it any more using the drop statement.
DROP view Works_ON1
Used as a security and authorization mechanism by:
 By restricting a user to a specific rows (to see his/her record) or column (not to see salary
column) in a table
 Aggregate information instead of supplying details (present sum of a particular column)

6.4. Stored Procedures

It is a prepared SQL code that can be Saved and reused over and over again. It is a group of SQL
statements compiled in to a single execution plan. The SQL statements needed to do a commonly
performed task can be designed, coded, and tested once in a stored procedure. Each application
needing to perform that task can then simply execute the stored procedure.
Many tasks can be implemented as series of SQL statements. If these SQL statements are written
into a stored procedure, they become part of a single execution plane. Stored procedures can also

146
shield users from needing to know the details of the tables in the database. SQL server includes a
set of system stored procedures whose names usually start with SP_
Example: to change name of the database you can write
Execute SP_renameDB ‘database name’, ‘new name’
To create user defined stored procedures you can use the create procedure statement
Create procedure <owner>.<procedure name><param><data type> As <Body>
Examples
AS
Select * from [Users]
Where Isnull(@login,login) =login
You can write your stored procedure to select all information from Employee table for example
and use it whenever you want as the following.
CREATE procedure Employee_details
AS
Select * from Employee
To run this just write EXECUTE Employee_details

6.5. SQL queries and Relational Algebra

6.5.1. Relational Algebra
It enables a user to specify basic retrieval requests. A sequence of relational algebra operations
forms a relational algebra expression. It provides a formal foundation for relational model
operations. It is used as a basis for implementing and optimizing queries in relational database
management system. Its operations can be divided into two:
1. Include set operations, UNION, INTERSECTION, SET DIFFERENCE, and CARTESIAN
PRODUCT.
2. Developed for relational database specifically (SELECT, PROJECT, and JOIN)
1. SELECT operation
A SELECT operation can be visualized as a horizontal partitioning of the relation into two sets
of tuples.

Example, σDno=4(Employee) – to select employees whose department is 4

The general form is σ<Selection condition>(R)

σ - sigma is used to denote the select operator, and the selection operation is Boolean expression.

146
Select operation is commutative

σ<cond1>( σ<cond2>(R)) = σ<cond2>( σ<cond1>(R))

2 Project operation
If we are interested only in certain attributes, we use project operation to project the relation over
these attributes only. It can be visualized as a virtual partitioning of the relation.
Example, to list each employee’s first and last name and salary, we can use project operation
πLname, Fname, Salary (Employee)
The general form of the project operation is π<Attribute list> (R)
Where π (Pi) is used to represent the project operation. If the attribute list includes only non key
attributes or R, duplicate tuples are likely to occur. However, project operation removes any
duplicate tuples.
Project operation is not commutative.
- We can apply several relational algebra operations one after the other.
πLname,Fname,Salary (σDno=5 (Employee))
3 JOIN
The JOIN operation denoted by⋈, is used to combine related tuples from two relations into a
single tuples. It allows as processing relationships among relations. For example, to get the
names of the managers of each department (i.e. to get the managers name, we need to combine
each department tuple with the employee tuple whose SSN value matches the mgrSSN value in
the department tuple.)
This is a general form R ⋈<join condition>S - it can be combined with other operations
πDname,Lname,Fname(R<mgrSSN=SSN>S (Employee))
There are different kinds of joins these are:
INNER JOIN
Used to combine data from multiple relations so that related information can be presented in a
single table, only matching records are kept in the result
OUTER JOIN
Can be used if we want to keep all the tuples in R, or all those in S if we have two relations R
and S, or all those in both relations regardless of whether or not they have matching tuples in the
other relation. It can be Left outer join, Right outer join, or full outer join
LEFT OUTER JOIN – to retrieve a list of all employee names and the name of the departments
they manage, if they do not manage it will be indicated by null. It keeps every tuple in the first or

146
left relation. If no matching tuple is found in S, these attributes are filled with Null values in the
result.
RIGHT OUTER JOIN- keeps every tuple in the second or right relation. If no matching tuples
found these attribute values will be filled with Null values.
FULL OUTER JOIN – keeps all tuples in both the left and right relation. If no matching tuples
are found it will put Null values.

6.5.2. Translating SQL queries to Relational Algebra

Since relational algebra is somewhat low, level than SQL queries it will give us a mathematical
foundation for analyzing and optimizing SQL queries. \

1. For example, consider the following subset of the engineering database schema

EMP(ENO, ENAME, TITLE)

ASG(ENO, PNO, RESP, DUR)
“Find the names of employees who are managing a project”
SELECT ENAME
FROM EMP,ASG
WHERE [Link] = [Link]
AND RESP = ‘‘Manager’’
Now to translate this SQL query to relational algebra we can use temporary variables that can
store the intermediate results.

146
 𝝅ENAME(𝛔RESP=”manager”^[Link]=[Link](EMP×ASG)
And

𝝅ENAME(EMP ⋈ ENO(𝛔RESP=”manager”(ASG)))

6.2. Query Processing and Optimization

6.2.1. Query Processing
The aim of query processing is to find information in one or more databases and deliver it to the
user quickly and efficiently. Traditional techniques work well for databases with standard,
single-site relational structures, but databases containing more complex and diverse types of data
demand new query processing and optimization techniques.
Query Processing can be divided into four main phases:
1. Decomposition:
2. Optimization
3. Code generation, and
4. Execution

Query Decomposition
Query decomposition is the process of transforming a high level query into a relational algebra
query, and to check that the query is syntactically and semantically correct. Query decomposition
consists of parsing and validation.
Typical stages in query decomposition are:
[Link]: lexical and syntactical analysis of the query (correctness). Query tree will be built for
the query containing leaf node for base relations, one or many non-leaf nodes for relations
produced by relational algebra operations and root node for the result of the query. Sequence of
operation is from the leaves to the root.
2. Normalization: convert the query into a normalized form. The predicate WHERE will be
converted to Conjunctive () or Disjunctive () Normal form. 
3. Semantic Analysis: to reject normalized queries hat are not correctly formulated or
contradictory. Incorrect if components do not contribute to generate result. Contradictory if the
predicate can not be satisfied by any tuple. Algorithms: relation connection graph and
normalized attribute connection graph.

146
4. Simplification: to detect redundant qualifications, eliminate common sub-expressions, and
transform the query to a semantically equivalent but more easily and effectively computed form.
5. Query Restructuring More than one translation is possible Use transformation rules
Most real-world data is not well structured. Today's databases typically contain much non-
structured data such as text, images, video, and audio, often distributed across computer
networks. In this complex environment, efficient and accurate query processing becomes quite
challenging. There could be tons of tricks (not only in storage and query processing, but also in
concurrency control, recovery, etc.) Different tricks may work better in different usage scenarios.
Same tricks get used over and over again in different applications.
Query processing: Execute transactions in behalf of this query and print the result. Steps in
query processing:

Example: Select Customer name

From Customer, Invoice
Where region = Kansas City and Amount > 1000

146
Figure 9 query processing
Query Optimization
What is wrong with the ordinary query?
Everyone wants the performance of their database to be optimal. In particular, there is often
a requirement for a specific query or object that is query based, to run faster.
Problem of query optimization is to find the sequence of steps that produces the answer to
user request in the most efficient manner, given the database structure.
The performance of a query is affected by the tables or queries that underlies the query and
by the complexity of the query.
When data/workload characteristics change

146
The best navigation strategy changes
The best way of organizing the data changes
Query optimizers are one of the main means by which modern database systems achieve their
performance advantages. Given a request for data manipulation or retrieval, an optimizer will
choose an optimal plan for evaluating the request from among the manifold alternative
strategies. i.e. there are many ways (access paths) for accessing desired file/record. The
optimizer tries to select the most efficient (cheapest) access path for accessing the data. DBMS is
responsible to pick the best execution strategy based on various considerations.
Query optimizers were already among the largest and most complex modules of database
systems.
Most efficient processing: Least amount of I/O and CPU resources.
Selection of the best method: In a non-procedural language, the system does the optimization at
the time of execution. On the other hand, in a procedural language, programmers have some
flexibility in selecting the best method. For optimizing the execution of a query the programmer
must know:
File organization,
Record access mechanism and primary or secondary key,
Data location on disk,
Data access limitations
To write correct code, application programmers need to know how data is organized physically
(e.g., which indexes exist), to write efficient code, application programmers also need to worry
about data/workload characteristics
One has to cope with change!
Example: Consider relations r(AB) and s(CD). We require r X s.
Method 1
a. Load next record of r in RAM.
b. Load all records of s, one at a time and concatenate with r.
c. All records of r concatenated?
NO: goto a.
YES: exit (the result in RAM or on disk).
Performance: Too many accesses.
Method 2: Improvement

146
a. Load as many blocks of r as possible leaving room for one block of s.
b. Run through the s file completely one block at a time.
Performance: Reduces the number of times s blocks are loaded by a factor of equal to the
number of r records than can fit in main memory.
Considerations during query Optimization:
Narrow down intermediate result sets quickly. SELECT before JOIN
Use access structures (indexes).

6.2.2. Approaches to Query Optimization

1. Heuristics Approach
 The heuristic approach uses the knowledge of the characteristics of the relational algebra
operations and the relationship between the operators to optimize the query.
Thus the heuristic approach of optimization will make use of:
 Properties of individual operators
 Association between operators
2. Query Tree: a graphical representation of the operators, relations, attributes and predicates
and processing sequence during query processing.

Query tree is composed of three main parts:

i. The Leafs: the base relations used for processing the query/ extracting the required
information
ii. The Root: the final result/relation as an output based on the operation on the relations used for
query processing
iii. Nodes: intermediate results or relations before reaching the final result.
Sequence of execution of operation in a query tree will start from the leaves and continues to the
intermediate nodes and ends at the root.
The properties of each operations and the association between operators is analyzed using set of
rules called TRANSFORMATION RULES. Use of the transformation rules will transform the
query to relatively good execution strategy.

6.2.3. Transformation Rules for Relational Algebra

1. Cascade of SELECTION: conjunctive SELECTION Operations can cascade into individual
Selection Operations and Vice Versa

(c1∩c2∩c3) (R)= 𝛔c1(𝛔c2(𝛔c3(R))where ci is a predicate where ci is a predicate

146
2. Commutatively of SELECTION operations

𝛔c1(𝛔c2(R))= 𝛔c2(𝛔c1(R)) where ci is a predicate

3. Cascade of PROJECTION: in the sequence of PROJECTION Operations, only the last in the
sequence is required

𝝅L1𝝅L2𝝅L3𝝅L4 (R)=𝝅 (R) L1

4. Commutatively of SELECTION with PROJECTION and Vise Versa

a. If the predicate c1 involves only the attributes in the projection list (L1), then the selection and
projection operations commute.

𝝅L1 𝛔c1( (R))= 𝛔 (𝝅 (R)) c1 L1

5. Commutatively of THETA JOIN/Cartesian Product

R X S is equivalent to S X R
Also holds for Equi-Join and Natural-Join

(R⋈ S)= (S⋈ R)

c1 c1

6. Commutatively of SELECTION with THETA JOIN

a. If the predicate c1 involves only attributes of one of the relations (R) being joined, then the
Selection and Join operations commute.

𝛔 c1 (R⋈ S)=( 𝛔 (R)) ⋈ S)

c c1 c

b. If the predicate is in the form c1,c2 and c1 involves only attributes of R and c2 involves only
attributes of S, then the Selection and Theta Join operations commute.

𝛔 c1^c2 (R⋈ S)=( 𝛔 (R)) ⋈ (𝛔 S))

c c1 c c2

7. Commutatively of PROJECTION and THETA JOIN

If the projection list is of the form L1, L2, where L1 involves only attributes of R and L2
involves only attributes of S being joined and the predicate c involves only attributes in the
projection list, then the SELECTION and JOIN operations commute

𝛑L1,L2 (R⋈c S)=( 𝛑L1,L2 (R)) ⋈c (𝛑L1,L2 S))

146
8. Commutatively of the Set Operations: UNION and INTERSECTION but not SET
DIFFERENCE

R∩S=S∩R R∪S=S∪R and

9. Associatively of the THETA JOIN,CARTESIAN PRODUCT, UNION and INTERSECTION.

(R𝜽 S)𝜽 T=R𝜽 (S𝜽T) where 𝜃 is one of the operations

10. Commuting SELECTION with SET OPERATIONS

𝛔c (R𝜃S)= (𝛔c(R) 𝜽𝛔c(S))where 𝜽is one of the operations

11. Commuting PROJECTION with UNION

𝛑 (S∪R)= 𝛑 (S)∪ 𝛑 (R)

L1 L1 L1

Heuristic Approach will be implemented by using the above transformation rules in the
following sequence or steps.

6.2.4. Sequence for Applying Transformation Rules

1. Use
Rule-1Cascade SELECTION
2. Use
Rule-2: Commutatively of SELECTION
Rule-4: Commuting SELECTION with PROJECTION
Rule-6: Commuting SELECTION with JOIN and CARTESIAN
Rule-10: commuting SELECTION with SETOPERATIONS
3. Use
Rule-9: Associatively of Binary Operations (JOIN,CARTESIAN, UNION and
INTERSECTION). Rearrange nodes by making the most restrictive operations to be performed
first (moving it as far down the tree as possible)
4. Perform Cartesian Operations with the subsequent Selection Operation
5. Use
Rule-3: Cascade of PROJECTION
Rule-4: Commuting PROJECTION with SELECTION
Rule-7: Commuting PROJECTION with JOIN and CARTESIAN

146
Rule-11: commuting PROJECTION with UNION
Main Heuristic
The main heuristic is to first apply operations that reduce the size (the cardinality and/or the
degree) of the intermediate relation. That is:
a. Perform SELECTION as early as possible: that will reduce the cardinality (number of tuples)
of the relation.
b. Perform PROJECTION as early as possible: that will reduce the degree (number of attributes)
of the relation.
Both a and b will be accomplished by placing the SELECT and PROJECT operations as far
down the tree as possible.
c. SELECT and JOIN operations with most restrictive conditions resulting with smallest absolute
size should be executed before other similar operations. This is achieved by reordering the nodes
with JOIN
Example: consider the following schemas and the query, where the EMPLOYEE and the
PROJECT relations are related by the WORKS_ON relation.
EMPLOYEE (EEmpID, FName, LName, Salary, Dept, Sex, DoB)
PROJECT (PProjID, PName, PLocation, PFund, PManagerID)
WORKS_ON (WEmpID, WProjID)
WEmpID (refers to employee identification) and PProjID (refers to project identification) are
foreign keys to WORKS_ON relation from EMPLOYEE and PROJECT relations respectively.
Query: The manager of the company working on road construction would like to view
employees name born before January 1 1965 who are working on the project named Ring Road.
Relational Algebra representation of the query will be:

𝛑<FName,
LName>(𝛔<DoB<Jan11965 WEmpID=EEmpID PProjID=WProjID PName=’Ring
Road’> (EMPLOYEEXWORKS_ONXPROJECT
The SQL equivalence for the above query will be:
SELECTFName, LName
FROM EMPLOYEE, WORKS_ON, PROJECT
WHEREDoB<Jan 1 1965 EEmpID=WEmpID WProjID=PProjID PName=”Ring Road”
The initial query tree will be:

146
By applying the first step (cascading the selection) we will come up with the following structure.

( (
𝛔 (DoB<Jan1 1965) 𝛔 (WEmpID=EEmpID) 𝛔 (PProjID=WProjID) 𝛔 PName=’Ring (
X
Road’) (EMPLOYEE WORKS_ON PROJECT) X ))
By applying the second step it can be seen that some conditions have attribute that belong to a single
relation ( DoB belongs to EMPLOYEE and PName belongs to PROJECT) thus the selection
operation can be commuted with Cartesian Operation. Then, since the condition
WEmpID=EEmpIDbase the employee andWORKS_ON relation the selection with this condition can
be cascaded.

(𝛔 PProjID=WProjID)( 𝛔 PName=’Ring Road’) PROJECT) X (𝛔

(

WEmpID=EEmpID) (WORKS_ONX (𝛔 (DoB<Jan1 1965) EMPLOYEE))))

(

The query tree after this modification will be:

146
Using the third step, perform most restrictive operations first.
From the query given we can see that selection on PROJECT is most restrictive than selection on
EMPLOYEE. Thus, it is better to perform selection on PROJECT BEFOR selection on
EMPLOYEE. Rearrange the nodes to achieve this.

146
146
Using the forth step, Perform Cartesian Operations with the subsequent Selection Operation.

Using the fifth step, Perform the projection as early as possible.

146
Cost Estimation Approach to Query Optimization
The main idea is to minimize he cost of processing a query. The cost function is comprised of:
I/O cost + CPU processing cost + communication cost + Storage cost
These components might have different weights in different processing environments
The DBMs will use information stored in the system catalogue for the purpose of estimating
cost. The main target of query optimization is to minimize the size of the intermediate relation.
The size will have effect in the cost of:
Disk Access

146
Data Transpiration
Storage space in the Primary Memory
Writing on Disk
The statistics in the system catalogue used for cost estimation purpose are:
Cardinality of a relation: the number of tuples contained in a relation currently (r)
Degree of a relation: number of attributes of a relation
Number of tuples on a relation that can be stored in one block of memory
Total number of blocks used by a relation
Number of distinct values of an attribute (d)
Selection Cardinality of an attribute (S): that is average number of records that will satisfy
an equality condition S=r/d
By sing the above information one could calculate the cost of executing a query and selecting the
best strategy, which is with the minimum cost of processing.
Cost Components for Query Optimization
The costs of query execution can be calculated for the following major process we have during
processing.
1. Access Cost of Secondary Storage
Data is going to be accessed from secondary storage, as a query will be needing some part of the
data stored in the database. The disk access cost can again be analyzed in terms of:
Searching
Reading, and
Writing, data blocks used to store some portion of a relation.
The disk access cost will vary depending on the file organization used and the access method
implemented for the file organization. In addition to the file organization, the data allocation
scheme, whether the data is stored contiguously or in scattered manner, will affect the disk
access cost.
2. Storage Cost
While processing a query, as any query would be composed of many database operations, there
could be one or more intermediate results before reaching the final output. These intermediate
results should be stored in primary memory for further processing. The bigger the intermediate

146
relation, the larger the memory requirement, which will have impact on the limited available
space. This will be considered as a cost of storage.
3. Computation Cost
Query is composed of many operations. The operations could be database operations like reading
and writing to a disk, or mathematical and other operations like:
Searching, Sorting, Merging, Computation on field values
4. Communication Cost
In most database systems the database resides in one station and various queries originate from
different terminals. This will have impact on the performance of the system adding cost for query
processing. Thus, the cost of transporting data between the database site and the terminal from
where the query originate should be analyzed.
Pipelining
Pipelining is another method used for query optimization. It is sometime referred to as on-the-fly
processing of queries. As query optimization tries to reduce the size of the intermediate result,
pipelining use a better way of reducing the size by performing different conditions on a single
intermediate result continuously. Thus the technique is said to reduce the number of intermediate
relations in query execution.
Pipelining performs multiple operations on a single relation in a pipeline.
Ex:
Let’s say we have a relation on employee with the following schema
Employee (ID, FName, LName, DoB, Salary, Position, Dept)
If a query would like to extract supervisors with salary greater than 2000, the relational algebra
representation of the query will be

𝛔 (Salary>2000) ∩ (Position=Supervisor)(Employee)
After reading the relation from the memory, the system could perform the operation by
cascading the SELECT operation.
1. Approach One

(
𝛔 (Salary>2000) 𝛔 (Position=Supervisor) (Employee))
Using this approach we will have the following relations

146
Employee
Relation created by the Operation:

R1 = 𝛔 (Position=Supervisor) (Employee)
The resulting Relation with the Operation

R2 = 𝛔 (Salary>2000)(R1)
2. Approach Two
One can select a single tuple from the relation Employee and perform both tests in a pipeline and
create the final relation at once. This is what is called PIPELINING.

Review Exercise six

Chapter 6

1. What are the two type of structure query languages?

2. What is the difference between table and view?
3. List and write their formula for different relational algebra.
4. What is query processing and optimization?
5. What are different Approaches to Query Optimization?
6. Convert the following relational calculus to relational algebra.
SELECT ENAME
FROM EMP,ASG
WHERE [Link] = [Link]
AND RESP = ‘‘depthead’’

146
 Chapter- Seven
Concurrency Control and Transactions Processing
What is a transaction?
A Transaction is a mechanism for applying the desired modifications/operations to a database. It
is evident in real life that the final database instance after a successful manipulation of the
content of the database is the most up-to-date copy of the database. Action, or series of actions,
carried out by a single user or application program, which accesses or changes contents of
database. (i.e. Logical unit of work on the database.) A transaction could be a whole program,
part/module of a program or a single command. Changes made in real time to a database are
called transactions. Examples include ATM transactions, credit card approvals, flight
reservations, hotel check-in, phone calls, supermarket canning, academic registration and billing.
A transaction could be composed of one or more database and non-database operations.
Transforms database from one consistent state to another, although consistency may be violated
during transaction.
A database transaction is a unit of interaction with database management system or similar
system that is treated in a coherent and reliable way independent of other transactions.

7.1. Transaction processing system

A system that manages transactions and controls their access to a DBMS is called a TP monitor.
A transaction processing system (TPS) generally consists of a TP monitor, one or more DBMSs,
and a set of application programs containing transaction.
In database field, a transaction is a group of logical operations that must all succeed or fail as a
group. Systems dedicated to supporting such operations are known as transaction processing
systems.
In comparison with database transaction, application program is series of transactions with non-
database processing in between.
Distinction between business transactions and online transactions:
A business transaction is an interaction in the real world, usually between an enterprise and a
person, where something is exchanged. An online transaction is the execution of a program that

146
performs an administrative or real-time function, often by accessing shared data sources, usually
on behalf of an online user (although some transactions are run offline in batch).
What we are interested about is the online transaction, which is the interaction between the users
of a database system and the shared data stored in the database. This transaction program
contains the steps involved in the business transaction.
Transactions can be started, attempted, then committed or aborted via data manipulation
commands of SQL.
Can have one of two outcomes for any transaction:
Success - transaction commits and database reaches a new consistent state
Committed transaction cannot be aborted or rolled back.
How do you discard a committed transaction?
Failure - transaction aborts, and database must be restored to consistent state before it started.
Such a transaction is rolled back or undone. Aborted transaction that is rolled back can be
restarted later. In many data manipulation languages, there are keywords used to indicate
different states of a transaction.
A single transaction might require several queries, each reading and/or writing information in the
database. When this happens it is usually important to be sure that the database is not left with
only some of the queries carried out. For example, when doing a money transfer, if the money
was debited from one account, it is important that it also be credited to the depositing account.
Also, transactions should not interfere with each other.
A transaction is expected to exhibit some basic features or properties to be considered as a valid
transaction. These features are:
A: Atomicity
C: Consistency
I: Isolation
D: Durability
It is referred as ACID property of transaction. Without the ACID property, the integrity of the
database cannot be guaranteed.
Atomicity
Is all or none property

146
Every transaction should be considered as an atomic process, which cannot be sub divided into
small tasks. Due to this property, just like an atom, which exists or does not exist, a transaction
has only two states. Done or Never Started. 41 Advanced Database Systems Lecture Note –
Wollo University, Department of Computer Science
Done - a transaction must complete successfully and its effect should be visible in the database.
Never Started - If a transaction fails during execution then all its modifications must be undone
to bring back the database to the last consistent state, i.e., remove the effect of failed transaction.
No state between Done and Never Started
Consistency
If the transaction code is correct then a transaction, at the end of its execution, must leave the
database consistent. A transaction should transform a database from one previous consistent state
to another consistent state.
Isolation
A transaction must execute without interference from other concurrent transactions and its
intermediate or partial modifications to data must not be visible to other transactions.
Durability
The effect of a completed transaction must persist in the database, i.e., its updates must be
available to other transaction immediately after the end of its execution, and is should not be
affected due to failures after the completion of the transaction.
In practice, these properties are often relaxed somewhat to provide better performance.

7.1.1. State of a Transaction

A transaction is an atomic operation from the users‘ perspective. But it has a collection of
operations and it can have a number of states during its execution.
A transaction can end in three possible ways.
1. Successful Termination: when a transaction completes the execution of all operations in it and
reaches the COMMIT command.
2. Suicidal Termination: when the transaction detects an error during its processing and decide to
abrupt itself before the end of the transaction and perform a ROLL BACK
3. Murderous Termination: When the DBMS or the system force the execution to abort for any
reason.

146
Figure 10 states of transaction
Most SQL statements seem to be very short and easy to execute. But the reverse is true if you
consider it as a one command transaction. Actually a database system interprets a transaction not
as an application program but as a logical sequence of low- level operations read and write
(referred to as primitives).

7.1.2. Ways of Transaction Execution

In a database system, many transactions are executed. Basically there are two ways of executing
a set of transactions:
(a) Serially: Serial Execution: In a serial execution transactions are executed strictly serially.
Thus, Transaction Ti completes and writes its results to the database then only the next
transaction Tj is scheduled for execution. This means at one time there is only one
transaction that is being executed in the system. The data is not shared between
transactions at one specific time.

146
In Serial transaction execution, one transaction being executed does not interferethe execution of
any other transaction.
Good things about serial execution Correct execution, i.e., if the input is correct then output will
be correct. Fast execution, since all the resources are available to the active.
The worst thing about serial execution is very inefficient resource utilization.
T2
read (X) read (X)
X := X+N X := X+N
write (X) write (X)
read (Y)
Y := Y+N
write (Y)
We execute this transaction serially as follows:
Time T1 T2
read (X) {X = 10}
X := X+N {X =
11}
write (X) {X = 11}
read (Y) {Y = 6}
Y := Y+N {Y = 7}
write (Y) {Y = 7}
read (X) {X = 11}
X := X+N {X = 12}
write (X)
Final values of X, Y at the end of T1 and T2: X = 12 and Y = 7.
Thus we can witness that in serial execution of transaction, if we have two transactions Ti and
Ti+1, then Ti+1 will only be executed after the completion of Ti.
(b) Concurrently: is the reverse of serially executable transactions, in this scheme the
individual operations of transactions, i.e., reads and writes are interleaved in some order.

Time T1 T2
read (X) {X = 10}
read (X) {X = 10}
X := X+N {X = 11}
X := X+N {X = 11}
write (X) {X = 11}
write (X)
read (Y) {Y = 6}
Y := Y+N {Y = 7}

146
 write (Y) {Y = 7}
Final values at the end of T1 and T2 : X = 11, and Y = 7. This improves resource utilization,
unfortunately gives incorrect result.
The correct value of X is 12 but in concurrent execution X =11, which is incorrect. The reason
for this error is incorrect sharing of X by T1 and T2.
In serial execution T2 read the value of X written by T1 (i.e., 11) but in concurrent execution T2
read the same value of X (i.e., 10) as T1 did and the update made by T1 was overwritten by T2‘s
update.
This is the reason the final value of X is one less that what is produced by serial execution.

7.2. Problems Associated with Concurrent Transaction Processing

Although two transactions may be correct in themselves, interleaving of operations may produce
an incorrect result, which needs control over access.
Having a concurrent transaction processing, one can enhance the throughput of the system. As
reading and writing is performed from and on secondary storage, the system will not be idle
during these operations if there is a concurrent processing.
Every transaction should be correct by themselves, but this would not guarantee that the
interleaving of these transactions will produce a correct result.
The three potential problems caused by concurrency are:
 Lost Update Problem
 Uncommitted Dependency Problem
 Inconsistent Analysis Problem
1. Lost Update Problem
Successfully completed update on a data set by one transaction is overridden by another
transaction/user.
E.g. Account with balance A=100.
T1 reads the account A
T1 withdraws 10 from A
 T1 makes the update in the Database
 T2 reads the account A
 T2 adds 100 on A
 T2 makes the update in the Database

146
  In the above case, if done one after the other (serially) then we have no problem.
 If the execution is T1 followed by T2 then A=190
 If the execution is T2 followed by T1 then A=190
 But if they start at the same time in the following sequence:
 T1 reads the account A=100
 T1 withdraws 10 making the balance A=90
 T2 reads the account A=100
 T2 adds 100 making A=200
 T1 makes the update in the Database A=90
 T2 makes the update in the Database A=200

After the successful completion of the operation in this schedule, the final value of A will be
200, which override the update made by the first transaction that changed the value from 100 to
90.
2. Uncommitted Dependency Problem
It occurs when one transaction can see intermediate results of another transaction before it is
committed.
E.g.
T2 increases 100 making it 200 but then aborts the transaction before it is committed. T1 gets
200, subtracts 10 and make it 190. But the actual balance should be 90
3. Inconsistent Analysis Problem
It occurs when transaction reads several values but second transaction updates some of them
during execution and before the completion of the first.
E.g.
T2 would like to add the values of A=10, B=20 and C=30. after the values are read by T2 and
before its completion, T1 updates the value of B to be 50. at the end of the execution of the two
transactions T2 will come up with the sum of 60 while it should be 90 since B is updated to 50.
As discussed above, the objective of Concurrency Control Protocol is to schedule transactions in
such a way as to avoid any interference between them. This demands a new principle in
transaction processing, which is serializability of the schedule of execution of multiple
transactions.

146
7.2.1. Concurrency Control Techniques
Concurrency Control is the process of managing simultaneous operations on the database
without having them interfere with one another. Prevents interference when two or more users
are accessing database simultaneously and at least one is updating data. Although two
transactions may be correct in themselves, interleaving of operations may produce an incorrect
result.
Three basic concurrency control techniques:
1. Locking methods
2. Time stamping
3. Optimistic
Locking and Time stamping are pessimistic approaches since they delay transactions.
Both Locking and Time stamping are conservative approaches: delay transactions in case they
conflict with other transactions.
The optimistic approach allows us to proceed and check conflicts at the end.
Optimistic methods assume conflict is rare and only check for conflicts at commit.
1. Locking Method
A LOCK is a mechanism for enforcing limits on access to a resource in an environment where
there are many threads of execution. Locks are one way of enforcing concurrency control
policies. Transaction uses locks to deny access to other transactions and so prevent incorrect
updates.
Lock prevents another transaction from modifying item or even reading it, in the case of a write
lock.
Lock (X): If a transaction T1 applies Lock on data item X, then X is locked and it is not
available to any other transaction.
Unlock (X): T1 Unlocks X. X is available to other transactions.
Types of a Lock
Shared lock: A Read operation does not change the value of a data item. Hence a data item can
be read by two different transactions simultaneously under share lock mode. So only to read a
data item T1 will do: Share lock (X), then Read (X), and finally Unlock (X).
Exclusive lock: A write operation changes the value of the data item. Hence two write
operations from two different transactions or a write from T1 and a read from T2 are not
allowed. A data item can be modified only under Exclusive lock. To modify a data item T1 will
do: Exclusive lock (X), then Write (X) and finally Unlock (X).

146
When these locks are applied, then a transaction must behave in a special way. This special
behavior of a transaction is referred to as well-formed.
Well-formed: A transaction is well- formed if it does not lock a locked data item and it does not
try to unlock an unlocked data item.
Locking - Basic Rules
 If transaction has shared lock on item, can read but not update item.
 If transaction has exclusive lock on item, can both read and update item.
 Reads cannot conflict, so more than one transaction can hold shared locks simultaneously
on same item.
 Exclusive lock gives transaction exclusive access to that item.
 Some systems allow transaction to upgrade a shared lock to an exclusive lock, or vice-
versa.
Examples: T1 and T2 are two transactions. They are executed under locking as follows. T1
locks A in exclusive mode. When T2 want s to lock A, it finds it locked by T1 so T2 waits for
Unlock on A by T1. When A is released then T2 locks A and begins execution.
Suppose a lock on a data item is applied, the data item is processed and it is unlocked
immediately after reading/writing is completed as follows.
Initial values of A = 10 and B = 20.
Table 1 locking thechnique
Serial Execution of T1 and then T2 Concurrent Execution of T1 and T2
T1 T1 T1 T2
Lock (A) Lock (A)
read (A) {A = 10} read (A) {A = 10}
A := A + 100 A := A + 100
write (A) (A = write (A) (A = 110}
110}
Unlock (A) Unlock (A)
Lock (B) Lock (B)
read (B) {B = 20} read (B) {B = 20}
B := B + 10 B := B * 5
write (B) {B =30} write (B) {B =
100}
Unlock (B) Unlock (B)
Lock (B) Lock (B)
read (B) {B = 30} read (B) {B = 100}
B := B * 5 B := B + 10
write (B) {B = 150} write (B) {B = 110}
Unlock (B) Unlock (B)
Lock (A) Lock (A)
Read (A) {A = Read (A) {A =
110} 110}
A := A + 20 A := A + 20
Write (A) {A = Write (A) {A =
130} 130}
Unlock (A) Unlock (A)

146
Final Result: A=130 B=150 Final Result: A=130 B=110

The final result of the two transactions using the two types of transaction execution (serial and
concurrent) is not the same. This indicates that the above method of locking and unlocking is not
correct. Thus, to preserve consistency we have to use another approach to locking, two-phase
locking scheme. Two-Phase Locking (2PL) A transaction follows 2PL protocol if all locking
operations precede the first unlock operation in the transaction. The 2PL protocol demands
locking and unlocking of a transaction to have two phases.
 Growing phase - acquires all locks but cannot release any locks.
 Shrinking phase - releases locks but cannot acquire any new locks.
Locking methods: problems Deadlock: A deadlock that may result when two (or more)
transactions are each waiting for locks held by the other to be released. Deadlock - possible
solutions only one-way to break deadlock: abort one or more of the transactions in the
deadlock. Deadlock should be transparent to user, so DBMS should restart transaction(s). Two
general techniques for handling deadlock:
 Deadlock prevention
 Deadlock detection and recovery
Timeout The deadlock detection could be done using the technique of TIMEOUT. Every
transaction will be given a time to wait in case of deadlock. If a transaction waits for the
predefined period of time in idle mode, the DBMS will assume that deadlock occurred and it will
abort and restart the transaction.
2. Time-stamping Method
Timestamp: a unique identifier created by DBMS that indicates relative starting time of a
transaction. Can be generated by:

 using system clock at time transaction started, or

 Incrementing a logical counter every time a new transaction starts.
Time-stamping: A concurrency control protocol that orders transactions in such a way that older
transactions, transactions with smaller time stamps, get priority in the event of conflict.
Transactions ordered globally base do their timestamp so that older transactions, transactions
with earlier timestamps, get priority in the event of conflict.
 Conflict is resolved by rolling back and restarting transaction.

146
  Since there is no need to use lock there will be No Deadlock.
In timestamp ordering, the schedule is equivalent to the particular serial order that corresponds to
the order of the transaction timestamps. To implement this scheme, every transaction will be
given a timestamp which is a unique identifier of a transaction. If Ti came to processing prior to
Tj then TS of Tj will be larger than TS of Ti. Again each data item will have a timestamp for
Read and Write.
 WTS(A) which denotes the largest timestamp of any transaction that successfully
executed Write(A)
 RTS(A) which denotes the largest timestamp of any transaction that successfully
executed Read(A)
These timestamps are updated whenever a new Read(A) or Write(A) instruction is executed.
Read/write proceeds only if last update on that data item was carried out by an older transaction.
Otherwise, transaction requesting read/write is restarted and given a new timestamp.
The timestamp ordering protocol ensures that any conflicting read and write operations are
executed in the timestamp order. The protocol manages concurrent execution such that the time-
stamps determine the serializability order. Rules for permitting execution of operations in
Time-stamping Method Suppose that Transaction Ti issues Read(A)
 If TS(Ti) < WTS(A): this implies that Ti needs to read a value of A which was already
overwritten. Hence the read operation must be rejected and Ti is rolled back.
 If TS(Ti) >= WTS(A): then the read is executed and RTS(A) is set to the maximum of
RTS(A) and TS(Ti).
Suppose that Transaction Ti issues Write(A)
 If TS(Ti) < RTS(A): then this implies that the value of A that Ti is producing was
previously needed and it was assumed that it would never be produced. Hence, the Write
operation must be rejected and Ti is rolled back.
 If TS(Ti) < WTS(A): then this implies that Ti is attempting to Write an object value of A.
hence, this write operation can be ignored.
 Otherwise the Write operation is executed and WTS(A) is set to the maximum of
WTS(A) or TS(Ti).
A transaction that is rolled back due to conflict will be restarted and be given a new timestamp.
Problem with timestamp-ordering protocol:

146
  Suppose Ti aborts, but Tj has read a data item written by Ti
 Then Tj must abort; if Tj had been allowed to commit earlier, the schedule is not
recoverable.
 Further, any transaction that has read a data item written by Tj must also abort
 This can lead to cascading rollback…
Cascading Rollback Whenever some transaction T tries to issue a Read_Item(X) or a
Write_Item(X) operation, the basic timestamp ordering algorithm compares the timestamp of T
with the read timestamp and the write timestamp of X to ensure that the timestamp order of
execution of the transactions is not violated. If the timestamp order is violated by the operation,
then transaction T will violate the equivalent serial schedule, so T is aborted. Then T is
resubmitted to the system as a new transaction with new timestamp. If T is aborted and rolled
back, any transaction Ti that may have used a value written by T must also be rolled back.
Similarly, any transaction Tj that may have used a value written by Ti must also be rolled back,
and so on. This effect is known as cascading rollback.
3. Optimistic Technique
 Locking and assigning and checking timestamp values may be unnecessary for some
transactions
 Assumes that conflict is rare.
 When transaction reaches the level of executing commit, a check is performed to
determine whether conflict has occurred. If there is a conflict, transaction is rolled back
and restarted.
 Based on assumption that conflict is rare and more efficient to let transactions proceed
without delays to ensure serializability.
 At commit, check is made to determine whether conflict has occurred.
 If there is a conflict, transaction must be rolled back and restarted.
 Potentially allows greater concurrency than traditional protocols.
 Three phases:
1. Read
2. Validation
3. Write
1. Optimistic Techniques - Read Phase

146
  Extends from start until immediately before commit.
 Transaction reads values from database and stores them in local variables. Updates are
applied to a local copy of the data.
2. Optimistic Techniques - Validation Phase
 Follows the read phase.
 For read-only transaction, checks that data read are still current values. If no
interference, transaction is committed, else aborted and restarted.
 For update transaction, checks transaction leaves database in a consistent state, with
serializability maintained.
3. Optimistic Techniques - Write Phase
 Follows successful validation phase for update transactions.
 Updates made to local copy are applied to the database.
7.3. Granularity of data items
Granularity is the size of the data items chosen as the unit of protection by a concurrency
control protocol. It could be:
The entire database
 A file
 A page (a section of physical disk in which relations are stored)
 A record
 A field value of a record
The granularity has effect on the performance of the system. As locking will prevent access to
the data, the size of the data required to be locked will prevent other transactions from having
access. If the entire database is locked, then consistency will be highly maintained but less
performance of the system will be witnessed. Is a single data item is locked; consistency maybe
at risk but concurrent processing and performance will be enhanced. Thus, as one go from the
entire database to a single value, performance and concurrent processing will be enhanced but
consistency will be at risk and needs good concurrency control mechanism and strategy.

Review Exercise Seven

Chapter 7

1. Define transaction and its basic characteristics.

146
2. Depict state of transaction with suitable diagram.
3. What are the three basic concurrency control techniques?
4. What is deadlock?
5. What does mean granularity?

146
 Chapter - Eight
Database Recovery
Database recovery is the process of restoring database to a correct state in the event of a failure.
A database recovery is the process of eliminating the effects of a failure from the database.
Recovery, in database systems terminology, is called restoring the last consistent state of the data
items. Types of failures A failure is a state where data inconsistency is visible to transactions if
they are scheduled for execution. The kind of failure could be:
 System crashes, resulting in loss of main memory,
 Media failures, resulting in loss of parts of secondary storage,
 Application software errors,
 Natural physical disasters,
 Carelessness or unintentional destruction of data or facilities,
 Sabotage
In databases usually a failure can generally be categorized as one of the following major groups:
1. Transaction failure: a transaction cannot continue with its execution, therefore, it is aborted
and if desired it may be restarted at some other time. Reasons: Deadlock, timeout, protection
violation, or system error.
2. System failure: the database system is unable to process any transactions. Some of the
common reasons of system failure are: wrong data input, register overflow, addressing error,
power failure, memory failure, etc.
3. Media failure: failure of non-volatile storage media (mainly disk). Some of the common
reasons are: head crash, dust on the recording surfaces, fire, etc.
To make the database secured, one should formulate a ―plan of attack‖ in advance. The plan
will be used in case of database insecurity that may range from minor inconsistency to total loss
of the data due to hazardous events
The basic steps in performing a recovery are
1. Isolating the database from other users. Occasionally, you may need to drop and re-create the
database to continue the recovery.
2. Restoring the database from the most recent useable dump.
3. Applying transaction log dumps, in the correct sequence, to the database to make the data as
current as possible.

146
It is a good idea to test your backup and recovery plans periodically by loading the backups and
transaction logs into a test database and verifying that your procedure really works. One can
recover databases after three basic types of problems: user error, software failure, and hardware
failure. Each type of failure requires a recovery mechanism. In a transaction recovery, the effect
of failed transaction is removed from the database, if any. In a system failure, the effects of failed
transactions have to be removed from the database and the effects of completed transactions have
to be installed in the database. The database recovery manger is responsible to guarantee the
atomicity and durability properties of the ACID property. The execution of a transaction T is
correct if, given a consistent database; T leaves the database in the next consistent state. Initial
consistent state of the database: S1. T changes the consistent state from S1 to S2. During this
transition the database may go into an inconsistent state, which is visible only to T. If the system
or T fails then database will not be able to reach S2, consequently the visible state would be an
inconsistent state. From this state we can go either forward (to state S2) or go backward (to state
S1).
Example: The initial value of A=100, B=200 and C=300 The Required state after the execution
of T1 is A=500, B=800 and C=700 Thus S1= (100,200,300) AND S2= (500,800,700)
Transaction (T1)

146
Force writing is the explicit writing of the buffers to secondary storage.

8.1. Transactions and Recovery

 Transactions represent basic unit of recovery.
 Recovery manager responsible for atomicity and durability
 If failure occurs between commit and database buffers being flushed to secondary
storage then, to ensure durability, recovery manager has to redo (roll forward)
transaction's updates.
 If transaction had not committed at failure time, recovery manager has to undo (rollback)
any effects of that transaction for atomicity.
 Partial undo - only one transaction has to be undone.
 Global undo - all transactions have to be undone.
Transaction Log: Execution history of concurrent transactions.

146
DBMS starts at time t0, but fails at time tf. Assume data for transactions T2 and T3 have been
written to secondary storage.
 T1 and T6 have to be undone. In absence of any other information, recovery manager
has to redo T2, T3, T4, and T5.
 Tc is the checkpoint time by the DBMS
 Recovery Facilities
 DBMS should provide following facilities to assist with recovery:
 Backup mechanism: that makes periodic backup copies of database.
 Logging facility: that keeps track of current state of transactions and database changes.
 Checkpoint facility: that enables updates to database in progress to be made permanent.
Recovery manger: which allows DBMS to restore the database to a consistent state following a
failure.
Restoring the database means transforming the state of the database to the immediate good state
before the failure. To do this, the change made on the database should be preserved. Such kind of
information is stored in a system log or transaction log file. Log File
Contains information about all updates to database:
 Transaction records
 Checkpoint records
 Often used for other purposes (for example, auditing).
Transaction records contain:
 Transaction identifier.
 Type of log record, (transaction start, insert, update, delete, abort, commit)
 Identifier of data item affected by database action (insert, delete, and update operations)
 Before-image of data item
 After-image of data item.
 Log management information.
 Log file sometimes split into two separate random-access files.
 Potential bottleneck; critical in determining overall performance.

146
Table 2 Transaction records

Check pointing: Checkpoint is a point of synchronization between database and log file. All
buffers are force-written to secondary storage.
 Checkpoint record is created containing identifiers of all active transactions.
 When failure occurs, redo all transactions that committed since the checkpoint and undo
all transactions active at time of crash.
 In previous example, with checkpoint at time tc, changes made by T2 and T3 have been
written to secondary storage. Thus:
 only redo T4 and T5,
 Undo transactions T1 and T6.
8.2. Database Recovery Techniques
Damage to the database could be either physical and relate which will result in the loss of the
data stored or just inconsistency of the database state after the failure. For each we can have a
recover mechanism:
1. If database has been damaged:
 Need to restore last backup copy of database and reapply updates of committed
transactions using log file.

146
  Extensive damage/catastrophic failure: physical media failure; is restored by using the
backup copy and by re executing the committed transactions from the log up to the time
of failure.
2. If database is only inconsistent:
 No physical damage/only inconsistent: the restoring is done by reversing the changes made
on the database by consulting the transaction log.
 Need to undo changes that caused inconsistency. May also need to redo some transactions to
ensure updates reach secondary storage.
 Do not need backup, but can restore database using before- and after-images in the log file.

8.2.1. Recovery Techniques for Inconsistent Database State

Recovery is required if only the database is updated. The kind of recovery also depends on the
kind of update made on the database. Database update: A transaction‘s updates to the database
can be applied in two ways: Three main recovery techniques:
1. Deferred Update
2. Immediate Update
3. Shadow Paging
Deferred Update
Updates are not written to the database until after a transaction has reached its commit point. If
transaction fails before commit, it will not have modified database and so no undoing of changes
required. May be necessary to redo updates of committed transactions as their effect may not
have reached database. A transaction first modifies all its data items and then writes all its
updates to the final copy of the database. No change is going to be recorded on the database
before commit. The changes will be made only on the local transaction workplace. Update on the
actual database is made after commit and after the change is recorded on the log. Since there is
no need to perform undo operation it is also called NO-UNDO/REDO Algorithm
Immediate Update/ Update-In-Place
 Updates are applied to database as they occur.
 Need to redo updates of committed transactions following a failure.
 May need to undo effects of transactions that had not committed at time of failure.
 Essential that log records are written before write to database. Write-ahead log protocol.

146
  If no "transaction commit" record in log, then that transaction was active at failure and
must be undone.
 Undo operations are performed in reverse order in which they were written to log.
As soon as a transaction updates a data item, it updates the final copy of the database on the
database disk. During making the update, the change will be recorded on the transaction log to
permit rollback operation in case of failure. UNDO and REDO are required to make the
transaction consistent. Thus, it is called UNDO/REDO Algorithm. This algorithm will undo all
updates made in place before commit. The redo is required because some operations, which are
completed but not committed, should go to the database. If we don‘t have the second scenario,
then the other variation of this algorithm is called UNDO/NO-REDO Algorithm.
Shadow Paging
It maintains two page tables during life of a transaction: current page and shadow page table.
When transaction starts, two pages are the same. Shadow page table is never changed thereafter
and is used to restore database in event of failure. During transaction, current page table records
all updates to database. When transaction completes, current page table becomes shadow page
table.

Review Exercise Eight

Chapter 8

1. What is database recovery?

2. What are different types of failures?
3. What are the three type of recovery technique?

146
 Chapter – Nine
Distributed Database Systems
Before the development of database technology, every application used to have its own data in
the application logic.
Database development facilitates the integration of data available in an organization from a
number of applications and enforces security on data access on a single local site. However, it is
not always the case that organizational data reside in one central site. This demand databases at
different sites to be integrated and synchronized with all the facilities of database approach.
This is will be made possible by computer networks and data communication optimized by
internet, mobile and wireless computing and intelligent devices.
This leads to Distributed Database Systems.
The decentralization approach to database mirrors the natural organizational structure of
companies, which are logically distributed in to divisions, departments, projects and so on and
physically, distributed in to offices, plants, and factories each of which maintains its own
operational data. Distributed Database is not a centralized database.

Figure 11 centralized and Distributed database

9.1. Data Distribution Strategies

Distributed DB stores logically related shared data and metadata at several physically
independent sites connected via network. Distributed DBMS is the software system that permits
the management of a Distributed DB and makes the distribution transparent to the user. Data
allocation is the process of deciding where to allocate/store particular data item.
There are 3 data allocation strategies:
1. Centralized: the entire DB is located at a single site. And computers access through networks.
Known as distributed processing.

146
2. Partitioned: the DB is split into several disjoint parts (called partitions, segments or
fragments) and stored at several sites.
3. Replicated: copies of one or more partitions are stored at several sites
Selective- combines fragmentation (locality of reference for those which are less updated)
replication and centralization as appropriate for the data.
Complete: - database copy is made available in each site. Snap shot is one method used here.
In a distributed database system, the database is logically stored as single database but
physically fragmented on several computers. The computers in a distributed system
communicate with each other through various communication media, such as high speed buses
or telephone line. A distributed database system has the following components.
 Local DBMS
 Distributed DDBMS
 Global System Catalog(GSC)
 Data communication (DC)
A distributed database system consists of a collection of sites, each of which maintains a local
database system (Local DBMS) but each local DBMS also participates in at least one global
transaction where different databases are integrated together.
 Local Transaction: transactions that access data only in that single site
 Global Transaction: transactions that access data in several sites.
 Parallel DBMS: a DBMS running across multiple processors and disks that is designed
to execute operations in parallel, whenever possible, in order to improve performance.
Three architectures for parallel DBMS:
 Shared Memory- for fast data access for a limited number of processors.
 Shared Disk- for application inherently centralized
 Shared nothing.- massively parallel
 What makes DDBMS different is that
 The various sites are aware of each other
 Each site provides a facility for executing both local and global transactions.
The different sites can be connected physically in different topologies.
 Fully /networked,
 Partially Connected,
 Tree Network,
 Star Network and
 o Ring Network
The differences between these sites is based on:
Installation Cost: cost of linking sites physically.
Communication Cost: cost to send and receive messages and data
Reliability: resistance to failure
Availability: degree to which data can be accessed despite the failure.
The distribution of the database sites could be:
1. Large Geographical Area: Long-Haul Network
 relatively slow
 less reliable
 uses telephone line, microwave, satellite
2. Small Geographical Area: Local Area Network
 higher speed

146
  lower rate of error
 use twisted pair, base band coaxial, broadband coaxial, fiber optics
Even though integration of data implies centralized storage and control, in distributed database
systems the intention is different. Data is stored in different database systems in a decentralized
manner but act as if they are centralized through development of computer networks. A
distributed database system consists of loosely coupled sites that share no physical component
and database systems that run on each site are independent of each other.
 Those, which share physical components, are known as Parallel DBMS.
 Transactions may access data at one or more sites
 Organization may implement their database system on a number of separate computer
system rather than a single, centralized mainframe. Computer Systems may be located at
each local branch office.

9.2. Functions of a DDBMS

DDBMS have the following functionality.
 Extended Communication Services to provide access to remote sites
 Extended Data Dictionary- to store data distribution details a need for global system
catalog
 Distributed Query Processing - optimization of query remote data access
 Extended security- access control to a distributed data
 Extended Concurrency Control –maintain consistency of replicated data
 Extended Recovery Services- failures of individual sites and the communication line.

9.3. Issues in DDBMS How is data stored in DDBMS?

There are several ways of storing a single relation in distributed database systems.
1. Replication:
 System maintains multiple copies of similar data (identical data)
 Stored in different sites, for faster retrieval and fault tolerance.
 Duplicate copies of the tables can be kept on each system (replicated). With this option,
updates to the tables can become involved (of course the copies of the tables can be read-
only).
 Advantage: Availability, Increased parallelism (if only reading)
 Disadvantage: increased overhead of update
2. Fragmentation:
Relation is partitioned into several fragments stored in distinct [Link] partitioning could be
vertical, horizontal or both.
I. Horizontal Fragmentation
Systems can share the responsibility of storing information from a single table with individual
systems storing groups of rows. It is performed by the Selection Operation. The whole content
of the relation is reconstructed using the UNION operation

146
Figure 12 horizontal fragmentation
Vertical Fragmentation Systems can share the responsibility of storing particular attributes of a
table. It Needs attribute with tuple number (the primary key value be repeated.) which is
performed by the Projection Operation. The whole content of the relation is reconstructed using
the Natural JOIN operation using the attribute with Tuple number (primary key values)

146
Figure 13 horizontal fragmentation
Both (hybrid fragmentation) is a system that can share the responsibility of storing particular
attributes of a subset of records in a given relation. It is reformed by projection then selection
or selection then projection relational algebra operators. Reconstruction is made by combined
effect of Union and natural join operators
Fragmentation is correct if it fulfills the following
1. Complete: - a data item must appear in at least one fragment of a given relation R (R1,
R2…Rn).
2. Reconstruction:- it must be possible to reconstruct a relation from the fragments
3. Disjointness: - a data item should only be found in a single fragment except for vertical
fragmentation (the primary key is repeated for reconstruction).
Data transparency: The degree to which system user may remain unaware of the details of how
and where the data items are stored in a distributed system.
1. Distribution transparency Even though there are many systems they appear as one- seen as a
single, logical entity.
2. Replication transparency Copies of data floating around everywhere also seem like just one
copy to the developers and users

146
3. Fragmentation transparency A table that is actually stored in parts everywhere across sites
may seem like just a single table in a single location
4. Location Transparency- the user doesn‘t need to know where a data item is physically
located.
How does it work? Distributed computing can be difficult to implement, particularly for
replicated data that can be updated from many systems. In order to operate a distributed database
system has to take care of
 Distributed Query Processing
 Distributed Transaction Management
 Replication Data Management -If you are going to have copies of data on many
machines how often does the data get updated if it is changed in another system? Who is
in charge of propagating the update to the data?
 Distributed Database Recovery If one machine goes down how does that affect the
others.
 Security: Just like any computer network, a distributed system needs to have a common
way to validate users entering from any computer in the network of servers.
 Common Data-Dictionary Your schema now has to be distinguished and work in
connection to schemas created on many systems.
9.4. Homogeneous and Heterogeneous Distributed Databases
1. In a homogeneous distributed database
 All sites have identical software (DBMS)
 Are aware of each other and agree to cooperate in processing user requests.
 Each site surrenders part of its autonomy in terms of right to change schemas or software
 Appears to the user as a single system
2. In a heterogeneous distributed database
 Different sites may use different schemas and software (DBMS)
 Difference in schema is a major problem for query processing
 Difference in software is a major problem for transaction processing
 Sites may not be aware of each other and may provide only limited facilities for
cooperation in transaction processing.
 May need gateways to interface one another.

146
9.5. Advantages and disadvantages of DDBMS
9.5.1. Why DDBMS/Advantages
1. Many existing systems
 Maybe you have no choice.
 Possibly there are many different existing system, with possible different kinds of
systems (Oracle, Informix, others) that need to be used together.
2. Data sharing and distributed control:
 User at one site may be able to access data that is available at another site.
 Each site can retain some degree of control over local data
 We will have local as well as global database administrator
3. Reliability and availability of data If one site fails the rest can continue operation as long as
transaction does not demand data from the failed system and the data is not replicated in other
sites
4. Speedup of query processing If a query involves data from several sites, it may be possible
to split the query into sub-queries that can be executed at several sites which is parallel
processing. Query can be sent to the least heavily loaded sites
5. Expansion(Scalability):In a distributed environment you can easily expand by adding more
machines to the network.
9.5.2. Disadvantages of DDBMS
1. Software Development Cost
Is difficult to install, thus is costly
2. Greater Potential for Bugs
Parallel processing may endanger correctness of algorithms
3. Increased Processing Overhead: Exchange of message between sites – high communication
latency: Due to communication jargons
4. Communication problems
5. Increased Complexity and Data Inconsistency Problems: Since clients can read and modify
closely related data stored in different database instances concurrently.
6. Security Problems: network and replicated data security.

146
9.6. Query Processing and Transaction Management in DDBMS Query
Processing
There are different strategies to process a specific query, which in turn increase the performance
of the system by minimizing processing time and cost. In addition to the cost estimates we have
for a centralized database (disk access, relation size, etc), we have to consider the following in
distributed query processing:
 Cost of data transmission over the huge network
 Gain of parallel processing of a single query
For the case of Replicated data allocation, even though parallel processing is used to increase
performance, update will have a great impact since all the sites containing the data item should
be updated. For the case of fragmentation, update works more like the centralized database but
reconstruction of the whole relation will require accessing data from all sites containing part of
the relation. Let the distributed database has three sites (S1, S2, and S3). And two relations,
EMPLOYEE and DEPARTMENT are located at S1 and S2 respectively without any
fragmentation. And a query is initiated from S3 to retrieve employees [First Name (15 byte
long), Last name (15 byte long) and Department name (10 byte long) total of 40 bytes with the
department they are working in. 72 Advanced Database Systems Lecture Note – Wollo
University, Department of Computer Science
Let: For EMPLOYEE we have the following information
1. 10,000 records
2. each record is 100 bytes long
For DEPARTMENT we have the following information
3. 100 records
4. each record is 35 bytes long
There are three ways of executing this query:
1. Transfer DEPARTMENT and EMPLOYEE to S3 and perform the join there: needs transfer of
10,000*100+100*35=1,003,500 byte.
2. Transfer the EMPLOYEE to S2, perform the join there which will have 40*10,000 = 400,000
bytes and transfer the result to S3. we need 1,000,000+400,000=1,400,000 byte to be transferred

146
3. Transfer the DEPARTMENT to S1, perform the join there which will have 40*10,000 =
400,000 bytes and transfer the result to S3. We need 3,500+400,000=403,500 byte to be
transferred.
Then one can select the strategy that will reduce the data transfer cost for this specific query.
Other steps of optimization may also be included to make the processing more efficient by
reducing the size of the relations using projection. Transaction Management Transaction is a
logical unit of work constituted by one or more operations executed by a single user. A
transaction begins with the user's first executable query statement and ends when it is committed
or rolled back. A Distributed Transaction is a transaction that includes one or more statements
that, individually or as a group, update data on two or more distinct nodes of a distributed
database.
Representation of Query in Distributed Database
SQL Statement Object Database Domain
SELECT * FROM dept sales [Link];
dept@[Link]
[Link];
There are two types of transaction in DDBMS to access data from other sites:
1. Remote Transaction: contains only statements that access a single remote node. Thus,
Remote Query statement is a query that selects information from one or more remote tables, all
of which reside at the same remote node or site.
For example, the following query accesses data from the dept table in the Addis schema (the site)
of the remote sales database:
SELECT * FROM [Link]@[Link];
A remote update statement is an update that modifies data in one or more tables, all of which
are collocated at the same remote node. For example, the following query updates the branch
table in the Addis schema of the remote sales database:
UPDATE [Link]@ [Link];
SET loc = 'Arada'
WHERE BranchNo = 5;
2. Distributed Transaction: contains statements that access more than one node.
A distributed query statement retrieves information from two or more nodes. If all statements of
a transaction reference only a single remote node, the transaction is remote, not distributed.

146
A database must guarantee that all statements in a transaction, distributed or non-distributed,
either commit or roll back as a unit. The effects of an ongoing transaction should be invisible to
all other transactions at all nodes; this transparency should be true for transactions that include
any type of operation, including queries, updates, or remote procedure calls.
o For example, the following query accesses data from the local database as well as the remote
sales database:
SELECT ename, dname
FROM [Link] DS, [Link]@ [Link] AD
WHERE [Link] = [Link]; {Employee data is stored in Dessie and Sales data is stored in
Addis, there is an employee responsible for each sale}
Different kinds of SQL statements
Remote query
client_nm from clients@[Link];
Distributed query
select project_name, student_nm from intership@[Link] i, student s where
s.stu_id = i.stu_id
Remote Update
update intership@[Link] set stu_id = '242' where stu_id = '200'
Distributed Update
update intership@[Link] set stu_id = '242' where stu_id = '200' update student
set stu_id = '242' where stu_id = '200' commit
Concurrency Control
There are various techniques used for concurrency control in centralized database systems. The
techniques in distributed database system are similar with the centralized approach with
additional implementation requirements or modifications.
The main difference or the change that should be incorporated is the way the lock manager is
implemented and how it functions. There are different schemes for concurrency control in DDBS
1. Non-Replicated Scheme
 No data is replicated in the system
 All sites will maintain a local lock manager (local lock and unlock)
 If site Si needs a lock on data in site Sj it send message to lock manager of site

146
  Sj and the locking will be handled by site Sj
 All the locking and unlocking principles are handled by the local lock manager in which
the data object resides.
 Is simple to implement
 Need three message transfers
 To request a lock
 To notify grant of lock
 To request unlock
2. Single Coordinate Approach
 The system choose one single lock manager that resides in one of the sites (Si)
 All locks and unlocks requests are made at site Si where the lock manager resides
 Is simple to implement
 Needs two message transfers
 To request a lock
 To request unlock
 Simple deadlock handling
 Could be a bottleneck since all processes are handled at one site
 Is vulnerable/at risk if the site with the lock manager fails

Review Exercise Nine

Chapter 9

1. Differentiate distributed vs central database.

2. What does mean fragmentation and replication?
3. Discuss in detail homogenous and heterogeneous distribute database?
4. List down some advantages and disadvantages of distributed
database.

146
 Chapter – Ten
Introduction to Object-Oriented Database Systems Object
Orientation
An object-oriented database (OOD) is a database system that can work with complex data
objects i.e objects that mirror those used in object-oriented programming languages.

In object-oriented programming, everything is an object, and many objects are quite complex,
having different properties and methods. An object-oriented database management system works
in concert with an object-oriented programming language to facilitate the storage and retrieval of
object-oriented data.

You might be thinking, “Wait, I use objects in my programming all the time. In addition, I use a
database. So, does that mean the database I use is an OOD?” Probably not, and the reason has to
do with one of the main features of OOD: object data persistence.

When your program is running, you might have an object, for example, an instance of a task.
That object has properties like a name and status. It might also have some methods
like update_task() or get_task_history(). Somewhere early in your program, you initialized
that task object, and now you have access to it because it is stored in memory.

What happens when your program terminates execution? Your object… is gone. That data object
was transient, not persistent. The next time your program starts up, you’ll need to retrieve those
data values (like name and status) from your database all over again in order to initialize
a new task object instance.

With an OOD, data objects are stored with all of their properties in the database. When your
program terminates, the objects continue to persist, stored in the OOD. When your program
starts up again, it can retrieve an object with the properties from the database. The process of
storing and retrieving a complex data object with an OOD is transparent to the user of the
database.

This is quite different from relational databases (like MySQL or SQLite) but not significantly
from document databases (like MongoDB). In relational databases, the developer needs to
compose an object from the results of a set of queries, while in document databases the mapping
of the document fields to the class properties should be almost transparent.

146
OODs have been around for decades. MongoDB Realm is one of the new and promising pieces
of software in that field.

10.1. Object Orientation

It is set of design and development principles and works based on autonomous computer
structures known as objects

10.2. OO Contribution areas

The following are OO contribution areas

 Programming Languages
 Graphical User Interfaces
 Databases
 Design
 Operating Systems

10.3. Evolution of OO Concepts

Concepts stem from object-oriented programming languages (OOPLs)
 Ada, ALGOL, LISP, SIMULA
 OOPLs goals
 Easy-to-use development environment
 Powerful modeling tools for development
 Decrease in development time
 Make reusable code
 OO Attributes
 Data set not passive
 Data and procedures bound together
 Objects can act on itself
Advanced Database Applications The application of database is being highly practiced in
complex applications demanding different way of modeling and designing. Some of these
applications are:
 Computer Aided Design (CAD)
 Computer Aided Manufacturing
 Computer Aided Software Engineering
 Network Management System
 Multimedia System
 Digital Publication
 Geographic Information System
 Interactive and Dynamic Web Sites

Drawbacks/Weaknesses of Relational DBMS In addition to the emergence of many advanced

database application areas, there were some drawbacks on the relational database management
system.
1. Poor representation of ‗real world‘ entities: relations does not correspond to real world objects

146
2. Semantic overloading (semantically Overloaded): Representation of complex relationship is
difficult
Eg. M:N relationship is represented by adding one additional relation (making the relation an
entity)
 One cannot distinguish a relation from a relationship.
 Difficult to distinguish different types of relationship.
3. Poor support for integrity and enterprise constraints: Many commercial BMS do not support
all integrity constraints. The relational model do not support enterprise constraint, it has to be
done on the DBMS
4. Homogeneous data structure
 Has vertical and horizontal homogeneity
 Horizontal Homogeneity: Each tuple of a relation have same number and type of
attributes
 Vertical Homogeneity: Values of an attribute should come from same domain.
 Field value should be atomic
5. Limited operations
 Relational model has fixed operations on the data
 Does not allow additional/new operations
6. Difficulty in handling recursive queries: Direct and indirect recursive queries of a single
relation cannot be represented. Query to extract information from recursive relationship between
tuples of same entity is difficult to represent.
7. Impedance mismatch Mixing of different programming paradigms: Mismatch between the
languages used
8. Poor navigational process: Access is based on navigating individual records from different
relations

10.4. Object oriented Concepts

Object is a uniquely identifiable entity that contains both the attributes that describes the state of
the ‗real world‘ object and the action that are associated with it. OODBMS can manage;

 complex, highly interrelated information.

 Abstract representation of a real-world entity
 Unique identity
 Embedded properties
 Ability to interact with other objects and self

OID (Object Identity) Each object is unique in OO systems, Unique to object, Not a primary
key (PK is unique only for a relation, PK is selected from attribute making it dependent on the
state), Is invariant (will not change), Independent of values of attributes ( two objects can have
same state but will have different OID), Is invisible to users
• Entity integrity is enforced in oop
• Relationship: embedding the OID of one object into the other ( embed OID for a branch to
employee object)
Advantage of using OID:
 Are efficient

146
  Are fast
 Cannot be modified by users (system generated)
 Independent of content

Figure 14 representation of objects

Attributes and Methods: An object has state and behaviors. An object has properties (which might also
be called attributes) like name, status, and create_date. The set of properties taken together represents
its state. Along with this, an object has behaviors (also known as methods, actions, or functions) that
modify or operate on its properties, like update_task() or get_task_history().
Object state: It is object values at any given time and values of attributes at any given point in
time.

146
Figure 15 representation of object and method
Messages
 Means by which objects communicate
 Request from one object to the other to activate one of its methods
 Invokes method/calls method to be applied
 Sent to object from real world or other object
 Notation: Object. Method
Eg: Staff Object. Update salary(slary)

146
Figure 16 mwessaging process in redal worled events
Classes: It is grouping of all objects with the same properties and behaviors form a class. In our
example above, we talked about task objects. These objects together all belong to the Task class.
 Blueprint for defining similar objects
 Objects with similar attributes and respond to same message are grouped together
 Defined only once and used by many objects
 Collection of similar objects
 Shares attributes and structure
o Objects in a class are called instances of the class
Eg: Class Definition : defining the class BRANCH
BRANCH
Attributes
BrabchNo
street
city
postcode
Methods
Print()
getPostCode()
numberofStaff()

Objects of BRANCH class

146
brabchNo=B005 brabchNo=B007 brabchNo=B003
street=st1 street=st2 city=Dire street=st2
city=Addis postcode=452 city=Bahirdar
postcode=1425 postcode=85

Figure 17 class assigning techniques

I. Object Characteristics
1. Class Hierarchy

146
• Superclass
• Subclass
2. Inheritance
It is bility of object to inherit the data structure and behavior of classes above it
• Single inheritance – class has one immediate superclass
• Multiple – class has more than one immediate superclass
II. Method Overriding
• Method redefined at subclass
III. Polymorphism
• Allows different objects to respond to same message in different ways

10.4.1 Object Classification

Objects in oop can be classified as follows

A) Simple
They are only single-valued attributes have no attributes refer to other objects.
B) Composite
They have at least one multi-valued attribute and no attributes refer to other object
C) Compound
They have at least one attribute that references other object
D) Hybrid
They are repeating group of attributes and can at least one refers to other object

10.5. Characteristics of OO Data Model

OO Data Model has the following characteristics
 Supports complex objects
 Must be extensible
 Supports encapsulation
 Exhibit inheritance
 Supports object identity

146
Figure 18 OO Data Model
Table 3 OO vs. E-R Model Components
OO Data Model E-R Model
Type Entity definition
Object Entity Instance
Class Entity set
Instance variable Attribute
N/A Primary key
OID N/A
Class hierarchy E-R diagram

10.5. OODBMS
Object-oriented database technology is a marriage of object-oriented programming and database
technologies. Database management system integrates benefits of typical database systems with
OODM characteristics
 Handles a mix of data types (since OODBMS permits new data definition)
 Follows OO rules
 Follows DBMS rules

10.5.1 OO and Database Design

It provides data identification and the procedures for data manipulation
 Data and procedures self-contained entity

146
  Iterative and incremental
 DBA does more programming
 Lack of standards

10.5.2 OODBMS Advantages

 More semantic information
 Support for complex objects
 Extensibility of data types (user defined data types)
 May improve performance with efficient caching
 Versioning
 Polymorphism: one operation shared by many objects and each acting differently
 Reusability
 Inheritance speeds development and application: defining new objects in terms of

 Potential to integrate DBMSs into single environment

 Relationship between objects is represented explicitly supporting both navigational and
associative access to information.
10.5.3. OODBMS Disadvantages
 Strong opposition from the established RDBMSs
 Lack of theoretical foundation
 No standard
 No single data model
 Throwback to old pointer systems
 Lack of standard ad hoc query language
 Lack of business data design and management tools
 Steep learning curve
 Low market presence
 Lack of compatibility between different OODBMSs

Review Exercise Ten

Chapter 10

1. What is object-oriented database?

146
2. What are the contribution areas of object-oriented?
3. Write OQL based on the following information
Let myMovie denote an object of type Movie. Then:

 The value of [Link] is the length of the movie, that is, the value
of the length attribute for the Movie object denoted by myMovie.
 The value of [Link]() is a real number, the length of the
movie in hours, computed by applying the method lengthInHours to
object myMovie.
 The value of [Link] is the set of Star objects related to themovie
myMovie by the relationship stars.
4. Let us ask for the names of the stars of Disney movies. Write the OQL that does the job,
eliminating duplicate names in the situation where a star appeared in several Disney
movies.

146
 Chapter - Eleven
Database Administration and Security
In today's society, information is a critical resource in not only the fields of industry, commerce,
education, or medicine, but also in the fields of military, diplomacy, or governments. Some
information is extremely important as to have to be protected. For example, data corruption or
fabrication in a hospital database could result in patients' receiving the wrong medication.
Disclosure or modification of military information could endanger national security.
Privacy – Ethical and legal rights that individuals have with regard to control over the
dissemination and use of their personal information
Database security – Protection of information contained in the database against unauthorized
access, modification or destruction
Database integrity – Mechanism that is applied to ensure that the data in the database is correct
and consistent
A good database security management system has not only the following characteristics: data
independence, shared access, minimal redundancy, data consistency, and data integrity but also
the following characteristics: privacy, integrity, and availability.
 Privacy signifies that an unauthorized user cannot disclose data
 Integrity ensures that an unauthorized user cannot modify data
 Availability ensures that data be made available to the authorized user unfailingly
 Copyright ensures the native rights of individuals as a creator of information.
 Validity ensures activities to be accountable by law.
With a strong enforcement and management of these, it is said that the database system can
effectively prevent accidental security and integrity threats from system error, improper
authorization and concurrent usage anomalies. In addition to have an efficient system, it should
have prevention on malicious or intentional security and integrity threats where computer system
operator can bypass security as well as programmers as hackers. There are certain security policy
issues that we should recognize, where we should consider administrative control policies,
decide which security features offered by the DBMS is used to implement the system, decide
whether the focus of security
administration is left with DBA and whether it is centralized or decentralized. Besides, one
should decide on ownership of shared data as well. When we talk about the levels of security

146
protection, it may start from organization & administrative security, physical & personnel
security, communication security and Information systems security Database security and
integrity is about protecting the database from being inconsistent and being disrupted. We can
also call it database misuse. Database misuse could be Intentional or Accidental, where
accidental misuse is easier to cope with than intentional misuse. Accidental inconsistency could
occur due to:
 System crash during transaction processing
 Anomalies due to concurrent access
 Anomalies due to redundancy
 Logical errors
Likewise, even though there are various threats that could be categorized in this group,
Intentional misuse could be:
 Unauthorized reading of data
 Unauthorized modification of data or
 Unauthorized destruction of data
Most systems implement good Database Integrity to protect the system from accidental misuse
while there are many computer based measures to protect the system from intentional misuse,
which is termed as Database Security measures. Levels of Security Measures Security
measures can be implemented at several levels and for different components of the system.
These levels are:
1. Physical Level: concerned with securing the site containing the computer system. The backup
systems should also be physically protected from access except for authorized users. In other
words, the site or sites containing the computer systems must be physically secured against
armed or sneaky entry by intruders.
2. Human Level: concerned with authorization of database users for access the content at
different levels and privileges.
3. Operating System: concerned with the weakness and strength of the operating system
security on data files. Weakness may serve as a means of unauthorized access to the database.
No matter how secure the database system is, weakness in operating system security may serve
as a means of unauthorized access to the database. This also includes protection of data in
primary and secondary memory from unauthorized access.

146
4. Database System: concerned with data access limit enforced by the database system. Access
limit like password, isolated transaction and etc. Some database system users may be authorized
to access only a limited portion of the database. Other users may be allowed to issues queries,
but may be forbidden to modify the data. It is the responsibility of the database system to ensure
that these authorization restrictions are not violated.
5. Application Level: Since almost all database systems allow remote access through terminals
or networks, software-level security with the network software is as important as physical
security, both on the Internet and networks private to an enterprise.
Even though we can have different levels of security and authorization on data objects and users,
who access which data is a policy matter rather than technical. These policies
 should be known by the system: should be encoded in the system
 should be remembered: should be saved somewhere (the catalogue)
Database Integrity constraints contribute to maintaining a secure database system by preventing
data from becoming invalid and hence giving misleading or incorrect results
Domain Integrity means that each column in any table will have set of allowed values and
cannot assume any value other than the one specified in the domain.
Entity Integrity means that in each table the primary key (which may be composite) satisfies
both of two conditions:
1. That the primary key is unique within the table and
2. That the primary key column(s) contains no null values.
Referential Integrity means that in the database as a whole, things are set up in such a way that if
a column exists in two or more tables in the database (typically as a primary key in one table and
as a foreign key in one or more other tables), then any change to a value in that column in any
one table will be reflected in corresponding changes to that value where it occurs in other
tables. This means that the RDBMS must be set up so as to take appropriate actions to spread a
change in one table from that table to the other tables where the change must also occur.
The effect of the existence and maintenance of referential integrity is, in short, that if a column
exists in two or more tables in the database, every occurrence of the column will contain only
values that are consistent across the database.
Key constraints in a relational database, there should be some collection of attributes with a
special feature used to maintain the integrity of the database. These attributes will be named as

146
Primary Key, Candidate Key, Foreign Key, and etc. These Key(s) should obey some rules set by
the relational data model.
Enterprise Constraint means some business rules set by the enterprise on how to use, manage
and control the database
Database Security - the mechanisms that protect the database against intentional or accidental
threats. Database security encompasses hardware, software, people and data.
Database Management Systems supporting multi-user database system must provide a database
security and authorization subsystem to enforce limits on individual and group access rights and
privileges.
11.1 Security Issues and general considerations
Legal, ethical and social issues regarding the right to access information
Physical control issues regarding how to keep the database physically secured.
Policy issues regarding privacy of individual level at enterprise and national level
Operational consideration on the techniques used (password, etc) to access and manipulate the
database
System level security including operating system and hardware control
Security levels and security policies in enterprise level
The designer and the administrator of a database should first identify the possible threat that
might be faced by the system in order to take counter measures.
Threat may be any situation or event, whether intentional or accidental, that may adversely
affect a system and consequently the organization
A threat may be caused by a situation or event involving a person, action, or circumstance that is
likely to bring harm to an organization
The harm to an organization may be tangible or intangible
Tangible – loss of hardware, software, or data
Intangible – loss of credibility or client confidence
Examples of threats:
Using another persons’ means of access
Unauthorized amendment/modification or copying of data
Program alteration
Inadequate policies and procedures that allow a mix of confidential and normal out put

146
Wire-tapping
Illegal entry by hacker
 Blackmail
 Theft of data, programs, and equipment
Failure of security mechanisms, giving greater access than normal
 Staff shortages or strikes
 Inadequate staff training
Viewing and disclosing unauthorized data
 Electronic interference and radiation
 Data corruption owing to power loss or surge
 Fire (electrical fault, lightning strike, arson), flood, bomb
 Physical damage to equipment
 Breaking cables or disconnection of cables
 Introduction of viruses
An organization deploying a database system needs to identify the types of threat it may be
subjected to and initiate appropriate plans and countermeasures, bearing in mind the costs of
implementing each.
Countermeasures: Computer Based Controls
The types of countermeasure to threats on computer systems range from physical controls to
administrative procedures
Despite the range of computer-based controls that are available, it is worth noting that, generally,
the security of a DBMS is only as good as that of the operating system, owing to their close
association
The following are computer-based security controls for a multi-user environment:
Authorization: The granting of a right or privilege that enables a subject to have legitimate
access to a system or a system‘s object
Authorization controls can be built into the software, and govern not only what system or object
a specified user can access, but also what the user may do with it
Authorization controls are sometimes referred to as access controls

146
The process of authorization involves authentication of subjects (i.e. a user or program)
requesting access to objects (i.e. a database table, view, procedure, trigger, or any other object
that can be created within the system)
Views: A view is the dynamic result of one or more relational operations operation on the base
relations to produce another relation.
A view is a virtual relation that does not actually exist in the database, but is produced upon
request by a particular user.
The view mechanism provides a powerful and flexible security mechanism by hiding parts of the
database from certain users.
Using a view is more restrictive than simply having certain privileges granted to a user on the
base relation(s)
Backup and recovery: Backup is the process of periodically taking a copy of the database and
log file (and possibly programs) on to offline storage media. A DBMS should provide backup
facilities to assist with the recovery of a database following failure. Database recovery is the
process of restoring the database to a correct state in the event of a failure.
Journaling is the process of keeping and maintaining a log file (or journal) of all changes made to
the database to enable recovery to be undertaken effectively in the event of a failure.
The advantage of journaling is that, in the event of a failure, the database can be recovered to its
last known consistent state using a backup copy of the database and the information contained in
the log file. If no journaling is enabled on a failed system, the only means of recovery is to
restore the database using the latest backup version of the database. However, without a log file,
any changes made after the last backup to the database will be lost
Integrity: Integrity constraints contribute to maintaining a secure database system by preventing
data from becoming invalid and hence giving misleading or incorrect results
 Domain Integrity: setting the allowed set of values
 Entity integrity: demanding Primary key values not to assume a NULL value
 Referential integrity: enforcing Foreign Key values to have a value that already exist in
the corresponding Candidate Key attribute(s) or be NULL.
 Key constraints: the rules the Relational Data Model has on different kinds of Key.
Encryption Authorization may not be sufficient to protect data in database systems, especially
when there is a situation where data should be moved from one location to the other using

146
network facilities. Encryption is used to protect information stored at a particular site or
transmitted between sites from being accessed by unauthorized users. Encryption is the encoding
of the data by a special algorithm that renders the data unreadable by any program without the
decryption key. It is not possible for encrypted data to be read unless the reader knows how to
decipher/decrypt the encrypted data. If a database system holds particularly sensitive data, it
may be deemed necessary to encode it as a precaution against possible external threats or
attempts to access it. The DBMS can access data after decoding it, although there is degradation
in performance because of the time taken to decode it. Encryption also protects data transmitted
over communication lines. To transmit data securely over insecure networks requires the use of a
Cryptosystem, which includes:
1. An encryption key to encrypt the data (plaintext)
2. An encryption algorithm that, with the encryption key, transforms the plaintext into cipher
text
3. A decryption key to decrypt the cipher text
4. A decryption algorithm that, with the decryption key, transforms the cipher text back into
plaintext Data encryption standard (DES) is an approach, which does both a substitution of
characters and a rearrangement of their order based on an encryption key.
Types of Cryptosystems
Cryptosystems can be categorized into two
1. Symmetric encryption – uses the same key for both encryption and decryption and relies on
safe communication lines for exchanging the key.
2. Asymmetric encryption – uses different keys for encryption and decryption e.g. RSA
Generally, symmetric algorithms are much faster to execute on a computer than those that are
asymmetric. In the contrary, asymmetric algorithms are more secure than symmetric algorithms.

11.2. RAID technology (Redundant Array of Independent Disks)

The hardware that the DBMS is running on must be fault-tolerant, meaning that the DBMS
should continue to operate even if one of the hardware components fails. This suggests having
redundant components that can be seamlessly integrated into the working system whenever there
is one or more component failures. The main hardware components that should be fault-tolerant
include disk drives, disk controllers, CPU, power supplies, and cooling fans. Disk drives are the

146
most vulnerable components with the shortest times between failures of any of the hardware
components.
RAID works on having a large disk array comprising an arrangement of several independent
disks that are organized to improve reliability and at same time increase performance
 Performance is increased through data striping
Data striping – the data is segmented into equal size partitions (the striping unit) which are
transparently distributed across multiple disks.

11.3. Security at different Levels of Data

Almost all RDBMSs provide security at different levels and formats of data. This includes:
1. Relation Level: permission to have access to a specific relation.
2. View Level: permission to data included in the view and not in the named relations
3. Hybrid (Relation/View): the case where only part of a single relation is made available to
users through View.
Any database access request will have the following three major components
2. Requested Operation: what kind of operation is requested by a specific query?
3. Requested Object: on which resource or data of the database is the operation sought to be
applied?
4. Requesting User: who is the user requesting the operation on the specified object?
The database should be able to check for all the three components before processing any request.
The checking is performed by the security subsystem of the DBMS.
Authentication
All users of the database will have different access levels and permission for different data
objects, and authentication is the process of checking whether the user is the one with the
privilege for the access level.
Is the process of checking the users are who they say they are.
Each user is given a unique identifier, which is used by the operating system to determine who
they are
Thus the system will check whether the user with a specific username and password is trying to
use the resource.

146
Associated with each identifier is a password, chosen by the user and known to the operation
system, which must be supplied to enable the operating system to authenticate who the user
claims to be.
Authorization/Privilege
Authorization refers to the process that determines the mode in which a particular (previously
authenticated) client is allowed to access a specific resource controlled by a server. Most of the
time, authorization is implemented by using Views.
Views are unnamed relations containing part of one or more base relations creating a
customized/personalized view for different users.
Views are used to hide data that a user needs not to see.
Forms of user authorization
There are different forms of user authorization on the resource of the database. These forms are
privileges on what operations are allowed on a specific data object. User authorization on the
data/extension
1. Read Authorization: the user with this privilege is allowed only to read the content of the
data object.
2. Insert Authorization: the user with this privilege is allowed only to insert new records or
items to the data object.
3. Update Authorization: users with this privilege are allowed to modify content of attributes
but are not authorized to delete the records.
4. Delete Authorization: users with this privilege are only allowed to delete a record and not
anything else.
Different users, depending on the power of the user, can have one or the combination of the
above forms of authorization on different data objects.
User authorization on the database schema
1. Index Authorization: deals with permission to create as well as delete an index table for
relation.
2. Resource Authorization: deals with permission to add/create a new relation in the database.
3. Alteration Authorization: deals with permission to add as well as delete attribute.
4. Drop Authorization: deals with permission to delete and existing relation.

146
11.4. Role of DBA in Database Security
The database administrator is responsible to make the database to be as secure as possible. For
this the DBA should have the most powerful privilege than every other user. The DBA provides
capability for database users while accessing the content of the database. The major
responsibilities of DBA in relation to authorization of users are:
1. Account Creation: involves creating different accounts for different USERS as well as USER
GROUPS.
2. Security Level Assignment: involves in assigning different users at different categories of
access levels.
3. Privilege Grant: involves giving different levels of privileges for different users and user
groups.
4. Privilege Revocation: involves denying or canceling previously granted privileges for users
due to various reasons.
5. Account Deletion: involves in deleting an existing account of users or user groups. Is similar
with denying all privileges of users on the database.

11.5. Approaches to Database Security

There are two broader approaches to security. The two types of database security mechanisms
are:
1. Discretionary security mechanisms
Grant different privileges to different users and user groups on various data objects
The privilege is to access different data objects
The mode of the privilege could be
 Read,
 Insert,
 Delete,
 Update files, records or fields.
 Is more flexible
 One user can have A but not B and another user can have B but not A
2. Mandatory security mechanisms
 Enforce multilevel security

146
  Classifying data and users into various security classes (or levels) and implementing the
appropriate security policy of the organization.
 Each data object will have certain classification level
 Each user is given certain clearance level
 Only users who can pass the clearance level can access the data object
 Is comparatively not-flexible/rigid
If one user can have A but not B then B is accessed by users with higher privilege and we cannot
have B but not A
The ability to classify user into a hierarchy of groups provide a powerful tool for administering
large systems with thousands of users and objects. A database system can support one or both of
the security mechanisms to protect the data. In most systems it is better to filter those that are
allowed rather than identifying the not allowed. Since if some object is authorized then it means
it is not constrained.

Review Exercise Eleven

Chapter 11

1. What are two type of cryptosystem?

2. What are the different approaches of database security?

146
 References
H. Garcia-Molina, J. D. Ullman, and J. Widom, “Database Systems: The Complete Book,” p.
570.
“Fundamentals of Database Systems, 7th Edition.” [Link]
com/one-dot-com/us/en/higher-education/[Link] (accessed Jun. 14, 2022).
R. Elmasri and S. Navathe, Fundamentals of database systems, 5th ed. Boston: Pearson/Addison
Wesley, 2007.
R. Elmasri and S. Navathe, Fundamentals of database systems, 6th ed. Boston: Addison-Wesley,
2011.
“DATABASE MANAGEMENT SYSTEMS SOLUTIONS MANUAL THIRD EDITION - PDF
Drive.” [Link]
[Link].
Database System Concepts 3/e. Abraham Sibcrschatz Heriy F Korth & S. Sudarshan, McGraw-
Hill,1997.
A First Course in Database Systems, Jeffrey Ullman & Jennifer Widom, Prentice-Hall, 1997.
Database System Implementation, Hector Garcia-Molina, Jeffrey Ullman & Jennifer Widom,
Prentice-Hall, 2000.
Readings in Database Systems, Michael Stonebraker & Joe Hellerstein, eds, Morgan-Kaufmann,
1998
Thomas M. Connolly and Carolyn [Link]. (2004). A step by step approach to building
databases, [Link] Education Limited.
David M. Kroenke. (1998). Database processing, 6th ed. Prentice Hall
Van der Lans (2006). Introduction to SQL, Mastering the relational database language. 3rd ed.
London, Addis Wesley
Silbershatz A. Korth H andSundarshan (2006). Database System concepts, 5th ed.
Boston, McGraw Hill
RamaKrishman(1998). Database Management Systems. Boston McGraw Hill
Namdagopalan (2003). Database Management Systems with oracle and [Link], Appa
Book house.
Date, .J (1981). An Introduction to Database systems. 3rd ed. Vol. 1. New Delhi. Narosa
publishing House

146
146