DBMS Module 2

Syllabus
Introduction to database Systems, advantages of database system over traditional
file system, Basic concepts & Definitions, Database users, Database Language,
Database System Architecture, Schemas, Sub Schemas, & Instances, database
constraints, 3-level database architecture, Data Abstraction, Data Independence,
Mappings, Structure, Components & functions of DBMS, Data models.

Entity relationship model, Components of ER model, Mapping E-R model to

Relational schema, Network and Object Oriented Data models. Relational Algebra,
Tuple & Domain Relational Calculus, Relational Query Languages: SQL and QBE.
Query processing and optimization: Evaluation of Relational Algebra Expressions,
Query optimization, Query cost estimation.

Database Design:-Database development life cycle (DDLC), Automated design tools,

Functional dependency and Decomposition, Join strategies, Dependency
Preservation & lossless Design, Normalization, Normal forms:1NF, 2NF,3NF, and
BCNF, Multi-valued Dependencies, 4NF & 5NF.

Transaction processing and concurrency control: Transaction concepts, properties of

transaction, concurrency control, locking and Timestamp methods for concurrency
control schemes. Database Recovery System, Types of Data Base failure & Types of
Database Recovery, Recovery techniques. Fundamental concepts of advanced
databases.
Storage Strategies: Detailed Storage Architecture, RAID

Entity-Relationship (ER) Model:

Definition:

The Entity-Relationship (ER) model is a conceptual data model used in database

design to represent the relationships between entities and their attributes in a
clear and graphical manner.

Key Components:

DBMS Module 2 1
1. Entity:

Represents a real-world object, concept, or thing with distinct properties.

Example: "Customer," "Product," or "Employee."

2. Relationship:

Describes how entities are related to each other.

Example: "Works for" relationship between "Employee" and "Department."

3. Attribute:

Describes a property or characteristic of an entity.

Example: "Name," "Age," or "Salary."

4. Key Attribute:

An attribute that uniquely identifies each instance of an entity.

Example: "EmployeeID" as the key attribute for the "Employee" entity.

5. Multivalued Attribute:

An attribute that can have multiple values for a single entity.

Example: "Phone Numbers" for a "Contact" entity.

6. Derived Attribute:

An attribute whose value is derived from other attributes.

Example: "Age" can be derived from the "Birthdate" attribute.

7. Weak Entity:

An entity that does not have a key attribute of its own and relies on the
parent entity for identification.

Example: "Dependent" entity in relation to "Employee."

8. Cardinality:

Describes the number of instances of one entity that can be related to the
number of instances in another entity.

Example: "One-to-Many" or "Many-to-Many" cardinality.

9. Participation Constraints:

DBMS Module 2 2
Specify whether the existence of an entity depends on its relationship with
another entity.

Example: "Total Participation" means every entity in the relationship must

participate.

10. Weak Relationship:

Describes a relationship where the existence of one entity depends on the

existence of another entity.

Example: The relationship between "Department" and "Employee" where a

department may have no employees.

Relational Algebra:
Definition:

Relational Algebra is a procedural query language that operates on relations

(tables) to retrieve desired information from a relational database.

Key Operations:

1. Selection (σ):

Selects rows from a relation that satisfy a specified condition.

Example: σAge>25 (Employee)

​

2. Projection (π):

Retrieves specific columns (attributes) from a relation.

Example: πN ame,S alary (Employee)

​

3. Union ( ∪):
Combines tuples from two relations, removing duplicates.

Example: R ∪S
4. Intersection (∩):

Retrieves tuples common to both relations.

Example: R ∩ S

5. Difference (-):

DBMS Module 2 3
Retrieves tuples from the first relation that are not in the second.

Example: R - S

6. Cartesian Product (×):

Combines all possible pairs of tuples from two relations.

Example: R × S

7. Join (⨝):

Combines tuples from two relations based on a specified condition.

Example: R ⨝_{R.A=S.A} S

Tuple Relational Calculus:

Definition:

Tuple Relational Calculus is a non-procedural query language that specifies the

desired information without detailing how to obtain it. It uses variables and logical
conditions.

Syntax:

{t | P(t)}

t: Tuple variable

P(t): Predicate or condition on the tuple variables

Example:

{ EmpID, Name | Employee(EmpID, Name, Age) ∧ Age > 25}

Domain Relational Calculus:
Definition:

Domain Relational Calculus is another non-procedural query language that

focuses on specifying the desired information using variables and conditions.

Syntax:

{t | ∃u, v, ... (P(t, u, v, ...))}

t: Tuple variable

u, v, ...: Other variables

P(t, u, v, ...): Predicate or condition involving the variables

DBMS Module 2 4
Example:

∃
{ Name | Age, Salary (Employee(EmpID, Name, Age, Salary) ∧ Age > 25 ∧
Salary > 50000)}

Key Differences:
1. Relational Algebra:

Procedural: Specifies how to obtain the desired result using a sequence of

operations.

Operations: Selection, Projection, Union, Intersection, Difference, Cartesian

Product, Join.

2. Tuple Relational Calculus:

Non-Procedural: Specifies the desired result without detailing the process.

Syntax: {t | P(t)} with logical conditions on tuple variables.

3. Domain Relational Calculus:

Non-Procedural: Similar to tuple calculus but introduces quantified

variables.

Syntax: {t | ∃u, v, ... (P(t, u, v, ...))} with quantified variables and logical
conditions.

Query Processing and Optimization:

1. Evaluation of Relational Algebra Expressions:

Parsing and Translation:

The query is initially parsed and translated into a relational algebra

expression, breaking it down into its fundamental operations.

Query Rewriting:

The system may perform transformations to rewrite the query into an

equivalent, more efficient form.

Optimization Rules:

Apply optimization rules to the relational algebra expression to minimize the

number of operations and improve efficiency.

DBMS Module 2 5
Plan Generation:

Generate different execution plans for the query based on the optimized
algebraic expressions.

Plan Selection:

Evaluate various plans and select the one with the least cost or the most
optimal execution strategy.

2. Query Optimization:

Cost-Based Optimization:

Evaluate the cost of executing different query plans based on factors like
access methods, join strategies, and index usage.

Statistics Collection:

Collect and maintain statistics about the database, such as the number of
tuples in a relation, to aid in cost estimation.

Index Selection:

Decide whether to use indexes for accessing data and, if so, which indexes
to use.

Join Order Optimization:

Determine the most efficient order in which to perform joins, considering the
cost associated with different join orders.

Materialized Views:

Explore the possibility of using precomputed materialized views to speed up

query processing.

3. Query Cost Estimation:

Cost Metrics:

Assign costs to different operations in the query plan, such as the cost of
reading a tuple, performing a join, or sorting data.

Cardinality Estimation:

Estimate the number of tuples that will be processed at each stage of the
query execution.

I/O and CPU Costs:

DBMS Module 2 6
Consider the I/O and CPU costs associated with accessing and processing
data, factoring in disk I/O, CPU processing time, and network costs.

Optimization Techniques:

Use mathematical models and optimization algorithms to minimize the

overall cost of query execution.

Feedback Mechanism:

Implement feedback mechanisms to adapt the optimization strategy based

on the actual performance observed during execution.

Dynamic Query Optimization:

In some systems, dynamically adjust the query execution plan based on

changing conditions, statistics, or resource availability.

Example Scenario:
Consider a complex SQL query involving multiple joins and aggregations. The
system goes through the following steps:

1. Parsing and Translation:

Translate the SQL query into a corresponding relational algebra expression.

2. Query Rewriting:

Apply transformation rules to simplify and optimize the relational algebra

expression.

3. Optimization Rules:

Use rules to reorder joins or select more efficient access methods.

4. Plan Generation:

Generate multiple execution plans based on the optimized expression.

5. Plan Selection:

Choose the plan with the lowest estimated cost by considering factors like
join order, index usage, and access methods.

6. Cost-Based Optimization:

Evaluate the cost of different plans based on statistics about the database,
such as the number of tuples and distribution of data.

7. Join Order Optimization:

DBMS Module 2 7
Determine the most efficient order for joining tables by estimating the cost of
different join orders.

8. Query Cost Estimation:

Assign costs to various operations in the query plan, considering I/O costs,
CPU costs, and cardinality estimation.

9. Feedback Mechanism:

If the actual execution deviates significantly from the estimated cost, adjust
the optimization strategy dynamically.

DBMS Module 2 8