Unit 1 (ER Modeling)

Entity Types in DBMS

1. Entity

o An object or thing in the real world that can be identified distinctly.

o Examples: Students, Employees, Products.

2. Entity Type

o A collection or set of entities that share the same attributes.

o Example: Student is an entity type, where individual students like John, Jane, etc., are
entities.

3. Attributes of an Entity Type

o Define properties of the entity.

o Example: For the Student entity type, attributes could be Name, Roll No, Age, Address.

4. Key Attributes

o Uniquely identify each entity within an entity type.

o Example: Roll No for the Student entity type.

5. Types of Entity:

o Strong Entity

▪ Can exist independently of other entities.

▪ Has a primary key.

▪ Example: Employee with attributes Emp_ID, Name, Dept.

o Weak Entity

▪ Depends on a strong entity for its existence.

▪ Does not have a primary key; instead, uses a foreign key combined with a partial
key.

▪ Example: Dependent related to Employee.

6. Entity Set

o A collection of entities of the same type.

o Example: All students in a database form a Student entity set.

7. Relationships with Entity Types

 o Entities are related to each other through relationships.

o Example: A Student entity can have a relationship with a Course entity via the Enrollment
relationship.

Entity Set in DBMS

1. Definition

o An entity set is a collection of entities of the same type that share the same attributes.

o Example: All students in a university form a "Student" entity set, where each student is
an individual entity.

2. Attributes of an Entity Set

o Each entity in the set has attributes that define its properties.

o Example: In the "Student" entity set, attributes might include Name, Roll No, Age, and
Department.

3. Key Characteristics

o Entity Set = Entity Type + Instances

▪ Entity Type: The schema or template (e.g., "Student").

▪ Instances: The actual data or objects (e.g., John, Roll No. 101).

o It is represented as a rectangle in an Entity-Relationship (ER) diagram.

4. Types of Entity Sets

o Strong Entity Set

▪ Contains entities that are independent and uniquely identifiable.

▪ Has a primary key.

▪ Example: Employee entity set with key Emp_ID.

o Weak Entity Set

▪ Contains entities that are dependent on another (strong) entity set.

▪ Does not have a primary key; uses a foreign key and a discriminator (partial
key).

▪ Example: Dependent entity set associated with Employee.

5. Representation in ER Diagram

o Strong Entity Set: Represented by a rectangle.

o Weak Entity Set: Represented by a double rectangle.

 6. Entity Set vs. Relationship Set

o Entity Set: Represents objects (e.g., Student, Teacher).

o Relationship Set: Represents associations between these objects (e.g., Enrollment,

Teaching).

Attributes in DBMS

1. Definition

o Attributes are properties or characteristics of an entity or a relationship.

o Example: For the Student entity, attributes include Name, Roll Number, and Age.

2. Types of Attributes

o Simple Attribute

▪ Cannot be divided further.

▪ Example: Age, Roll Number.

o Composite Attribute

▪ Can be divided into sub-parts.

▪ Example: Full Name can be divided into First Name and Last Name.

o Derived Attribute

▪ Can be derived from other attributes.

▪ Example: Age can be derived from the Date of Birth.

o Single-Valued Attribute

▪ Has a single value for each entity.

▪ Example: Roll Number.

o Multi-Valued Attribute

▪ Can have multiple values for a single entity.

▪ Example: Phone Numbers for an employee.

o Null Attribute

▪ May not have a value for certain entities.

▪ Example: Middle Name might be null for some individuals.

3. Representation in ER Diagrams

o Attributes are represented as ellipses connected to their entity or relationship.

Keys in DBMS

1. Definition

o A key is an attribute (or a set of attributes) used to uniquely identify a tuple (row) in a
relation (table).

2. Types of Keys

o Super Key

▪ A set of attributes that can uniquely identify a tuple in a table.

▪ Example: {Roll Number, Email} in a Student table.

o Candidate Key

▪ A minimal super key (no proper subset can uniquely identify tuples).

▪ Example: Roll Number in a Student table.

o Primary Key

▪ A candidate key chosen to uniquely identify tuples in a table.

▪ Cannot have null values.

▪ Example: Roll Number.

o Alternate Key

▪ Candidate keys not chosen as the primary key.

▪ Example: If Roll Number is the primary key, Email could be an alternate key.

o Foreign Key

▪ An attribute in one table that refers to the primary key in another table.

▪ Example: Course_ID in an Enrollment table referencing Course_ID in the Course

table.

o Composite Key

▪ A primary key consisting of two or more attributes.

▪ Example: (Student_ID, Course_ID) in an Enrollment table.

o Unique Key

▪ Ensures all values in a column are unique but allows null values.

▪ Example: Employee Email in an Employee table.

Attributes vs. Keys

Aspect Attributes Keys

Definition Properties of entities/relationships Identify rows in tables uniquely

Representation Ellipses in ER diagrams Underlined in table schema or ER diagrams

Examples Name, Age, Email Primary Key, Candidate Key

Relationships in DBMS

1. Definition

o A relationship is an association or link between two or more entities.

o Example: A Student enrolls in a Course.

2. Representation in ER Diagrams

o Represented as a diamond shape connecting the related entities.

3. Components of a Relationship

o Entities: The objects participating in the relationship.

o Attributes: Properties of the relationship (optional).

▪ Example: Date of Enrollment can be an attribute of the Enrolls relationship.

o Cardinality: Describes the number of entities participating in a relationship.

4. Degree of a Relationship

o Indicates the number of entities involved:

▪ Unary Relationship (1 entity): Self-referential. Example: Employee supervises

Employee.

▪ Binary Relationship (2 entities): Most common type. Example: Student enrolls in

Course.

▪ Ternary Relationship (3 entities): Example: Supplier supplies Product to

Warehouse.

Relationship Types in DBMS

1. Based on Cardinality
 o One-to-One (1:1)

▪ Each entity in one set is related to at most one entity in another set.

▪ Example: Each Person has one Passport.

o One-to-Many (1

▪ One entity in the first set is related to multiple entities in the second set.

▪ Example: A Teacher teaches multiple Students.

o Many-to-Many (M

▪ Many entities in one set are related to many entities in another set.

▪ Example: Students enroll in multiple Courses, and each Course has multiple
Students.

2. Based on Participation

o Total Participation

▪ All entities in an entity set participate in the relationship.

▪ Example: All Employees are assigned to a Department.

o Partial Participation

▪ Some entities in an entity set participate in the relationship.

▪ Example: Some Employees may manage Projects.

3. Identifying vs. Non-Identifying Relationships

o Identifying Relationship

▪ A relationship where a weak entity depends on a strong entity for its identity.

▪ Example: A Dependent depends on an Employee.

o Non-Identifying Relationship

▪ A relationship between strong entities.

▪ Example: Student enrolls in a Course.

4. Recursive Relationship

o An entity is related to itself in a relationship.

o Example: Employee supervises another Employee.

Relationships vs. Relations

Aspect Relationships Relations

Definition Association between entities A table in a relational database

Representation Diamond in ER diagrams Rows and columns in a relational table

Example Student enrolls in Course A table with columns like Student_ID, Course_ID

Roles in DBMS

1. Definition

o Roles refer to the function or part played by entities in a relationship.

o Example: In the relationship Teaches, the roles are:

▪ Teacher: teaches the course.

▪ Course: is taught by the teacher.

2. Types of Roles

o Explicit Roles

▪ Clearly defined in the relationship for clarity.

▪ Example: In a Marriage relationship, roles are Husband and Wife.

o Implicit Roles

▪ Assumed without explicit labeling if roles are obvious.

▪ Example: In Enrolled, it is assumed that Student and Course are roles.

3. Recursive Relationships and Roles

o A single entity participates in a relationship with itself.

o Roles become crucial to differentiate the function of each instance.

o Example: In the Supervision relationship of an Employee entity:

▪ Role 1: Supervisor.

▪ Role 2: Subordinate.

Structural Constraints in DBMS

 1. Definition

o Structural constraints define the rules or restrictions on how entities can participate in a
relationship.

o Two key structural constraints are:

▪ Cardinality

▪ Participation

1. Cardinality

• Specifies the number of instances of one entity that can or must be associated with instances of
another entity.

• Types of Cardinality:

o One-to-One (1:1)

▪ One entity instance is related to at most one instance of another entity.

▪ Example: Each Person has one Passport.

o One-to-Many (1

▪ One entity instance is related to multiple instances of another entity.

▪ Example: A Teacher teaches multiple Students.

o Many-to-Many (M

▪ Multiple instances of one entity are related to multiple instances of another.

▪ Example: Students enroll in multiple Courses, and each Course has multiple
Students.

2. Participation

• Describes the extent to which entities in an entity set participate in a relationship.

• Types of Participation:

o Total Participation

▪ All instances of the entity must participate in the relationship.

▪ Represented by a double line in ER diagrams.

 ▪ Example: All Employees must belong to a Department.

o Partial Participation

▪ Only some instances of the entity participate in the relationship.

▪ Represented by a single line in ER diagrams.

▪ Example: Not all Employees manage Projects.

Combining Roles and Structural Constraints

• Example: Employee and Department Relationship

o Relationship: Works_For.

o Roles:

▪ Employee: works for a department.

▪ Department: employs employees.

o Structural Constraints:

▪ Cardinality: An employee works for exactly one department (1:1 or 1

).

▪ Participation: All employees must belong to a department (Total Participation).

Key Differences

Aspect Roles Structural Constraints

Defines the part played by entities in a Defines restrictions on entity

Definition
relationship. participation.

Focus Function of entities in the relationship. Cardinality and participation rules.

1
Example Teacher and Course in Teaches
relationship with total participation.

Weak Entities in DBMS

Definition
 • A weak entity is an entity type that cannot be uniquely identified by its attributes alone.

• It depends on a strong (owner) entity for its identification.

• Example: A Dependent entity (e.g., child) relies on an Employee entity (e.g., parent).

Characteristics of Weak Entities

1. Lack of a Primary Key

o Weak entities do not have a primary key of their own.

o They are identified using a partial key along with a foreign key from a related strong
entity.

2. Dependent on a Strong Entity

o Every weak entity must be associated with a strong entity.

o Example: A Dependent must be associated with an Employee.

3. Existence Dependency

o A weak entity cannot exist without its associated strong entity.

o Example: A Dependent cannot exist without a corresponding Employee.

4. Participation Constraint

o Weak entities have total participation in the relationship with the strong entity.

o This means every weak entity must be linked to at least one strong entity.

5. Partial Key (Discriminator)

o An attribute or set of attributes in a weak entity that uniquely identifies it within the
context of a strong entity.

o Example: Dependent_Name can uniquely identify dependents of a specific Employee.

Representation in ER Diagram

• Weak Entity: Represented by a double rectangle.

• Identifying Relationship:

o Links the weak entity to the strong entity.

o Represented by a double diamond.

• Primary Key:
 o Combination of the partial key and the primary key of the strong entity.

Example of Weak Entity

1. Scenario:

o Employee (strong entity) has dependents (Dependent, weak entity).

2. Attributes:

o Employee: Employee_ID (Primary Key), Name, Department.

o Dependent: Dependent_Name (Partial Key), Age, Relationship.

3. Relationship:

o Has_Dependent: Identifying relationship between Employee and Dependent.

4. Primary Key for Weak Entity:

o Dependent: {Employee_ID + Dependent_Name}.

Key Differences Between Strong and Weak Entities

Aspect Strong Entity Weak Entity

Primary Key Has a unique primary key. Does not have a primary key of its own.

Dependency Independent of other entities. Dependent on a strong entity.

Participation Can have partial or total participation. Always has total participation.

ER Diagram Represented by a single rectangle. Represented by a double rectangle.

Enhanced ER Model (EER) and Object Modeling in DBMS

Enhanced ER Model (EER)

The Enhanced ER Model (EER) extends the basic Entity-Relationship (ER) model by incorporating more
advanced concepts to represent complex data relationships.

Key Features of EER

1. Specialization and Generalization

 o Specialization:

▪ Process of creating sub-classes (sub-entities) from a super-class (general entity).

▪ Example: A Person entity can be specialized into Student and Employee.

o Generalization:

▪ Process of merging two or more sub-entities into a single generalized entity.

▪ Example: Car and Truck can be generalized into Vehicle.

o Representation:

▪ Represented in ER diagrams using a triangle.

2. Inheritance

o Subclasses inherit attributes and relationships from their superclass.

o Example: A Student inherits Name and Address from the Person entity.

3. Categories (Union Types)

o Combines entities from different entity sets into a single subclass.

o Example: Part-Time Staff can be a union of Students and Teachers.

4. Aggregation

o Represents a relationship as a higher-level entity.

o Useful when a relationship needs to participate in another relationship.

o Example: Loan is a relationship between Bank and Customer, and it can participate in
another relationship, Approval, with an Employee.

5. Participation Constraints and Cardinality

o Allows precise representation of participation (total or partial) and cardinality (1:1, 1

,M

) in relationships.

Representation in EER Diagrams

EER diagrams extend ER diagrams by including:

• Triangles for specialization/generalization.

• Double rectangles for categories.

• Diamonds within diamonds for aggregation.

Object Modeling in DBMS

Object modeling in DBMS is based on the Object-Oriented Data Model, which combines the principles
of object-oriented programming with database design.

Key Concepts of Object Modeling

1. Objects

o An object represents a real-world entity, combining data (attributes) and behavior

(methods).

o Example: A Student object has attributes (Name, Roll No) and methods
(CalculateGrade()).

2. Classes

o A class is a blueprint for objects, defining attributes and methods.

o Example: Class Student can have attributes (Name, Roll No) and methods (Enroll(),
Drop()).

3. Inheritance

o Allows one class (subclass) to inherit properties and methods from another (superclass).

o Example: A GraduateStudent class inherits from the Student class.

4. Encapsulation

o Combines attributes and methods within a single unit (object), hiding implementation
details from the user.

5. Polymorphism

o Enables the same method to perform different operations based on the object calling it.

o Example: A method CalculateSalary() can behave differently for Manager and Employee
objects.

6. Relationships in Object Modeling

o Association: Represents links between objects.

▪ Example: A Student is associated with a Course.

o Aggregation: A whole-part relationship where parts can exist independently.

▪ Example: A Department has multiple Professors.

o Composition: A whole-part relationship where parts cannot exist independently.

 ▪ Example: A Car consists of Engine and Wheels.

Advantages of Object Modeling

• Represents complex data relationships naturally.

• Facilitates reuse through inheritance and polymorphism.

• Bridges the gap between real-world concepts and database design.

Comparison Between EER and Object Modeling

Aspect Enhanced ER Model (EER) Object Modeling

Advanced representation of entities and Combines data and behavior in a single

Focus
relationships. unit.

Specialization, generalization, Classes, objects, inheritance,

Core Concepts
aggregation. encapsulation.

Representation EER diagrams. Object-oriented diagrams (UML, etc.).

Object-oriented databases or object-

Use Case Extending relational databases.
relational mapping.

Subclasses and Superclasses in DBMS

Definition

1. Superclass:

o A generalized entity that represents common attributes and relationships shared by its
subclasses.

o Example: Person is a superclass with attributes like Name and Address.

2. Subclass:

o A specialized entity that inherits attributes and relationships from a superclass while
introducing additional attributes or relationships.

o Example: Student and Employee are subclasses of Person.

Key Concepts

1. Generalization and Specialization

o Generalization:

▪ Combining two or more similar subclasses into a superclass.

▪ Example: Car and Truck can be generalized into Vehicle.

o Specialization:

▪ Dividing a superclass into two or more subclasses based on specific

characteristics.

▪ Example: Person can be specialized into Student and Employee.

2. Inheritance

o Subclasses inherit attributes and relationships from the superclass.

o Example: If Person has attributes Name and Address, then Student (a subclass) also has
these attributes.

3. Attributes in Subclasses

o Subclasses can have additional attributes or relationships.

o Example: Student may have Roll Number, while Employee may have Employee ID.

Constraints on Subclasses and Superclasses

1. Disjoint vs. Overlapping Subclasses

o Disjoint:

▪ An entity instance of the superclass can belong to only one subclass.

▪ Example: A Person can be either a Student or an Employee, but not both.

o Overlapping:

▪ An entity instance of the superclass can belong to more than one subclass.

▪ Example: A Person can be both a Student and an Employee.

2. Completeness Constraints

o Total Specialization:

▪ Every entity in the superclass must belong to at least one subclass.

▪ Example: Every Person is either a Student or an Employee.

 ▪ Represented by a double line in an EER diagram.

o Partial Specialization:

▪ Some entities in the superclass do not belong to any subclass.

▪ Example: Some Persons may not be Students or Employees.

▪ Represented by a single line in an EER diagram.

Representation in EER Diagrams

• Superclass: Represented as a rectangle.

• Subclass: Represented as rectangles connected to the superclass with a triangle indicating

generalization or specialization.

• Constraints:

o Disjoint subclasses are labeled d.

o Overlapping subclasses are labeled o.

Example: Superclass and Subclass

1. Scenario

o Person is a superclass with attributes: Person_ID, Name, and Address.

o Subclasses:

▪ Student: Attributes: Roll Number, Course.

▪ Employee: Attributes: Employee ID, Department.

2. Specialization Constraints

o Disjoint: A Person can either be a Student or an Employee.

3. ER Diagram Representation

o A rectangle labeled Person (superclass).

o Two triangles connect Person to Student and Employee (subclasses).

o d is placed in the triangle to indicate disjoint specialization.

Applications

• In Databases:
 o Allows more efficient organization of data by representing hierarchical relationships.

o Example: Separating customers into Corporate and Individual types in a CRM database.

• In Object-Oriented Systems:

o Forms the basis for inheritance in object-oriented design.

Unit 2 (File Organization)

Indexed Sequential Access File (ISAM) in DBMS

Definition

Indexed Sequential Access Method (ISAM) is a file organization technique that combines the advantages
of both sequential access and indexing to provide efficient access to data in a file. In ISAM, the data is
stored sequentially, and an index is maintained to provide faster access to records.

Key Characteristics of ISAM

1. Sequential File Organization

o Data records are stored sequentially in a file according to a specific key attribute.

o For example, records in an employee file might be sorted based on Employee ID.

2. Indexing

o An index file is created, which contains keys and pointers to the actual data records.

o The index allows for direct access to the data without needing to scan through the entire
file sequentially.

3. Combination of Sequential and Random Access

o Sequential access is used for operations like scanning the entire file.

o Indexed access allows for quick retrieval of records without scanning the entire file,
improving performance for searches.

Structure of ISAM

1. Data File

o Contains the actual records, which are stored in sorted order based on a key field.

o The file is divided into fixed-length blocks or pages.

2. Index File
 o Contains an ordered list of key values and corresponding pointers to the data file.

o It helps to locate the position of data records quickly.

o Primary Index: Directly indexes the records using the key field.

o Secondary Index: Provides additional indexing on non-primary fields (optional).

3. Overflow Area

o In ISAM, an overflow area is used when new records cannot fit into the predefined slots
of the index or data file due to insertions or deletions.

o This area stores records that don’t fit into the sequential structure.

Working of Indexed Sequential Access Method (ISAM)

1. Insertion

o When a new record is inserted, it is added in the appropriate sorted order in the data
file.

o If there is no space in the index, it might require a reorganization of the index and data
files.

2. Search

o To search for a record, the system looks up the index for the key value and retrieves the
corresponding pointer to the data file.

o The pointer directs the system to the exact location of the record in the data file.

3. Deletion and Update

o When a record is deleted or updated, it might require the reorganization of the file to
maintain the sequential order and integrity of the index.

4. Overflow Handling

o When the data file becomes full, the new records that don't fit are stored in an overflow
area.

o Overflow records are linked to the main file or index, and a pointer is used to access
them.

Advantages of ISAM

1. Fast Access

o Provides faster retrieval of records compared to purely sequential files by using indexes.
 2. Efficient for Range Queries

o Because the records are sorted and indexed, it is efficient for range-based queries,
where you need to find records that fall within a specific range of key values.

3. Supports Both Sequential and Direct Access

o It allows for sequential scanning of the file and direct access to individual records via
the index, combining the advantages of both methods.

Disadvantages of ISAM

1. Reorganization Overhead

o The need to reorganize the file (rebuilding the index and data file) when records are
inserted or deleted can be costly and time-consuming, especially when the file grows
large.

2. Fixed Size Limitations

o ISAM files are typically designed with fixed-size blocks and indexes. This can lead to
overflow issues when the number of records exceeds the capacity of the file or index
structure.

3. Inefficiency with Heavy Insertions/Deletions

o If there are frequent insertions and deletions, ISAM may become inefficient due to the
overhead of reorganization and handling overflow areas.

ISAM vs. Other File Access Methods

Aspect ISAM Heap File B+ Tree

Sequential with index and

File Structure Unordered storage Balanced tree structure
overflow

Fast for search and range Slow for search and range Fast for search and range
Access Speed
queries queries queries

Requires reorganization No reorganization Efficient with inserts and

Insertion/Deletion
occasionally required deletes

Uses primary and secondary Uses balanced index for

Indexing No indexing
indexes quick access

Applications of ISAM
 • Transaction Processing Systems: ISAM is well-suited for systems where there is a mix of
sequential processing and direct access, such as bank account records or inventory systems.

• Data Warehousing: When efficient retrieval and range queries are required, ISAM is often used
for storing and accessing large volumes of data.

Implementation of B and B+ Trees in DBMS

In a Database Management System (DBMS), both B-trees and B+ trees are commonly used for indexing
because they offer efficient search, insertion, and deletion operations. These trees are balanced,
meaning they maintain a structure that ensures logarithmic access time for all operations, which is
crucial for database indexing.

B-Tree

A B-tree is a self-balancing search tree data structure that maintains sorted data and allows for efficient
insertion, deletion, and search operations. It is generalized to allow more than two children per node.

Properties of B-Tree

1. Balanced:

o All leaf nodes are at the same level.

2. Nodes:

o Each node contains multiple keys, and each key is associated with a pointer to a child
node.

o The number of keys in each node is between a defined minimum and maximum number
of keys (based on the order of the tree).

3. Order:

o The order of a B-tree defines the maximum number of children a node can have. For
example, a B-tree of order m can have at most m-1 keys and m children in each node.

4. Key Property:

o Keys within each node are sorted in non-decreasing order.

5. Searching:

o Searching in a B-tree involves traversing the tree from the root to the leaf, comparing
keys at each node to determine which child pointer to follow.

B-Tree Operations
 1. Search:

o Start from the root node and search through the keys in each node.

o If the key is less than the first key, follow the left child; if greater than the first key but
less than the second key, follow the middle child, and so on.

2. Insertion:

o Insert a key in the appropriate leaf node.

o If the node is full, split the node into two, and push the middle key to the parent node.

3. Deletion:

o Delete the key from the appropriate node.

o If the node has fewer than the minimum required keys after deletion, borrow a key from
a sibling or merge nodes.

B-Tree Example (Order 3)

• A B-tree of order 3 can have a maximum of 2 keys and 3 children per node.

• The nodes can be organized as:

css

Copy code

[17, 28]

/ | \

[5, 9] [18, 23] [30, 35]

B+ Tree

A B+ Tree is a variation of the B-tree where all leaf nodes are linked in a linked list to facilitate range
queries. It maintains the structure of the B-tree but has some differences in how it stores data.

Properties of B+ Tree

1. Leaf Nodes Store Data:

o In a B+ Tree, only the leaf nodes contain the actual data records (or pointers to the
data). Internal nodes only store keys to guide the search.

2. All Leaf Nodes are Linked:

o Leaf nodes are linked in a doubly linked list, allowing efficient range queries.
 3. Sorted Data:

o Just like in B-trees, the keys in both the internal and leaf nodes are sorted.

4. Search Efficiency:

o The search operation is similar to that of a B-tree, but in B+ trees, since the leaf nodes
are linked, range queries can traverse the leaf nodes directly.

B+ Tree Operations

1. Search:

o The search in a B+ tree starts like a B-tree but follows the internal nodes to find the
appropriate leaf node.

2. Insertion:

o Similar to B-trees, insert the key into the appropriate leaf node. If the node is full, it
splits and the middle key is pushed up to the parent node.

3. Deletion:

o Deletion follows the same procedure as B-trees. If a node falls below the minimum
number of keys, borrowing or merging happens.

B+ Tree Example

Consider a B+ Tree of order 3 with a maximum of 2 keys per internal node and 2 keys per leaf node. The
structure might look like:

css

Copy code

[10]

/ \

[5, 7] [12, 15]

/ | \

[1, 2] [8] [11, 13]

• Internal nodes contain only keys: [10].

• Leaf nodes contain data or references to data: [1, 2], [8], [11, 13].
Implementation of B-Tree and B+ Tree

Below is a simple implementation outline for both B-tree and B+ tree operations.

B-Tree Implementation (Order m)

python

Copy code

class BTreeNode:

def __init__(self, is_leaf):

self.is_leaf = is_leaf

self.keys = []

self.children = []

class BTree:

def __init__(self, order):

self.order = order

self.root = BTreeNode(True)

# Insert key into BTree

def insert(self, key):

root = self.root

if len(root.keys) == self.order - 1: # Split root if full

new_node = BTreeNode(False)

new_node.children.append(self.root)

self.split(new_node, 0)

self.root = new_node

self.insert_non_full(self.root, key)

# Insert key into non-full node

def insert_non_full(self, node, key):

 if node.is_leaf:

node.keys.append(key)

node.keys.sort()

else:

i = len(node.keys) - 1

while i >= 0 and key < node.keys[i]:

i -= 1

self.insert_non_full(node.children[i + 1], key)

# Split a full node

def split(self, parent, index):

full_node = parent.children[index]

new_node = BTreeNode(full_node.is_leaf)

mid = len(full_node.keys) // 2

parent.keys.insert(index, full_node.keys[mid])

parent.children.insert(index + 1, new_node)

# Move keys and children to the new node

new_node.keys = full_node.keys[mid + 1:]

full_node.keys = full_node.keys[:mid]

if not full_node.is_leaf:

new_node.children = full_node.children[mid + 1:]

full_node.children = full_node.children[:mid + 1]

B+ Tree Implementation

python

Copy code

class BPlusTreeNode:
 def __init__(self, is_leaf):

self.is_leaf = is_leaf

self.keys = []

self.children = []

class BPlusTree:

def __init__(self, order):

self.order = order

self.root = BPlusTreeNode(True)

# Insert a key in the B+ Tree

def insert(self, key):

root = self.root

if len(root.keys) == self.order - 1: # Split root if full

new_node = BPlusTreeNode(False)

new_node.children.append(self.root)

self.split(new_node, 0)

self.root = new_node

self.insert_non_full(self.root, key)

# Insert key into non-full node

def insert_non_full(self, node, key):

if node.is_leaf:

node.keys.append(key)

node.keys.sort()

else:

i = len(node.keys) - 1

while i >= 0 and key < node.keys[i]:

i -= 1
 self.insert_non_full(node.children[i + 1], key)

# Split a full node

def split(self, parent, index):

full_node = parent.children[index]

new_node = BPlusTreeNode(full_node.is_leaf)

mid = len(full_node.keys) // 2

parent.keys.insert(index, full_node.keys[mid])

parent.children.insert(index + 1, new_node)

# Move keys and children to the new node

new_node.keys = full_node.keys[mid + 1:]

full_node.keys = full_node.keys[:mid]

Conclusion

• B-trees are widely used for general-purpose indexing because of their balanced structure and
efficient search, insertion, and deletion.

• B+ trees are often preferred when range queries are important, as they store all data in the leaf
nodes, which are linked together.

These trees ensure that the database can scale efficiently, providing fast query performance even with
large datasets.

Hashing and Hash Function in DBMS

What is Hashing?

Hashing is a technique used in databases and other applications to quickly access data in a large set by
using a hash function. The goal of hashing is to map data of arbitrary size (like a string or a record) to a
fixed-size value (called a hash value or hash code). Hashing is used to facilitate constant-time retrieval of
data, typically in hash tables.

In DBMS, hashing is primarily used in indexing methods and file organization to ensure that data
retrieval operations are fast, especially when the dataset is large.
Hash Function

A hash function is a mathematical algorithm that takes an input (or key) and converts it into a fixed-size
output called the hash value or hash code. The hash function's goal is to distribute the keys uniformly
across the hash table, minimizing the number of collisions.

Properties of a Good Hash Function:

1. Deterministic:

o For the same input, a hash function must always return the same hash value.

2. Uniform Distribution:

o A good hash function ensures that keys are distributed uniformly across the hash table
to minimize collisions.

3. Efficiency:

o The hash function should be computationally efficient, meaning it should quickly map
the input to the hash value.

4. Minimize Collisions:

o A collision occurs when two different keys produce the same hash value. The hash
function should minimize the likelihood of collisions.

5. Fixed Output Size:

o The output of the hash function should always be of a fixed size, regardless of the size of
the input.

Hashing Techniques in DBMS

There are two common methods used for hashing in DBMS: Static Hashing and Dynamic Hashing.

1. Static Hashing

In static hashing, the size of the hash table is fixed, and the hash function directly maps a key to a bucket
in the table.

Steps in Static Hashing:

1. Hash function: The hash function h(k) maps the key k to an integer value, which determines the
bucket number where the record is stored.

2. Buckets: A bucket is a data structure (often a linked list or an array) where records with the same
hash value are stored.

3. Overflow Handling:
 o Overflow occurs when a bucket is full. One common approach to handle overflow is
chaining, where each bucket holds a linked list of records that hash to the same value.

o Open addressing is another method for resolving collisions, where the next available
bucket is used.

Example of Static Hashing:

Suppose we have a hash table of size 10, and we want to insert a key k. The hash function h(k) = k % 10
determines the bucket location.

• For k = 42, the bucket will be h(42) = 42 % 10 = 2, so it will be inserted in bucket 2.

• For k = 25, the bucket will be h(25) = 25 % 10 = 5, so it will be inserted in bucket 5.

Drawback of Static Hashing:

• The fixed size of the hash table means that if there are too many records or if keys are not
uniformly distributed, the table will suffer from overflows or high load factors, making
operations slower.

2. Dynamic Hashing

Dynamic hashing is an extension of static hashing that allows the hash table to grow or shrink as
needed, maintaining efficient performance as the database size changes. This technique addresses the
limitations of static hashing by resizing the hash table dynamically.

Steps in Dynamic Hashing:

1. Extendible Hashing:
This method involves a directory of hash buckets, which dynamically adjusts its size as more
buckets are needed. The hash function is applied to the key, and a global depth is used to decide
the number of bits used for the hash value.

2. Buckets and Directory:

o The directory holds pointers to buckets that contain the actual data records. The
directory size grows as needed.

o Each bucket has a local depth, and the global depth indicates the number of bits from
the hash value used for indexing.

3. Splitting and Merging:

When a bucket overflows, the bucket is split into two, and the global or local depth is increased.
If a bucket becomes empty, it can be merged with another.

Example of Dynamic Hashing:

• Suppose a hash table with a global depth of 2 (2 bits are used from the hash value) and 4
buckets. The hash function is h(k) = k % 4 initially.
 • When the table grows, the global depth increases, and more bits are considered for the hash
function, expanding the number of available buckets.

Collision Handling in Hashing

Since it's not always possible to have a perfect hash function, collisions (when two keys map to the same
bucket) are inevitable. Common methods for handling collisions are:

1. Chaining:

o Each bucket is implemented as a linked list, and all records that hash to the same bucket
are stored in the list. The linked list helps to store multiple records in the same bucket.

o Pros: Easy to implement, and no need to worry about the size of the table.

o Cons: Can degrade performance if the linked list becomes long.

2. Open Addressing:

o When a collision occurs, the hash table looks for the next available slot (bucket).
Common techniques for open addressing include:

▪ Linear Probing: If a collision occurs, check the next available bucket in a linear
fashion.

▪ Quadratic Probing: Similar to linear probing but with a quadratic step size (e.g.,
check 1, 4, 9, ... positions).

▪ Double Hashing: Uses a second hash function to compute the next available
position.

o Pros: No extra memory for linked lists.

o Cons: Can suffer from clustering (when adjacent buckets fill up).

Applications of Hashing in DBMS

1. Indexing:
Hashing is used to build hash indexes, where a hash function is applied to the key to quickly
locate records in the database.

2. Partitioning:
Hashing is used for data partitioning in distributed databases. The hash function maps records
to different partitions or nodes, allowing parallel processing and storage.

3. Caching:
Hashing is used in caching to store frequently accessed data in a hash table, ensuring fast
retrieval.
 4. Encryption:
Hash functions are widely used in cryptographic systems for creating secure hash values (e.g.,
MD5, SHA-256).

Example of Hash Function:

Consider a simple hash function for strings:

less

Copy code

hash("apple") = (ASCII("a") + ASCII("p") + ASCII("p") + ASCII("l") + ASCII("e")) % table_size

For a hash table of size 10:

scss

Copy code

hash("apple") = (97 + 112 + 112 + 108 + 101) % 10 = 530 % 10 = 0

So, the key "apple" would be stored in bucket 0.

Collision Resolution in Hashing

Collision resolution is a critical aspect of hashing, especially in situations where multiple keys hash to the
same index (bucket) in a hash table. This can happen because the hash function does not guarantee
unique hash codes for each possible key, so multiple keys may map to the same hash value (bucket).

In DBMS and other applications that use hash tables, resolving collisions efficiently is key to maintaining
the performance of hash-based operations like insert, search, and delete.

There are two primary techniques for handling collisions: Open Addressing and Chaining.

1. Chaining (External Collision Resolution)

In chaining, each bucket in the hash table stores a linked list (or another data structure) of all the keys
that hash to the same index. Instead of storing just one key per bucket, each bucket stores a linked list of
keys (or even complete records).

How Chaining Works:

• If two or more keys hash to the same bucket, they are inserted into the linked list at that bucket.

• The linked list allows the bucket to hold multiple keys, which is useful in cases where collisions
are frequent.

Pros:
 • Easy to implement.

• It allows the hash table to handle an arbitrary number of collisions.

• It is flexible, as the size of the linked list can grow dynamically.

Cons:

• It requires additional memory to store the linked lists.

• Performance can degrade if too many keys hash to the same bucket (linked lists become long),
leading to slower operations.

Example of Chaining:

Suppose we have a hash table of size 5 with the hash function h(k) = k % 5. Let's insert keys 10, 15, and
20:

yaml

Copy code

Table:

Bucket 0: [10 -> 15 -> 20]

Bucket 1: []

Bucket 2: []

Bucket 3: []

Bucket 4: []

In this case, h(10) = 0, h(15) = 0, and h(20) = 0. All three keys end up in the same bucket (bucket 0), and
they are stored as a linked list.

2. Open Addressing (Internal Collision Resolution)

In open addressing, instead of using linked lists to store colliding elements, the hash table itself is used
to store all keys. When a collision occurs, the algorithm searches for another open slot within the hash
table, using a probing strategy to find the next available bucket.

Open addressing is typically used with hash tables that have fixed size.

There are several types of open addressing:

Types of Open Addressing

1. Linear Probing

In linear probing, when a collision occurs at the hash index i, the algorithm checks the next slot i + 1. If
that slot is also occupied, it checks i + 2, and so on, until an empty slot is found.
Formula:
h(k, i) = (h(k) + i) % table_size

Where i is the probe number (starting from 0).

Pros:

o Easy to implement.

o Works well for small tables.

Cons:

o Clustering: This is when consecutive slots fill up, leading to primary clustering (adjacent
keys clustering in the same part of the table) and reducing the efficiency of lookups.

Example of Linear Probing:

For a table of size 5 and a hash function h(k) = k % 5, let's insert keys 10, 15, and 20:

o h(10) = 0, so 10 is placed in bucket 0.

o h(15) = 0, but bucket 0 is occupied, so linear probing finds the next available bucket
(bucket 1).

o h(20) = 0, but buckets 0 and 1 are occupied, so linear probing finds the next available
bucket (bucket 2).

yaml

Copy code

Table:

Bucket 0: 10

Bucket 1: 15

Bucket 2: 20

Bucket 3: []

Bucket 4: []

2. Quadratic Probing

In quadratic probing, when a collision occurs, instead of checking the next slot sequentially, it checks
slots in a quadratic pattern. Specifically, after checking i slots, the algorithm checks the (i^2)th slot.

Formula:
h(k, i) = (h(k) + i^2) % table_size

This approach reduces primary clustering compared to linear probing, but it can still suffer from
secondary clustering (keys that hash to the same index follow the same probing pattern).
Example of Quadratic Probing:

For a table of size 5 and a hash function h(k) = k % 5, insert keys 10, 15, and 20:

o h(10) = 0, so 10 is placed in bucket 0.

o h(15) = 0, but bucket 0 is occupied. The next probe is h(15, 1) = (0 + 1^2) % 5 = 1, so 15

goes to bucket 1.

o h(20) = 0, but buckets 0 and 1 are occupied. The next probe is h(20, 1) = (0 + 1^2) % 5 = 1
(already occupied), so the next probe is h(20, 2) = (0 + 2^2) % 5 = 4, and 20 goes to
bucket 4.

yaml

Copy code

Table:

Bucket 0: 10

Bucket 1: 15

Bucket 2: []

Bucket 3: []

Bucket 4: 20

3. Double Hashing

Double hashing uses a second hash function to determine the step size for probing. This method
minimizes clustering by ensuring that the probe sequence is less predictable.

Formula:
h(k, i) = (h1(k) + i * h2(k)) % table_size

Where h1(k) is the primary hash function and h2(k) is the secondary hash function.

Example of Double Hashing:

For a table of size 5, let the primary hash function be h1(k) = k % 5 and the secondary hash function be
h2(k) = 1 + (k % 4). Insert keys 10, 15, and 20.

o h1(10) = 0, so 10 is placed in bucket 0.

o h1(15) = 0, but bucket 0 is occupied. The secondary hash function gives h2(15) = 1 + (15
% 4) = 2. The next probe is h(15, 1) = (0 + 1 * 2) % 5 = 2, so 15 goes to bucket 2.

o h1(20) = 0, but buckets 0 and 2 are occupied. The next probe is h(20, 1) = (0 + 1 * 2) % 5
= 2 (already occupied). The next probe is h(20, 2) = (0 + 2 * 2) % 5 = 4, so 20 goes to
bucket 4.

yaml
Copy code

Table:

Bucket 0: 10

Bucket 1: []

Bucket 2: 15

Bucket 3: []

Bucket 4: 20

Comparison of Collision Resolution Methods

Method Pros Cons Use Case

Simple to implement; Requires extra memory for Good for cases with frequent
Chaining
handles overflow easily linked lists collisions or dynamic datasets

Linear Simple; no extra memory Clustering can degrade Suitable for small datasets with
Probing needed performance a low load factor

Reduces clustering Works better than linear

Quadratic Still suffers from clustering;
compared to linear probing for moderate collision
Probing can leave gaps in the table
probing scenarios

Double Reduces clustering; more Secondary hash function Best for larger datasets where
Hashing uniform distribution needs to be carefully chosen clustering is a concern

Dynamic Hashing in DBMS

Dynamic hashing is an approach to handle the problems encountered with static hashing, particularly
when dealing with overflow and the fixed size of the hash table. It allows the hash table to grow or
shrink dynamically as needed, ensuring that the database can scale and maintain efficient performance
for insertions, deletions, and lookups.

Why Dynamic Hashing?

In static hashing, the size of the hash table is fixed, and if the number of records exceeds the number of
available slots in the hash table, the performance degrades due to overflow or clustering. Dynamic
hashing overcomes this issue by adapting the hash table's size dynamically to the number of records,
thereby maintaining efficient access as the dataset grows.

Key Concepts of Dynamic Hashing

Dynamic hashing works by adapting the hash function and the structure of the hash table as the number
of records grows. The key techniques used in dynamic hashing are:

1. Extendible Hashing (most commonly used)

2. Linear Hashing (less common)

Here, we'll focus on extendible hashing, which is widely used in DBMS systems.

Extendible Hashing

Extendible Hashing is a dynamic hashing technique that uses a directory of pointers to buckets, where
the directory size can grow or shrink dynamically. The idea is to adjust the global depth of the hash table
as needed, to ensure that the table can grow efficiently without causing a lot of collisions or overflow.

How Extendible Hashing Works

1. Hashing and Directory Structure:

The hash table has a directory that contains pointers to buckets. The global depth of the
directory is the number of bits used from the hash value to determine the bucket where a record
should go. The hash function produces an initial hash value, and the global depth determines
how many bits of the hash are considered to index into the directory.

2. Global Depth:
The global depth indicates how many bits of the hash value are used to access the directory. The
more bits are used, the larger the directory and the number of buckets. As the number of
records increases, the global depth may increase, causing the directory to double in size.

3. Local Depth:
Each bucket has a local depth, which indicates how many bits of the hash value are actually
being used to decide the placement of records in that specific bucket. If a bucket overflows, it
can be split, and its local depth may increase, while the global depth remains the same.

4. Splitting Buckets:
When a bucket overflows, it splits into two, and the global depth is increased. This may require
doubling the directory to accommodate the new split.

5. Doubling the Directory:

If the global depth exceeds the local depth of any bucket, the directory is doubled. This means
the number of pointers in the directory increases, which allows for more buckets and reduces
the chance of collisions.

6. Bucket Management:
When the directory is doubled, some pointers may need to be adjusted. The records in the split
buckets are redistributed based on the hash value and the local and global depth.

Steps in Extendible Hashing

1. Insertion Process

• Compute the hash value for the key using the hash function.

• The hash value is divided into two parts:

o The first part is used to index into the directory.

o The second part, based on the local depth of the bucket, determines the placement of
the key within the bucket.

• If the target bucket has space, the key is inserted directly into the bucket.

• If the bucket overflows, it is split. The bucket’s local depth increases, and records are
redistributed between the old bucket and the new one.

• If the global depth increases, the directory is doubled.

2. Directory Doubling

• If the local depth of a bucket exceeds the global depth, the directory must double in size to
accommodate more pointers.

• The new directory has the same entries, but the addressing of buckets changes. The split bucket
may cause records to be redistributed, and some entries may now point to the newly created
buckets.

• The global depth is incremented, and the directory now points to twice as many buckets.

3. Deletion Process

• To delete a record, the bucket is checked to see if the key exists. If found, the key is removed.

• After deletion, if a bucket becomes empty and its local depth is greater than the global depth, it
is merged with another bucket.

• The directory might be shrunk if many buckets become empty.

4. Bucket Split Example

Consider a hash table with a hash function h(k) = k % 8 and a global depth of 2, using 3 bits of the hash
value. We have a directory with pointers to 8 buckets. After inserting several keys, if a bucket overflows,
the bucket will be split, and the global depth will increase.

Example of Extendible Hashing

Consider a hash table with 4 buckets and a global depth of 2 (i.e., 2 bits used from the hash value):

less

Copy code

Directory (Global Depth = 2):

Index: 00 01 10 11

Buckets: [B0] [B1] [B2] [B3]

Assume the hash function is h(k) = k % 4 (which gives the last 2 bits of k):

1. Insert k = 3:
h(3) = 3 % 4 = 11 → Insert into bucket B3.

2. Insert k = 7:
h(7) = 7 % 4 = 11 → Bucket B3 overflows, so we split it.

3. Split Bucket B3:

o Split the bucket and increment the local depth of the bucket.

o The global depth is increased to 3, and the directory is doubled to accommodate the
new local depth.

After splitting, the new structure looks like:

less

Copy code

Directory (Global Depth = 3):

Index: 000 001 010 011 100 101 110 111

Buckets: [B0] [B1] [B2] [B3] [B4] [B5] [B6] [B7]

Now, the number of available buckets has increased, and the hash table can handle more records
efficiently.

Advantages of Extendible Hashing

1. Dynamic Resizing:

o The directory and the hash table grow or shrink as needed, preventing overflow
problems in static hashing.

2. Efficient Lookup:

o Even as the table grows, the number of buckets and the directory size remain
manageable, ensuring that lookups remain efficient.

3. No Overflow:

o Buckets are split and merged dynamically, ensuring that overflow is handled gracefully.

4. Distributed Load:
 o The dynamic adjustment of bucket sizes and directory depth leads to better distribution
of keys across the buckets, minimizing clustering.

Disadvantages of Extendible Hashing

1. Space Overhead:

o The need for maintaining a directory and potentially doubling its size leads to extra
space requirements.

2. Complexity:

o The process of handling splits, directory resizing, and adjusting local/global depth can be
more complex than static hashing.

3. Directory Access Time:

o As the global depth increases, the directory size may grow, potentially leading to higher
access time for locating the correct bucket.

Unit: Relational Data Model

Relational Model Concept in DBMS

The Relational Model is the most commonly used data model in Database Management Systems
(DBMS), introduced by E.F. Codd in 1970. It organizes data into tables (called relations) and describes
the relationships between the data in a logical and structured way.

In the relational model, data is stored in tables, where each table is a collection of rows and columns.
Each row represents a record or a tuple, and each column represents an attribute of the data. The
relational model provides a formal framework for defining, querying, and manipulating data.

Key Concepts of the Relational Model

1. Relation (Table)

o A relation is a set of tuples (rows) and a set of attributes (columns). It can be thought of
as a table in a database, where:

▪ Rows (also called tuples) represent individual records.

▪ Columns (also called attributes) represent the data fields for each record.

o Example: A Student relation could have attributes like StudentID, Name, Age, Major, etc.

Example of a Relation (Table):

 StudentID Name Age Major

101 Alice 20 Computer Science

102 Bob 22 Mathematics

103 Carol 21 Physics

2. Tuple

o A tuple (or row) is a single record in the table. It is a collection of attribute values that
describe a single entity.

o In the above example, (101, Alice, 20, Computer Science) is a tuple that represents a
student.

3. Attribute

o An attribute is a column in a relation. It represents a property or characteristic of the

data being stored.

o For instance, in the Student relation, StudentID, Name, Age, and Major are attributes of
the relation.

4. Domain

o The domain of an attribute is the set of all possible values that the attribute can take.
For example, the domain of Age might be {18, 19, 20, ..., 100} and the domain of Major
might be a set of valid department names such as Computer Science, Mathematics, etc.

5. Primary Key

o The primary key of a relation is an attribute (or a combination of attributes) that

uniquely identifies each tuple in the relation.

o In the Student table, StudentID can be the primary key since each student will have a
unique StudentID.

o A primary key ensures that no two tuples in a relation are identical.

6. Foreign Key

o A foreign key is an attribute (or a set of attributes) in one relation that refers to the
primary key of another relation. It is used to establish a relationship between two
relations.

o For example, in a Course table, StudentID could be a foreign key that references the
StudentID in the Student relation.

7. Relationship
 o In the relational model, a relationship between two relations is established through a
foreign key. A relation can be linked to another relation using the primary key and
foreign key pair.

o For example, if a Student takes multiple Courses, a relationship can be established

between the two using StudentID.

Relational Model Operations

The relational model supports a variety of operations that allow data to be queried and manipulated.
These operations are defined by Relational Algebra and SQL (Structured Query Language). The key
operations include:

1. Select (σ):
The select operation is used to retrieve rows from a relation that satisfy a given condition.

o Example: Select all students with the major "Computer Science".

SQL Query:

sql

Copy code

SELECT * FROM Student WHERE Major = 'Computer Science';

2. Project (π):
The project operation is used to retrieve specific columns (attributes) from a relation.

o Example: Select only the Name and Age of all students.

SQL Query:

sql

Copy code

SELECT Name, Age FROM Student;

3. Union (∪):
The union operation is used to combine the results of two relations that have the same set of
attributes. It returns all distinct tuples from both relations.

SQL Query:

sql

Copy code

SELECT * FROM Student1

UNION
SELECT * FROM Student2;

4. Set Difference (−):

The set difference operation returns tuples that are present in one relation but not in the other.

SQL Query:

sql

Copy code

SELECT * FROM Student1

EXCEPT

SELECT * FROM Student2;

5. Cartesian Product (×):

The Cartesian product operation combines every tuple in one relation with every tuple in
another relation. This can lead to very large results.

SQL Query:

sql

Copy code

SELECT * FROM Student1, Student2;

6. Join (⨝):
The join operation is used to combine two relations based on a common attribute, typically the
foreign key. The most common type of join is the inner join.

SQL Query:

sql

Copy code

SELECT Student.Name, Course.CourseName

FROM Student

INNER JOIN Course ON Student.StudentID = Course.StudentID;

Keys in the Relational Model

1. Candidate Key:
A candidate key is any attribute (or set of attributes) that can uniquely identify a tuple in a
relation. There can be multiple candidate keys, but one of them is chosen as the primary key.
 2. Superkey:
A superkey is a set of one or more attributes that can uniquely identify a tuple. Every primary
key is a superkey, but not every superkey is a primary key.

3. Composite Key:
A composite key is a primary key that consists of more than one attribute. For example, if a
student is identified by both StudentID and CourseID, the composite key would be the
combination of both.

4. Alternate Key:
An alternate key is a candidate key that was not chosen as the primary key.

Integrity Constraints in the Relational Model

Integrity constraints ensure the accuracy and consistency of data in a relational database. There are
several types of integrity constraints in the relational model:

1. Entity Integrity:
Ensures that each tuple in a relation has a unique identifier (the primary key) and that no
primary key value is null.

2. Referential Integrity:
Ensures that foreign keys correctly refer to primary keys in other relations. A foreign key in one
relation must either be null or match a primary key in the referenced relation.

3. Domain Integrity:
Ensures that the values of attributes are from a valid domain (i.e., they conform to the data type,
range, or other restrictions of the attribute).

4. User-Defined Integrity:
Refers to specific rules defined by the user to maintain consistency based on business logic (e.g.,
age should not be less than 18).

Advantages of the Relational Model

1. Simplicity:
The relational model is simple to understand and use, as it deals with tables, which are intuitive
and easy to conceptualize.

2. Flexibility:
The relational model is highly flexible and can handle a wide variety of data types and
relationships, including many-to-many and one-to-many relationships.

3. Data Independence:
The relational model provides a level of abstraction, allowing users to interact with data without
worrying about the underlying storage mechanisms.
 4. Normalization:
The relational model allows data to be normalized, reducing redundancy and improving data
integrity by organizing data into smaller, related tables.

5. Strong Theoretical Foundation:

The relational model is based on well-established mathematical concepts, such as set theory and
relational algebra, ensuring consistency and rigor in database design and querying.

Relational Constraints in DBMS

Relational constraints are rules that help ensure the accuracy and integrity of data in a relational
database. These constraints restrict the type of data that can be inserted into a relation (table) and
ensure that the database maintains consistency and correctness over time.

Relational constraints can be divided into the following types:

1. Domain Integrity Constraints

Domain integrity ensures that the data in a relation conforms to the domain of each attribute (i.e., the
allowable set of values). These constraints ensure that each column in a table contains values of the
correct type, range, and format.

• Example:
The domain of the Age attribute in a Person table might be restricted to positive integers
between 0 and 100.

• Enforced By:
Data types, constraints on values (e.g., constraints on valid values using CHECK), and ranges.

Example SQL:

sql

Copy code

CREATE TABLE Person (

PersonID INT PRIMARY KEY,

Name VARCHAR(100),

Age INT CHECK (Age BETWEEN 0 AND 100)

);

2. Entity Integrity Constraints

Entity integrity ensures that each row in a relation is uniquely identifiable. This is typically done by
enforcing a primary key constraint.
 • Primary Key Constraint:
A primary key is a set of one or more attributes that uniquely identify a tuple (row) in a relation.
The primary key cannot contain NULL values, ensuring every tuple is distinct.

• Enforced By:
The primary key column(s) cannot contain null values and must have unique values across all
tuples in the table.

Example SQL:

sql

Copy code

CREATE TABLE Employee (

EmployeeID INT PRIMARY KEY,

Name VARCHAR(100),

Department VARCHAR(50)

);

• Example Explanation:
The EmployeeID is the primary key, meaning each EmployeeID must be unique and cannot be
NULL.

3. Referential Integrity Constraints

Referential integrity ensures that relationships between tables are maintained and that foreign key
values always point to valid primary key values in another table. A foreign key is an attribute (or a set of
attributes) in one table that refers to the primary key in another table.

• Foreign Key Constraint:

A foreign key is used to establish a relationship between two tables. It ensures that the foreign
key value in the referencing table matches the primary key value in the referenced table, or is
NULL if the relationship is optional.

• Enforced By:
The foreign key constraint ensures that any value in the foreign key column must exist in the
referenced primary key column of another table.

Example SQL:

sql

Copy code

CREATE TABLE Department (

 DepartmentID INT PRIMARY KEY,

DepartmentName VARCHAR(100)

);

CREATE TABLE Employee (

EmployeeID INT PRIMARY KEY,

Name VARCHAR(100),

DepartmentID INT,

FOREIGN KEY (DepartmentID) REFERENCES Department(DepartmentID)

);

• Example Explanation:
The DepartmentID in the Employee table is a foreign key that refers to the DepartmentID in the
Department table. It ensures that any DepartmentID in the Employee table must correspond to
an existing DepartmentID in the Department table.

4. Key Constraints

Key constraints ensure that each tuple in a relation is uniquely identifiable by a set of attributes. The
primary key uniquely identifies a record in a table, and other possible unique identifiers are known as
candidate keys.

• Candidate Key:
A candidate key is a set of attributes that can uniquely identify a tuple in a table. There can be
multiple candidate keys in a table, but one of them is selected as the primary key.

• Unique Key:
A unique key is a set of attributes that must have unique values across all tuples in the table, but
it allows for a NULL value (unlike the primary key, which does not allow NULL).

• Enforced By:
The unique constraint ensures that all values in the column(s) are distinct, and that no two rows
have the same values in the specified columns.

Example SQL:

sql

Copy code

CREATE TABLE Employee (

EmployeeID INT PRIMARY KEY,

 Email VARCHAR(100) UNIQUE, -- Ensures that the email is unique

Name VARCHAR(100)

);

• Example Explanation:
The Email attribute has a unique key constraint, ensuring that no two employees can have the
same email address.

5. User-Defined Integrity Constraints

User-defined integrity constraints are custom rules created by the user to enforce business-specific logic
or rules that cannot be covered by domain, entity, referential, or key constraints. These constraints are
typically enforced through triggers, stored procedures, or check constraints.

• Enforced By:
Check Constraints or custom application logic.

Example SQL:

sql

Copy code

CREATE TABLE Employee (

EmployeeID INT PRIMARY KEY,

Name VARCHAR(100),

Age INT,

Salary DECIMAL(10, 2),

CHECK (Age >= 18 AND Salary >= 30000) -- Ensures that employees are at least 18 years old and earn
at least $30,000

);

• Example Explanation:
The check constraint ensures that the Age of an employee must be 18 or older, and the Salary
must be at least $30,000. This is an example of user-defined integrity.

6. Not Null Constraint

A not null constraint ensures that a particular attribute must always contain a value; it cannot be left
empty. This is useful for attributes that should always have meaningful data.
 • Enforced By:
The NOT NULL constraint ensures that the attribute cannot have NULL values.

Example SQL:

sql

Copy code

CREATE TABLE Customer (

CustomerID INT PRIMARY KEY,

Name VARCHAR(100) NOT NULL, -- Ensures Name cannot be NULL

Address VARCHAR(200)

);

• Example Explanation:
The Name column has a NOT NULL constraint, which ensures that every customer must have a
name.

7. Check Constraints

The check constraint ensures that values in a column satisfy a specific condition or logical expression.
This is commonly used to enforce business rules.

• Enforced By:
The CHECK keyword is used to define conditions that values must meet.

Example SQL:

sql

Copy code

CREATE TABLE Employee (

EmployeeID INT PRIMARY KEY,

Name VARCHAR(100),

Age INT CHECK (Age >= 18) -- Ensures Age is greater than or equal to 18

);

• Example Explanation:
The Age column has a check constraint that ensures the age is greater than or equal to 18.

Summary of Relational Constraints

Constraint Type Description Example SQL

Domain Ensures values are from a valid set or

CHECK (Age BETWEEN 18 AND 100)
Integrity range

Ensures each row is uniquely

Entity Integrity PRIMARY KEY (EmployeeID)
identifiable (Primary Key)

Ensures foreign keys correctly

Referential FOREIGN KEY (DepartmentID) REFERENCES
reference primary keys in another
Integrity Department(DepartmentID)
table

Ensures attributes uniquely identify

Key Constraints UNIQUE (Email)
tuples (Primary Key, Unique)

User-Defined Custom rules defined by users based

CHECK (Salary > 30000)
Integrity on business logic

Not Null Ensures an attribute cannot be NULL NOT NULL

Check Ensures attribute values satisfy a

CHECK (Age > 18)
Constraints specific condition or expression

Here are some SQL queries demonstrating common database operations and concepts like creating
tables, inserting data, updating, and querying data:

1. Create a Table

The CREATE TABLE statement is used to create a new table in the database.

SQL Query:

sql

Copy code

CREATE TABLE Employee (

EmployeeID INT PRIMARY KEY, -- Unique identifier

Name VARCHAR(100), -- Employee name

Age INT CHECK (Age >= 18), -- Age must be 18 or older

DepartmentID INT, -- Department reference

FOREIGN KEY (DepartmentID) REFERENCES Department(DepartmentID) -- Foreign key constraint

);

2. Insert Data into a Table

The INSERT INTO statement is used to insert data into a table.

SQL Query:

sql

Copy code

INSERT INTO Employee (EmployeeID, Name, Age, DepartmentID)

VALUES (1, 'John Doe', 30, 101);

INSERT INTO Employee (EmployeeID, Name, Age, DepartmentID)

VALUES (2, 'Jane Smith', 25, 102);

3. Retrieve Data from a Table

The SELECT statement is used to retrieve data from one or more tables.

• Select all columns from a table:

SQL Query:

sql

Copy code

SELECT * FROM Employee;

• Select specific columns from a table:

SQL Query:

sql

Copy code

SELECT Name, Age FROM Employee;

• Select with a WHERE condition:

SQL Query:

sql

Copy code

SELECT Name FROM Employee WHERE Age >= 30;

4. Update Data in a Table

The UPDATE statement is used to modify existing data in a table.

SQL Query:

sql

Copy code

UPDATE Employee

SET Age = 31

WHERE EmployeeID = 1;

5. Delete Data from a Table

The DELETE statement is used to remove records from a table.

SQL Query:

sql

Copy code

DELETE FROM Employee WHERE EmployeeID = 2;

6. Join Tables

The JOIN operation is used to combine rows from two or more tables based on a related column
between them.

• Inner Join (common rows in both tables):

SQL Query:

sql

Copy code

SELECT Employee.Name, Department.DepartmentName

FROM Employee

INNER JOIN Department ON Employee.DepartmentID = Department.DepartmentID;

• Left Join (all rows from the left table, and matching rows from the right table):

SQL Query:

sql

Copy code

SELECT Employee.Name, Department.DepartmentName

FROM Employee
LEFT JOIN Department ON Employee.DepartmentID = Department.DepartmentID;

7. Group By and Aggregate Functions

• Group by is used to arrange identical data into groups. It is often used with aggregate functions
like COUNT(), SUM(), AVG(), etc.

• Example to find the number of employees in each department:

SQL Query:

sql

Copy code

SELECT DepartmentID, COUNT(*) AS EmployeeCount

FROM Employee

GROUP BY DepartmentID;

8. Sorting Results

The ORDER BY statement is used to sort the result set by one or more columns.

• Sort by a column in ascending order:

SQL Query:

sql

Copy code

SELECT Name, Age FROM Employee

ORDER BY Age ASC;

• Sort by a column in descending order:

SQL Query:

sql

Copy code

SELECT Name, Age FROM Employee

ORDER BY Age DESC;

9. Create Index

Indexes are used to speed up the retrieval of data from a table.

SQL Query:

sql
Copy code

CREATE INDEX idx_employee_name ON Employee(Name);

10. Alter a Table

The ALTER TABLE statement is used to modify an existing table structure, like adding or deleting columns.

• Add a new column:

SQL Query:

sql

Copy code

ALTER TABLE Employee

ADD Salary DECIMAL(10, 2);

• Drop an existing column:

SQL Query:

sql

Copy code

ALTER TABLE Employee

DROP COLUMN Salary;

11. Rename a Table or Column

You can rename an existing table or column using ALTER in combination with RENAME.

• Rename a table:

SQL Query:

sql

Copy code

ALTER TABLE Employee

RENAME TO Staff;

• Rename a column:

SQL Query:

sql

Copy code

ALTER TABLE Employee

RENAME COLUMN Name TO FullName;

12. Create a View

A view is a virtual table based on the result set of a query. It does not store data but presents it in a
structured way.

SQL Query:

sql

Copy code

CREATE VIEW EmployeeView AS

SELECT Name, Age, DepartmentID

FROM Employee

WHERE Age > 25;

13. Subqueries

A subquery is a query nested inside another query. It can be used to perform complex queries.

• Example: Select employees who work in a specific department:

SQL Query:

sql

Copy code

SELECT Name FROM Employee

WHERE DepartmentID = (SELECT DepartmentID FROM Department WHERE DepartmentName = 'Sales');

14. Drop a Table

The DROP TABLE statement is used to remove a table from the database permanently.

SQL Query:

sql

Copy code

DROP TABLE Employee;

15. Drop a Column

The DROP COLUMN statement is used to remove a column from an existing table.

SQL Query:

sql
Copy code

ALTER TABLE Employee

DROP COLUMN Age;

Enhanced Entity-Relationship (EER) to Relational Mapping

The process of mapping an Enhanced Entity-Relationship (EER) diagram to a Relational Schema is a

crucial step in converting a conceptual design (EER diagram) to a logical database design that can be
implemented using relational database management systems (RDBMS). The EER model extends the
standard ER model by adding more complex concepts such as specialization, generalization,
aggregation, and union types.

Here’s how to map various EER concepts to relational schema:

1. Mapping Regular Entity Types (Simple Entities)

A regular entity type represents a real-world object that has attributes and can exist independently.

• Mapping:
For each strong entity (regular entity) in the EER model, create a relation (table) where:

o The attributes of the entity type become the attributes (columns) of the table.

o The primary key is the key attribute(s) of the entity.

Example:
An entity Student with attributes StudentID, Name, and DOB.

• EER:
Student (StudentID, Name, DOB)

• Relational Mapping:

sql

Copy code

CREATE TABLE Student (

StudentID INT PRIMARY KEY,

Name VARCHAR(100),

DOB DATE

);

2. Mapping Weak Entities

A weak entity cannot exist without a strong (owner) entity. It has a partial key, which uniquely identifies
weak entity instances in the context of a specific owner.

• Mapping:
For each weak entity, create a relation that includes:

o The attributes of the weak entity.

o The primary key of the strong entity that owns the weak entity.

o The partial key from the weak entity, combined with the primary key of the strong entity
to form a composite primary key for the weak entity.

Example:
A weak entity OrderItem with attributes Quantity, and Price, dependent on a strong entity Order.

• EER:
OrderItem (OrderID, ProductID, Quantity, Price)
Where OrderID and ProductID are part of the composite key.

• Relational Mapping:

sql

Copy code

CREATE TABLE OrderItem (

OrderID INT,

ProductID INT,

Quantity INT,

Price DECIMAL(10, 2),

PRIMARY KEY (OrderID, ProductID),

FOREIGN KEY (OrderID) REFERENCES Order(OrderID)

);

3. Mapping Superclass-Subclass Relationships (Specialization/Generalization)

A specialization is a process of creating sub-entities from a general entity, and generalization is the
reverse. The subtypes inherit attributes and relationships of the parent (superclass).

There are two primary ways to represent this relationship in the relational model:

a. Single Table (Union Mapping)

All the attributes of the superclass and all subclasses are stored in a single table, with columns for all
attributes. However, only the subclass-specific attributes are filled for instances belonging to that
subclass.

• Mapping:
A table is created that contains all attributes of both the superclass and the subclasses. A
discriminator attribute is added to indicate which subclass an entity belongs to.

Example:
Superclass Employee with subclasses FullTimeEmployee and PartTimeEmployee.

• EER:
Employee (EmpID, EmpName, EmpType)
FullTimeEmployee (Salary)
PartTimeEmployee (HourlyRate)

• Relational Mapping:

sql

Copy code

CREATE TABLE Employee (

EmpID INT PRIMARY KEY,

EmpName VARCHAR(100),

EmpType VARCHAR(50),

Salary DECIMAL(10, 2), -- For full-time employees only

HourlyRate DECIMAL(10, 2) -- For part-time employees only

);

b. Multiple Tables (Disjoint Mapping)

Each subclass is mapped to its own table, which includes the attributes of both the superclass and the
subclass. The superclass is also mapped to its own table, and each subclass table has a foreign key to the
superclass.

• Mapping:
Create separate tables for the superclass and each subclass. Use a foreign key in each subclass
table that references the primary key of the superclass table.

Example:
Employee superclass with FullTimeEmployee and PartTimeEmployee subclasses.

• EER:
Employee (EmpID, EmpName)
 FullTimeEmployee (EmpID, Salary)
PartTimeEmployee (EmpID, HourlyRate)

• Relational Mapping:

sql

Copy code

CREATE TABLE Employee (

EmpID INT PRIMARY KEY,

EmpName VARCHAR(100)

);

CREATE TABLE FullTimeEmployee (

EmpID INT PRIMARY KEY,

Salary DECIMAL(10, 2),

FOREIGN KEY (EmpID) REFERENCES Employee(EmpID)

);

CREATE TABLE PartTimeEmployee (

EmpID INT PRIMARY KEY,

HourlyRate DECIMAL(10, 2),

FOREIGN KEY (EmpID) REFERENCES Employee(EmpID)

);

4. Mapping Aggregation

Aggregation is used when we need to model a relationship between an entity and a relationship set (not
just between two entities). The relationship is treated as a higher-level entity.

• Mapping:
Convert the relationship into an entity, create a table for that entity, and link the original entities
to it via foreign keys.

Example:
If a ProjectAssignment is an aggregation of the Employee and Project entities:
 • EER:
ProjectAssignment (EmployeeID, ProjectID, AssignmentDate)

• Relational Mapping:

sql

Copy code

CREATE TABLE ProjectAssignment (

EmployeeID INT,

ProjectID INT,

AssignmentDate DATE,

PRIMARY KEY (EmployeeID, ProjectID),

FOREIGN KEY (EmployeeID) REFERENCES Employee(EmpID),

FOREIGN KEY (ProjectID) REFERENCES Project(ProjectID)

);

5. Mapping Union Types (Disjoint/Overlapping Subclasses)

In union types, an entity instance can belong to one or more subclasses. The subclasses are not
necessarily mutually exclusive.

• Mapping:
Create a table for the union type that contains the common attributes and a discriminator
column to identify the different types (subtypes).

Example:
Person is a union type with Employee and Customer subtypes.

• EER:
Person (ID, Name, Type)
Employee (ID, Salary)
Customer (ID, PurchaseHistory)

• Relational Mapping:

sql

Copy code

CREATE TABLE Person (

ID INT PRIMARY KEY,

Name VARCHAR(100),
 Type VARCHAR(50) -- 'Employee' or 'Customer'

);

CREATE TABLE Employee (

ID INT PRIMARY KEY,

Salary DECIMAL(10, 2),

FOREIGN KEY (ID) REFERENCES Person(ID)

);

CREATE TABLE Customer (

ID INT PRIMARY KEY,

PurchaseHistory TEXT,

FOREIGN KEY (ID) REFERENCES Person(ID)

);

Summary of Mapping from EER to Relational Model

EER Concept Relational Mapping

Strong Entity Create a table with the entity attributes and primary key.

Create a table with the weak entity's attributes, including the primary
Weak Entity
key of the owner entity.

Superclass-Subclass (Single Create one table for the superclass and subclasses, including a
Table) discriminator column.

Superclass-Subclass Create separate tables for the superclass and each subclass, with foreign
(Multiple Tables) keys linking to the superclass.

Create a table for the aggregated relationship and link to original entities
Aggregation
via foreign keys.

Create a table with a discriminator column and separate tables for each
Union Types
subtype.
Data Normalization in DBMS

Data Normalization is the process of organizing the attributes and tables of a relational database to
minimize redundancy and dependency. The goal is to ensure that data is stored efficiently and that
relationships between data are well defined to prevent data anomalies such as insertion, update, and
deletion anomalies.

Normalization is typically achieved by dividing large tables into smaller, manageable ones, and defining
relationships between them. This process ensures that the data is logically structured and avoids
redundancy.

Types of Normal Forms

There are several normal forms (NF) in database normalization, each with specific rules to improve the
structure of the database.

1. First Normal Form (1NF)

A relation is in First Normal Form (1NF) if:

• All attributes (columns) contain only atomic (indivisible) values.

• Each record in the table is unique (there is a primary key).

In simple terms, 1NF requires:

• Eliminate repeating groups or arrays in columns.

• Ensure each field contains only one value.

Example:
Consider a table where a single column contains multiple values (not atomic).

OrderID Products

1 Apple, Banana

2 Orange, Mango

To bring this into 1NF, we separate the products into individual rows.

Normalized Table (1NF):

OrderID Product

1 Apple

1 Banana

2 Orange
OrderID Product

2 Mango

2. Second Normal Form (2NF)

A relation is in Second Normal Form (2NF) if:

• It is already in First Normal Form (1NF).

• It does not contain any partial dependency, i.e., every non-prime attribute is fully functionally
dependent on the entire primary key.

A partial dependency occurs when a non-prime attribute is dependent on part of a composite primary
key (rather than the entire key).

Example: Consider a table where OrderID and ProductID together form the composite primary key, and
ProductName depends only on ProductID.

OrderID ProductID ProductName Quantity

1 101 Apple 5

1 102 Banana 3

2 101 Apple 2

Here, ProductName depends only on ProductID, not on OrderID. This is a partial dependency, so the
table is not in 2NF.

To convert to 2NF, we decompose the table:

1. Products Table (to handle the partial dependency):

sql

Copy code

CREATE TABLE Products (

ProductID INT PRIMARY KEY,

ProductName VARCHAR(100)

);

2. Orders Table (removes partial dependency):

sql

Copy code
CREATE TABLE Orders (

OrderID INT,

ProductID INT,

Quantity INT,

PRIMARY KEY (OrderID, ProductID),

FOREIGN KEY (ProductID) REFERENCES Products(ProductID)

);

3. Third Normal Form (3NF)

A relation is in Third Normal Form (3NF) if:

• It is in Second Normal Form (2NF).

• It does not contain any transitive dependency, i.e., no non-prime attribute depends on another
non-prime attribute.

A transitive dependency occurs when a non-prime attribute depends on another non-prime attribute,
rather than directly on the primary key.

Example:
Consider a table where OrderID is the primary key, and CustomerCity depends on CustomerID, and
CustomerID depends on OrderID:

OrderID CustomerID CustomerName CustomerCity

1 101 John New York

2 102 Jane Los Angeles

Here, CustomerCity is transitively dependent on OrderID via CustomerID.

To convert to 3NF, we split the table into two:

1. Customers Table (separates customer info):

sql

Copy code

CREATE TABLE Customers (

CustomerID INT PRIMARY KEY,

CustomerName VARCHAR(100),

CustomerCity VARCHAR(100)
);

2. Orders Table (now contains only order-specific info):

sql

Copy code

CREATE TABLE Orders (

OrderID INT PRIMARY KEY,

CustomerID INT,

FOREIGN KEY (CustomerID) REFERENCES Customers(CustomerID)

);

4. Boyce-Codd Normal Form (BCNF)

A relation is in Boyce-Codd Normal Form (BCNF) if:

• It is in Third Normal Form (3NF).

• For every non-trivial functional dependency, the left-hand side must be a superkey (a key that
uniquely identifies each record).

Example:
Consider a table where both StudentID and CourseID form the composite primary key, but
InstructorName depends only on CourseID:

StudentID CourseID InstructorName

101 CS101 Dr. Smith

102 CS101 Dr. Smith

103 MA101 Dr. Johnson

Here, InstructorName depends only on CourseID, which is not a superkey. This violates BCNF.

To convert to BCNF, we decompose the table:

1. Courses Table (contains instructor info):

sql

Copy code

CREATE TABLE Courses (

CourseID VARCHAR(10) PRIMARY KEY,

 InstructorName VARCHAR(100)

);

2. Enrollments Table (contains student-course enrollment info):

sql

Copy code

CREATE TABLE Enrollments (

StudentID INT,

CourseID VARCHAR(10),

PRIMARY KEY (StudentID, CourseID),

FOREIGN KEY (CourseID) REFERENCES Courses(CourseID)

);

5. Fourth Normal Form (4NF)

A relation is in Fourth Normal Form (4NF) if:

• It is in Boyce-Codd Normal Form (BCNF).

• It does not contain any multi-valued dependency, i.e., no attribute set in the table is
independent of another.

Example:
Consider a table where a student can have multiple phone numbers and multiple email addresses, but
the phone numbers and emails are independent of each other:

StudentID PhoneNumber EmailAddress

101 12345 [email protected]

101 67890 [email protected]

This violates 4NF because PhoneNumber and EmailAddress are multi-valued attributes.

To convert to 4NF, we decompose the table into two:

1. StudentPhones Table:

sql

Copy code

CREATE TABLE StudentPhones (

 StudentID INT,

PhoneNumber VARCHAR(15),

PRIMARY KEY (StudentID, PhoneNumber)

);

2. StudentEmails Table:

sql

Copy code

CREATE TABLE StudentEmails (

StudentID INT,

EmailAddress VARCHAR(100),

PRIMARY KEY (StudentID, EmailAddress)

);

6. Fifth Normal Form (5NF)

A relation is in Fifth Normal Form (5NF) if:

• It is in Fourth Normal Form (4NF).

• It does not contain any join dependency, i.e., it cannot be decomposed into multiple relations
without losing information.

In most cases, 5NF is used to deal with complex relationships and ensure that the database can be
decomposed into smaller, more manageable pieces without loss of data integrity.

Summary of Normal Forms

Normal
Criteria
Form

1NF Eliminate repeating groups; each attribute must contain atomic values.

Eliminate partial dependencies; every non-prime attribute must be fully dependent on

2NF
the primary key.

Eliminate transitive dependencies; non-prime attributes must depend directly on the

3NF
primary key.
Normal
Criteria
Form

Eliminate all non-trivial functional dependencies where the left-hand side is not a
BCNF
superkey.

Eliminate multi-valued dependencies; independent attributes must be stored in separate

4NF
relations.

5NF Eliminate join dependencies; decomposition must preserve all information.

Concurrency Control in DBMS

Concurrency Control in Database Management Systems (DBMS) refers to the mechanisms that ensure
that database transactions are executed in a way that preserves the integrity of the database when
multiple transactions are occurring simultaneously. It aims to prevent anomalies and maintain
consistency in a multi-user environment where several users may access and modify the same data
concurrently.

Concurrency control is critical in ensuring that transactions do not interfere with each other in ways that
could lead to errors, such as lost updates, temporary inconsistency, or uncommitted data being read.

Types of Concurrency Control Methods

There are mainly two approaches for concurrency control:

1. Lock-based Protocols

2. Timestamp-based Protocols

3. Optimistic Concurrency Control

4. Multiversion Concurrency Control (MVCC)

Let’s discuss each in detail:

1. Lock-based Protocols

Locking is one of the most widely used mechanisms to ensure that only one transaction can access a
particular piece of data at any given time. When a transaction wants to read or write data, it locks the
data item to prevent other transactions from accessing it until the lock is released.

Types of Locks:

• Exclusive Lock (X-lock): This type of lock is used when a transaction intends to write (modify) a
data item. It prevents all other transactions from reading or writing to the same data item.
 • Shared Lock (S-lock): This lock is used when a transaction wants to read a data item. Multiple
transactions can hold a shared lock on the same data item, but no transaction can write to the
item while there are active shared locks.

Locking Protocols:

• Two-Phase Locking (2PL): This protocol ensures that transactions acquire all the necessary locks
before any data is modified (growing phase), and release the locks only after the transaction is
completed (shrinking phase). It guarantees serializability but may cause deadlocks (when two or
more transactions wait for each other indefinitely).

• Strict 2PL: This is a stricter version of 2PL, where transactions hold all locks until they commit,
and only release them when they commit or abort. It guarantees serializability and also prevents
cascading rollbacks.

Deadlock in Locking: A deadlock occurs when two or more transactions are blocked forever because
each one is waiting for the other to release a resource (lock). To handle deadlocks:

• Deadlock Detection: Periodically check for deadlocks and resolve them, usually by aborting one
of the transactions involved.

• Deadlock Prevention: Avoid situations where deadlocks can occur, often by ensuring
transactions acquire locks in a predefined order.

2. Timestamp-based Protocols

Timestamp-based protocols use timestamps to decide the serializability of transactions without using
locks. Each transaction is assigned a timestamp when it starts, and this timestamp is used to decide the
order of transactions.

Timestamp Ordering Protocol:

• When a transaction requests to access a data item, its timestamp is compared to the last
timestamp of any transaction that has already accessed the item.

• If the transaction's timestamp is greater than the last access timestamp, it is allowed to access
the data. Otherwise, the transaction is aborted or rolled back.

Key Rules:

• Read Rule: A transaction can read a data item if no write has been performed after its
timestamp.

• Write Rule: A transaction can write a data item only if no other transaction has read or written
the item after its timestamp.

Advantages:

• No locking is involved, reducing the chances of deadlock.

 • Simpler and more efficient than lock-based protocols in some cases.

Disadvantages:

• It may lead to unnecessary transaction aborts or rollbacks if the timestamps do not allow for
transaction progression.

3. Optimistic Concurrency Control (OCC)

Optimistic Concurrency Control assumes that conflicts between transactions are rare, so transactions
are allowed to execute without locks. However, before committing a transaction, the system checks for
conflicts and ensures that the transaction can safely commit.

OCC Phases:

1. Read Phase: During this phase, the transaction reads the data and makes local copies of the
items it accesses. It does not make any changes to the database.

2. Validation Phase: Before committing, the system checks whether there were any conflicts during
the transaction execution. A conflict happens if another transaction has modified any data that
the current transaction has accessed.

3. Write Phase: If validation passes, the transaction writes its changes to the database and
commits. If validation fails, the transaction is rolled back and restarted.

Advantages:

• Minimal locking, so transactions can proceed in parallel, improving performance.

• Suitable for systems with low contention and high read operations.

Disadvantages:

• Potential for a high rate of transaction rollbacks if conflicts occur often.

• The validation phase may be costly in systems with high contention.

4. Multiversion Concurrency Control (MVCC)

Multiversion Concurrency Control (MVCC) is a concurrency control method that allows multiple versions
of a data item to exist concurrently. Each transaction accesses a snapshot of the database at a particular
point in time, ensuring that transactions can work independently without locking the data.

How MVCC Works:

• When a transaction modifies a data item, it does not overwrite the existing value but instead
creates a new version of that data item.

• Each version of the data item is tagged with a timestamp or transaction identifier to track when
it was created.
 • Transactions access the most appropriate version of the data based on the snapshot they are
working with.

Advantages:

• No locking is required, eliminating the risk of deadlocks.

• Provides a high degree of concurrency, as transactions can work with different versions of data.

• Suitable for read-heavy workloads.

Disadvantages:

• More complex implementation, as multiple versions of data need to be maintained.

• Can result in versioning overhead if not managed properly.

Other Concurrency Control Techniques

• Serializable Isolation Level: This is the highest level of isolation in which transactions are
executed such that the result of executing the transactions concurrently is the same as if they
were executed serially, one after another. It ensures no anomalies but can be performance-
intensive.

• Isolation Levels: SQL databases support different isolation levels to balance consistency and
concurrency:

1. Read Uncommitted: Transactions can read uncommitted (dirty) data.

2. Read Committed: Transactions can only read committed data.

3. Repeatable Read: Transactions can read the same data multiple times, ensuring no
other transaction modifies the data in the meantime.

4. Serializable: Transactions are fully isolated from each other, with no interference,
ensuring strict consistency.

Database Security in DBMS

Database Security refers to the protection of databases from unauthorized access, misuse, or
corruption. Since databases often contain sensitive and critical data, ensuring their security is vital for
maintaining confidentiality, integrity, and availability. Database security is designed to protect the
database from various threats, including unauthorized access, data breaches, data manipulation, and
other types of cyber-attacks.

Objectives of Database Security

The primary objectives of database security are:

1. Confidentiality: Ensuring that only authorized users can access sensitive data.
 2. Integrity: Ensuring that the data remains accurate and consistent, preventing unauthorized
changes.

3. Availability: Ensuring that data is available for authorized users when needed, and preventing
denial of service.

4. Accountability: Keeping track of who accessed the database and what actions were taken,
ensuring audit trails and logs are available.

Threats to Database Security

Some of the common security threats to databases include:

• Unauthorized Access: When an individual gains access to a database without proper

authorization.

• SQL Injection: A type of attack where malicious SQL statements are injected into a query to
manipulate the database.

• Data Breaches: Unauthorized access to sensitive or confidential data, leading to data leakage.

• Data Corruption: Data is intentionally or accidentally altered, making it unreliable.

• Denial of Service (DoS): An attacker may overload the system, preventing legitimate users from
accessing the database.

• Insider Threats: Security breaches caused by users who have legitimate access to the database
but misuse it.

• Backup and Recovery Failures: Failure to properly back up and restore data in the event of a
failure.

Types of Database Security Measures

There are various techniques and measures used to protect databases. These can be broadly classified
into the following categories:

1. Authentication

Authentication ensures that only authorized users can access the database. Common authentication
mechanisms include:

• Username and Password: The most basic form of authentication, where the user is identified by
a unique username and verified using a password.

• Multi-factor Authentication (MFA): Requires multiple forms of identification (e.g., password and
fingerprint, password and OTP) for access.
 • Biometric Authentication: Uses physical characteristics, like fingerprints, retina scans, or facial
recognition, to authenticate users.

• Single Sign-On (SSO): A mechanism that allows users to authenticate once and gain access to
multiple systems or databases without needing to log in multiple times.

2. Authorization

Authorization ensures that authenticated users can only access resources that they are permitted to use,
based on their roles and privileges. It controls the permissions assigned to users or roles, such as:

• Role-Based Access Control (RBAC): Users are assigned roles, and each role has predefined
permissions (e.g., read, write, delete) associated with it. This simplifies access control and
improves security.

• Discretionary Access Control (DAC): The owner of a resource (e.g., a table or view) decides who
can access it and what operations they can perform.

• Mandatory Access Control (MAC): Security policies define how access rights are granted, often
based on levels of classification (e.g., confidential, secret) and labels assigned to data and users.

• Attribute-Based Access Control (ABAC): Access control decisions are based on the attributes of
users, resources, or the environment (e.g., time of access, location, or job role).

3. Encryption

Encryption ensures that the data is unreadable to unauthorized users, even if it is intercepted or
accessed improperly.

• Data-at-Rest Encryption: Encrypting data stored in the database, ensuring that it remains
protected even if the physical storage media is compromised.

• Data-in-Transit Encryption: Encrypting data while it is being transmitted over the network (e.g.,
using SSL/TLS protocols) to prevent eavesdropping and man-in-the-middle attacks.

• Column-Level Encryption: Encrypting specific sensitive columns in the database (e.g., credit card
numbers, social security numbers) rather than the entire database.

• Transparent Data Encryption (TDE): A feature supported by many DBMSs that automatically
encrypts and decrypts data at the storage level without requiring changes to the application.

4. Auditing and Monitoring

Auditing and Monitoring involve tracking database activity and maintaining logs to detect and prevent
unauthorized actions, such as:
 • Audit Trails: Detailed logs of all database actions, including who performed them, when they
were performed, and what data was accessed or modified. These logs help detect suspicious
activities and investigate security incidents.

• Access Logs: Logs that record login attempts, successful logins, failed logins, and the duration of
the session. This helps detect brute-force attacks or unauthorized access attempts.

• Real-time Monitoring: Continuous surveillance of the database to detect unusual activity or

potential security breaches in real-time.

• Alerting Systems: Automated alerts triggered by suspicious activity, such as unauthorized access,
database changes, or failed login attempts.

5. Backup and Recovery

Backup and recovery mechanisms are essential to ensure that the database can be restored to a secure
and consistent state after a failure, attack, or corruption.

• Regular Backups: Ensuring periodic backups of the entire database, including all tables, indexes,
and metadata, so data can be restored if needed.

• Point-in-Time Recovery: This feature allows a database to be restored to a specific point in time
(e.g., before a data breach or corruption occurred).

• Offsite Backups: Storing backups in a secure offsite location (e.g., cloud storage) ensures that the
data can be recovered even in the event of physical damage to the primary data storage system.

• Encryption of Backups: Ensuring that backup data is encrypted to prevent unauthorized access
in case the backup media is lost or stolen.

6. SQL Injection Prevention

SQL Injection is one of the most common database security vulnerabilities, where an attacker inserts or
manipulates SQL queries to execute malicious commands on the database.

Techniques to Prevent SQL Injection:

• Prepared Statements (Parameterized Queries): Ensure that SQL queries are structured properly
and that user input is treated as data, not executable code.

• Stored Procedures: Use stored procedures to encapsulate SQL logic and reduce the possibility of
injection by not allowing direct user input in SQL queries.

• Input Validation: Ensure that user inputs are sanitized and validated to prevent malicious input,
such as checking for special characters like semicolons (;) and single quotes (').

• Escaping User Input: Properly escape special characters in SQL queries to ensure that user inputs
are treated as literals, not code.
7. Database Firewalls

A Database Firewall is a specialized security tool designed to monitor and filter database traffic to
prevent malicious or unauthorized access.

• Traffic Filtering: Database firewalls can monitor incoming queries and block suspicious requests,
such as those attempting SQL injection or unauthorized access.

• Behavior Analysis: The firewall can learn the typical query patterns of authorized users and flag
any queries that deviate from this pattern.

• Granular Access Control: Enforcing access control rules to ensure that only authorized users and
applications can access certain tables, columns, or database features.

8. Database Masking

Data Masking involves obfuscating sensitive data to protect it from unauthorized access while
maintaining its utility for testing and development.

• Static Data Masking: Replaces sensitive data with fake data in non-production environments. For
example, credit card numbers may be replaced with dummy values like XXXXXXXXXXXX1234.

• Dynamic Data Masking: Dynamically masks sensitive data when it is accessed, ensuring that only
authorized users can see the full data.

9. Physical Security

Physical Security involves protecting the physical hardware where the database resides, ensuring that
unauthorized individuals cannot gain access to the database servers.

• Access Controls: Limiting physical access to the database servers to authorized personnel only.

• Surveillance Systems: Installing cameras and security systems to monitor access to the database
hardware.

• Environmental Controls: Ensuring that data centers are equipped with proper fire suppression
systems, backup power supplies, and climate control to protect the hardware from physical
threats.

Database Recovery in DBMS

Database Recovery refers to the process of restoring a database to a consistent and correct state after a
failure or crash, ensuring that no data is lost, and integrity is maintained. A failure can occur due to
various reasons, including hardware malfunctions, software bugs, user errors, or power outages. The
goal of database recovery is to handle these failures in a way that minimizes downtime and ensures that
the database is returned to a reliable and usable state.
Key Concepts in Database Recovery

1. Transaction: A transaction is a sequence of operations that is treated as a single unit. Each

transaction should follow the ACID properties (Atomicity, Consistency, Isolation, Durability),
ensuring that either all operations in a transaction are committed or none of them are, even in
the event of a failure.

2. Log: The transaction log is a crucial component of database recovery. It records all the changes
made to the database, including both the before and after values of data items. The log helps in
identifying the transactions that were in progress at the time of a failure and provides the
necessary information for rolling back or rolling forward transactions.

3. Checkpoint: A checkpoint is a mechanism that periodically saves the current state of the
database and logs in the database. It marks a point at which the system can safely recover,
reducing the need to replay the entire transaction log during recovery.

4. Undo and Redo: These are two fundamental operations used during recovery:

o Undo: Reverts changes made by a transaction that was not completed (rolled back).

o Redo: Re-applies changes made by a transaction that was committed before the failure.

Types of Database Failures

1. Transaction Failures: A transaction may fail due to logical errors or violations of the integrity
constraints (e.g., attempting to divide by zero). In this case, only the affected transaction needs
to be rolled back.

2. System Failures: A system crash, such as a power failure or operating system crash, can occur.
This type of failure may leave some transactions in an inconsistent state, and the database needs
to be recovered to ensure consistency.

3. Media Failures: These failures occur when the storage medium (hard disk, SSD, etc.) experiences
physical damage, resulting in the loss of data. Recovery from this type of failure is often more
complex and may require restoration from backups.

Database Recovery Techniques

Several techniques and strategies are employed to achieve database recovery:

1. Write-Ahead Log (WAL) Protocol

The Write-Ahead Log (WAL) protocol is the foundation of many database recovery techniques.
According to this protocol:
 • Before any changes are made to the database, the log record of the transaction (which includes
the before and after images of the data) must be written to disk.

• Only after the log is written can the changes be applied to the actual database.

This protocol ensures that the database can always be restored to a consistent state, even in the event of
a crash, by replaying the transaction logs.

2. Transaction Log Recovery

The Transaction Log is a crucial part of the recovery process. It records each transaction's operation,
which can be used to:

• Redo operations that were committed but not yet written to the database before the failure.

• Undo operations for transactions that were not committed at the time of the failure.

There are two primary types of log-based recovery strategies:

• Deferred Update: Changes are first written to the log, and then the database is updated. If a
transaction fails, no changes are made to the database.

• Immediate Update: Changes are applied to the database immediately, but the transaction log is
still used for recovery. If a failure occurs, the database uses the log to undo or redo changes.

3. Checkpointing

A Checkpoint is a point in time where the database and log are synchronized, meaning that all
transactions before the checkpoint are either committed or rolled back. After a checkpoint, only a subset
of the transaction log needs to be replayed for recovery.

Checkpointing reduces the time required for recovery after a failure because it minimizes the number of
transactions that must be reprocessed from the log. Typically, a checkpoint includes:

• Writing all dirty pages (pages modified in memory) to disk.

• Updating the log to record the checkpoint.

The recovery process can then begin from the last checkpoint, avoiding the need to scan the entire log.

4. Recovery Process (Redo and Undo)

The recovery process is generally based on two main steps:

1. Redo Phase: Re-applies all transactions that were committed before the failure but whose
changes were not written to disk. This ensures that no committed transaction is lost.
 2. Undo Phase: Rolls back any transactions that were active at the time of the failure and had not
been committed. This ensures that the database does not contain any partial transactions that
could lead to inconsistency.

The recovery process proceeds as follows:

• Step 1: The system starts by scanning the transaction log from the last checkpoint.

• Step 2: It first re-applies the operations (redo) for transactions that were committed but had not
yet been written to disk at the time of the failure.

• Step 3: Then, it undoes the operations for transactions that were active or had failed before the
crash.

5. Shadow Paging

Shadow Paging is another technique used for database recovery, where two pages of data are
maintained: the current page and the shadow page (a backup page). During normal operations:

• When a transaction makes a change, it updates the current page and creates a new shadow page
with the previous version of the data.

• If a failure occurs, the system can recover by using the shadow page (which remains unchanged)
to restore the previous consistent state.

This approach reduces the need for extensive logging but may require more space since two copies of
the data are maintained at all times.

6. ARIES (Algorithm for Recovery and Isolation Exploiting Semantics)

ARIES is a widely used recovery algorithm that combines WAL and checkpointing with the concept of
"log-based" recovery. It follows these key principles:

• Write-Ahead Logging (WAL): All log records are written to stable storage before changes are
applied to the database.

• Cache Management: The ARIES algorithm ensures that recovery can take place even if pages are
cached in memory and not written to disk.

• Redo and Undo Operations: ARIES performs both redo (to reapply committed transactions) and
undo (to roll back incomplete transactions).

ARIES uses a three-phase recovery process:

• Analysis Phase: Scans the log to identify which transactions were active and which pages need
to be redone or undone.

• Redo Phase: Re-applies the changes made by all committed transactions.

 • Undo Phase: Rolls back the changes made by uncommitted transactions.

7. Backup and Restoration

While transaction logs and recovery mechanisms can restore a database to its most recent state after a
failure, backups are essential for more catastrophic failures, such as media crashes.

• Full Backup: A complete snapshot of the entire database at a specific point in time.

• Incremental Backup: A backup that contains only the changes made since the last backup, which
reduces storage requirements.

• Differential Backup: A backup that includes changes made since the last full backup.

• Point-in-Time Recovery: In case of a failure, the system can restore from backups and apply
transaction logs to bring the database to a specific point in time before the failure.

Recovery Techniques in DBMS

Database recovery techniques are critical in ensuring that a database can restore to a consistent state
after a failure. Different failure types (transaction failures, system crashes, media failures) require various
strategies and techniques. The recovery process ensures that no committed data is lost and that
uncommitted data is not present in the database after recovery.

Types of Failures

• Transaction Failures: Occurs when a transaction cannot complete due to internal errors or
violates integrity constraints.

• System Failures: System crashes, such as a power failure or operating system crash.

• Media Failures: Hardware failures or damage to storage devices that affect the database’s data.

Key Recovery Techniques

The recovery process involves using transaction logs, backups, and specific algorithms that allow the
system to restore the database state.

1. Write-Ahead Logging (WAL) Protocol

Write-Ahead Logging is one of the most widely used recovery techniques. It ensures that logs of the
transaction are written before any changes are made to the database. This guarantees that if the system
crashes, the log can be used to redo committed transactions or undo incomplete ones.

• Log records: Before any changes are made to the database, the transaction's log record
(including before and after images) is written to disk.

• Transaction commit: Once the log record is written, the changes can then be applied to the
database.
 • Recovery: In case of a crash, WAL ensures that the database can be restored by using the log to
either redo or undo transactions.

2. Transaction Log Recovery

The Transaction Log is a crucial part of recovery. It records the changes made by transactions and is used
to determine which transactions were committed or rolled back.

• Redo: When recovering, transactions that were committed before the failure, but whose
changes were not fully written to the database, are reapplied to the database.

• Undo: For transactions that were in progress at the time of the failure, any changes they made
need to be undone.

Two major types of transaction log recovery techniques are:

• Deferred Update: In this approach, changes are not written to the database until the transaction
commits. If the transaction fails before committing, no changes are made to the database,
ensuring consistency.

• Immediate Update: In this approach, changes are written to the database immediately, but the
log is still used to ensure recovery. If the transaction fails before committing, the log can be used
to undo changes.

3. Checkpointing

A checkpoint is a mechanism to reduce recovery time by periodically saving the current state of the
database and its log. During a checkpoint:

• All modified (dirty) pages in memory are written to disk.

• The transaction log is also updated to reflect that all changes up to that point are safely saved.

In case of a failure, the system can begin recovery from the most recent checkpoint, reducing the need
to process the entire log.

• Benefits: Checkpointing helps to minimize the amount of work required during recovery, as the
system only needs to replay the log from the last checkpoint.

4. Shadow Paging

Shadow Paging is an alternative recovery technique in which two copies of the database pages are
maintained:

• Current Pages: The active data pages in the database.

• Shadow Pages: A backup of the data pages before any changes are made.
In this method:

• When a transaction makes a change, a new page is created in memory (instead of directly
modifying the original page), and the shadow page remains intact.

• If a failure occurs, the system can discard the changes made and restore the database to the
state of the shadow pages, effectively "undoing" all uncommitted changes.

• Advantages: No need for a complex log; however, it can require a larger storage space since two
copies of pages are maintained.

5. ARIES (Algorithm for Recovery and Isolation Exploiting Semantics)

ARIES is a sophisticated recovery algorithm used in many modern DBMS systems. It combines WAL,
checkpointing, and transaction logs to provide a robust recovery mechanism.

ARIES follows a three-phase recovery process:

1. Analysis Phase: Scans the log from the last checkpoint to determine which transactions were
active at the time of the crash and which pages need to be re-logged.

2. Redo Phase: Re-applies all changes made by transactions that were committed before the
failure. This ensures that committed changes are not lost.

3. Undo Phase: Rolls back changes made by transactions that were not committed at the time of
the crash.

ARIES is known for its ability to handle large databases and high concurrency with minimal overhead.

6. Backup and Restore

Backup and Restore is a fundamental part of database recovery, especially in cases of hardware or
media failure. Regular backups (full, incremental, or differential) help ensure that data can be restored to
a consistent state after catastrophic failures.

• Full Backup: A complete copy of the entire database at a specific point in time.

• Incremental Backup: Only the changes made since the last backup are saved.

• Differential Backup: Saves the changes made since the last full backup.

During recovery, the database is restored from the latest full backup and then the incremental or
differential backups are applied in sequence to bring the database to the state it was in at the time of
failure.

7. Point-in-Time Recovery
Point-in-Time Recovery (PITR) allows the database to be restored to a specific point in time, typically just
before a failure or undesirable event (e.g., accidental deletion of data).

• Process: The database is first restored from the most recent backup, and then transaction logs
are applied up to the desired recovery point.

• Use case: PITR is useful for undoing specific changes, such as recovering from accidental data
deletion or corruption.

8. Write-Behind and Deferred Update

These are techniques used to delay the actual writing of changes to the database until after the
transaction commits.

• Write-Behind Update: Updates are first recorded in memory or log and written to the database
only when needed. This ensures that no changes are lost in case of a crash.

• Deferred Update: Changes are made to the transaction log but not applied to the database until
after the transaction commits. This approach ensures that no updates are made to the database
if a failure occurs before the commit.

9. Recovery Using Quorum-Based Replication

Quorum-based replication involves maintaining multiple copies of the database across different servers.
The system requires a majority (quorum) of the database replicas to be available for operations to
proceed.

• Recovery: In the event of a failure, the database can be restored using the available replicas, and
once the failed system recovers, it can be synchronized with the primary database.

This technique helps in achieving high availability and data consistency in distributed systems.

10. Hybrid Recovery Techniques

Many modern DBMSs use a combination of different recovery techniques to maximize both performance
and reliability. These hybrid approaches combine transaction logging, checkpoints, backup systems, and
distributed replication to achieve fast and reliable recovery.

For example:

• Write-Ahead Logging (WAL) may be used for transaction-level recovery, while shadow paging or
ARIES may be used to enhance performance or handle specific types of failures more efficiently.