DATABASE MANAGEMENT

SYSTEMS

Complete Exam Notes

1
. External Sorting & Sort-Merge Algorithm

2
. Join Algorithms (Nested Loop, Merge Join, Hash Join)

3
. Transaction Processing & ACID Properties

4
. Database Security Issues

5
. Statistical Databases & Security

6
. Mandatory Access Control (MAC)

7
. Transaction Schedules & Serializability

8
. Discretionary Access Control (DAC)
 Topic 1: External Sorting

Definition
External sorting is used when data is too large to fit into main memory (RAM).

Data is stored on disk and sorted in parts.

The most common method is the Sort-Merge Algorithm.

Sort-Merge Algorithm — Core Idea

It works in two main phases:

Phase 1: Sorting Phase (Run Generation)

• Large file is divided into small chunks (runs)
• Each chunk is loaded into memory, sorted in RAM
• Written back to disk as a sorted run
■ Result: Many small sorted files (runs)

Phase 2: Merging Phase

• Sorted runs are combined (merged)
• Multiple runs are merged at once
• Process repeats until only one fully sorted file remains
■ Result: Final sorted file

Important Terms (Must Write in Exam)

Term Symbol Meaning

Memory blocks; each holds one disk

Buffers n_B
block

Sorted chunks created in sorting

Runs n_R
phase

Number of runs merged at one time

Degree of Merge d_M = n_B − 1
(1 buffer reserved for output)

Example (High Chance in Exam)

Given: Total blocks b = 1024, Buffers n_B = 5

Step 1 — Sorting Phase: Number of runs = ■1024 / 5■ = 205 sorted runs

Step 2 — Merging Phase: Degree of merge d_M = 5 − 1 = 4 (merge 4 runs at a time)

Merge Passes:
Pass Runs In Runs Out

Pass 1 205 52

Pass 2 52 13

Pass 3 13 4

Pass 4 4 1 (final)

■ Total ≈ 4 passes

Cost Formula (VERY IMPORTANT)

Cost = 2b + 2b × logdM(nR)

• 2b → Read + Write in sorting phase

• 2b × log(d_M)(n_R) → Cost of all merging passes (each pass reads and writes entire file)

Key Points (Write for Full Marks)

✔ Minimum 3 buffers required
✔ Performance depends on: number of buffers, number of passes
✔ Used in: ORDER BY, DISTINCT, JOIN, UNION, INTERSECTION
✔ If data is already indexed → sorting may not be needed
 Topic 2: Join Algorithms in DBMS

Overview
Join algorithms combine rows from two or more tables based on a related column. The query optimizer
automatically selects the most efficient algorithm.

1. Nested Loop Join

Each row of one table is compared with every row of another table.

• Time complexity: O(n × m)

• Simple but inefficient for large datasets

• Performance improves significantly if indexes are used

2. Merge Join
Works on sorted tables. Both tables are sorted on the join column and scanned simultaneously.

• Time complexity: O(n log n)

• If data is already sorted → very efficient O(n + m)

• Best for pre-sorted or indexed data

3. Hash Join
Uses a hash table to match rows. A hash table is built on the smaller table; the larger table is probed.

• Average time complexity: O(n + m)

• Very efficient for large datasets

• Requires sufficient memory; performance decreases with hash collisions

Comparison Table
Feature Nested Loop Join Merge Join Hash Join

Complexity O(n × m) O(n log n) O(n + m)

Needs Sorting No Yes No

Needs Index Better with index No No

Best For Small tables Sorted/large data Large unsorted data

Query Optimizer — Selection Factors

Table Size: Large tables → Hash Join; small tables → Nested Loop
Index Availability: Indexes present → Nested Loop becomes faster
Data Distribution: Uniform data → improves Hash Join performance
Memory Availability: Hash Join requires memory for hash tables
Sorting: Already sorted data → Merge Join preferred
 Topic 3: Transaction Processing

System Types
Single-User System
Only one user can access and perform operations at a time. No concurrency issues — transactions
execute one at a time. Simple to manage but not suitable for large applications.

Example: Personal computer database

Multi-User System
Multiple users access and perform operations simultaneously. Improves performance and efficiency.
Requires proper concurrency control to prevent conflicts and data inconsistency.

Example: Banking system

Processing Methods
Interleaved Processing
A single CPU executes multiple transactions by switching rapidly between them. It appears simultaneous
but transactions actually execute one after another in fast sequence. Improves CPU utilization but not true
parallel execution.

Parallel Processing
Multiple CPUs execute multiple transactions truly simultaneously. Increases system speed and
performance. Used in modern systems for large-scale operations.

Transaction Definition
A transaction is a logical unit of work consisting of multiple database operations (read/write). It must
be completed entirely or not at all. Transactions ensure the database remains consistent and reliable.

Example: Money transfer between two bank accounts

ACID Properties
Atomicity
A transaction is treated as a single unit — either ALL operations complete or NONE execute. If any
error occurs, the system rolls back all changes.

Example: If money is deducted but not added → transaction fails

Consistency
 The database remains in a valid state before and after the transaction. No rules or constraints should
be violated.

Example: Total balance remains correct after transfer

Isolation
Multiple concurrent transactions do not affect each other. Each transaction works independently until
completed.

Example: One user's transaction is hidden from others

Durability
Once a transaction is committed, its changes are permanently stored even if a system crash occurs.

Example: Saved transaction remains after system restart

Transaction Operations
Operation Purpose Example

Retrieve data from database into

Read Reading account balance
memory

Update data in database after

Write Updating new balance
modification

Permanently save all changes made

Commit Finalizing money transfer
during transaction

Rollback Undo all changes if an error occurs Cancelling transaction on failure

Transaction Schedules
Serial Schedule
Transactions execute one after another without overlapping. Ensures maximum safety and consistency
but reduces performance.

■ T1 completes fully → then T2 starts

Non-Serial Schedule
Transactions are interleaved and executed concurrently. Improves performance but may cause conflicts if
not properly managed.

■ T1 and T2 execute operations together

Recovery Techniques
Technique Description Example

System saves current state at

Checkpointing regular intervals to reduce recovery System saves progress periodically
time

Reverses effects of incomplete

Undo Cancelling unfinished transaction
transactions to maintain consistency

Reapplies effects of committed Restoring saved transaction after

Redo
transactions not yet saved to disk crash

Changes not applied to database

Deferred Update Save only after confirmation
until transaction commits

Changes applied instantly; recorded

Immediate Update Live update with backup log
in logs for recovery

Changes made on a copy; after

Shadow Paging commit, original replaced with Editing copy, then replacing original
updated copy
 Topic 4: Database Security Issues

Overview
Database security is a broad area that includes legal, policy, and system-related issues. It focuses
on protecting data from unauthorized access, misuse, or damage.

Types of Security Issues

Legal and Ethical Issues
Rules about accessing and using information legally and ethically.
Example: Accessing someone's medical record without permission is illegal.

Policy Issues
Rules defined by an organization or government about which data should be protected.
Example: A company policy may restrict access to employee salaries.

System-Related Issues
Security implemented at hardware, OS, or DBMS level.
Example: Password protection at OS level + access control at DBMS level.

Multiple Security Levels

Data and users classified into: Top Secret, Secret, Confidential, Unclassified.
Example: Military database allows only top-level users to access 'Top Secret' data.

Threats to Databases (CIA Model)

Threat Definition Example

Unauthorized or incorrect Hacker changes student marks in

Loss of Integrity
modification of data database

Authorized users cannot access Server crash prevents database

Loss of Availability
data when needed access

Unauthorized disclosure of sensitive Leak of customer credit card

Loss of Confidentiality
data information

DBMS Security Mechanisms

Discretionary Security
Users are given privileges to access specific data.

Example: A user is allowed to read but not modify a table.

Mandatory Security
Access is based on security clearance levels. Users can only access data at their level or below.

Example: A 'Confidential' level user cannot access 'Top Secret' data.

Role-Based Security
Access is based on user roles in an organization.

Example: Manager → full access; Employee → limited access

Control Measures
✔ Access Control: Restricts access using usernames and passwords.
Example: Login system requiring ID and password.
✔ Inference Control: Prevents users from guessing confidential data from statistical results.
Example: Report shows average salary but hides individual salaries.
✔ Flow Control: Prevents information from reaching unauthorized users via covert channels.
Example: Blocking hidden communication channels.
✔ Data Encryption: Converts data into coded form to protect it during transmission and storage.
Example: HTTPS encrypts data during online transactions.

Role of DBA (Database Administrator)

• Create user accounts
• Grant and revoke privileges
• Assign security levels to users and data

Sensitive Data Types

Type Example

Inherently Sensitive Medical records

From Sensitive Source Secret informer's identity

Declared Sensitive Company marks data as confidential

Sensitive Attribute Salary column in a table

Sensitive by Relation Combining two datasets reveals private info

■■ EXAM TIP: CIA loss = main threats | DBA = main authority | DAC vs Mandatory = very
important difference | Sensitive data types = high exam chance
 Topic 5: Statistical Databases & Security

Definition
A Statistical Database contains information about a large group of individuals and is mainly used to
produce statistical summaries, not individual records.

• It hides individual data

• It allows only group-level (aggregate) information

Allowed Access — Aggregate Functions Only

Function Meaning

COUNT Number of records

SUM Total value

AVG Average value

MIN / MAX Smallest / largest value

STANDARD DEVIATION Variation in data

■ Direct access to individual records is RESTRICTED.

Statistical Queries
Safe Query: SELECT COUNT(*) FROM EMP_SALARY WHERE Emp_department = '3'

Returns total employees in dept 3 — no individual data exposed.

Unsafe Query: SELECT AVG(income) FROM EMP_SALARY WHERE Emp_id = '2'

■■ If only one employee matches → AVG = that person's exact salary → privacy broken!

Security Vulnerabilities
WHERE Condition Manipulation
Attackers change conditions to target one specific person and extract confidential data.

Small Group Problem

If a query applies to 1–2 people, the result can reveal individual data directly.

Query Combination Attack

Run multiple queries and subtract results to find a single person's data. Query 1: Salary of all employees in
dept → Query 2: Salary excluding one person → Subtract = that person's salary

Protection Measures
Partitioning of Database
Database divided into groups of minimum size. Queries access entire groups only — small subsets
blocked.

Threshold Constraints
A query is rejected if the number of records it accesses is below a set minimum (e.g., 5 people). Small
results make it easy to identify individuals.

Query Sequence Monitoring

System monitors sequences of queries to detect suspicious patterns. Tracks repeated or overlapping
queries and blocks suspicious activity.
 Topic 6: Mandatory Access Control (MAC)

Definition
Mandatory Access Control (MAC) is a security system where only the system or administrator
controls access. Normal users cannot change permissions by themselves. It is a strict and
centralized security model.

Where MAC is Used

• Military systems
• Government offices
• Intelligence agencies

How MAC Works

A. Clearance (for Users): Every user gets a security level — e.g., Employee → Manager →
Administrator

B. Classification (for Files/Data): Every file gets a security label — e.g., Public → Confidential →
Secret

Access Rule: If user clearance ≥ file classification → access GRANTED. If clearance < classification
→ access DENIED.

Example:
Manager → can access Confidential files ✔
Employee → cannot access Secret files ✘

Types of MAC
A. Multilevel Security System (Vertical)
Works like a ladder. A user can access their own level AND lower levels. Purpose: Stop higher-level
information from leaking.
Example: A Manager can see: Public + Confidential files. Cannot see: Secret files.

B. Multilateral Security System (Horizontal + Vertical)

Also checks department/domain. Two users with the same level but different departments cannot access
each other's data.
Example: HR Manager cannot access Finance files, even if both are 'Manager' level.

Key Characteristics
✔ Centralized Control — administrator or system controls everything
✔ No User Control — users cannot change permissions or share files
✔ Policy-Based — all decisions follow fixed security rules
 ✔ High Security — prevents data leakage and unauthorized access

Popular MAC Tools

Tool Used In

Security-Enhanced Linux (SELinux) Red Hat, CentOS

AppArmor Ubuntu, Debian (easier to manage)

TrustedBSD FreeBSD systems

■■ EXAM TIP: MAC = centralized control. Users cannot change permissions. Clearance level
must be ≥ data classification for access.
 Topic 7: Transaction Schedules & Serializability

Schedule — Definition
A schedule is the sequence in which operations (Read/Write) of multiple transactions are executed in
a database.

Types of Schedules
Serial Schedule
One transaction completes fully before another starts. Always consistent — no errors possible.

T1: Read(A) → Write(A) → Commit → T2: Read(A) → Write(A) → Commit

✔ No overlapping | ✔ Always safe

Non-Serial Schedule
Operations of multiple transactions are interleaved. Needs concurrency control.

T1: Read(A) → T2: Read(A) → T1: Write(A) → T2: Write(A)

■■ May cause inconsistency without proper control

Serializable Schedule
A non-serial schedule that produces the same result as a serial schedule. Gives performance +
correctness.

(1) Conflict Serializable

Can be converted into a serial schedule by swapping non-conflicting operations.

■ Check Method: Precedence Graph — No cycle = Serializable

(2) View Serializable

Same result as serial schedule even if not conflict-serializable.
• Same initial read
• Same final write
• Same read-from relation
✔ More general | ✔ Harder to check

Non-Serializable Schedule
Result is NOT equivalent to any serial schedule. Leads to data inconsistency and incorrect results.
Not acceptable in DBMS.
 Detection: If Precedence Graph contains a cycle → schedule is Non-Serializable.

Recoverable vs Non-Recoverable Schedules

(A) Recoverable Schedule
If T2 reads data written by T1, then T1 must COMMIT before T2 commits.

Example: T1: Write(A) → T2: Read(A) → T1: Commit → T2: Commit ✔

(B) Cascading Rollback (Problem)

If one transaction fails, all dependent transactions also fail — costly undo chain.

Example: T1 writes A → T2 reads A → T1 aborts → T2 must also abort ■

(C) Cascadeless Schedule (Solution)

Transactions only read COMMITTED data — no cascading rollback possible.

Example: T1: Write(A) → Commit → T2: Read(A) ✔ Safe

(D) Strict Schedule ■ Most Important

No transaction can read OR write data until the previous transaction commits/aborts. Safest schedule
— no dirty reads or writes.

Example: T1: Write(A) → Commit → T2: Read(A) ✔ Safest

(E) Non-Recoverable Schedule ■

T2 commits BEFORE T1 (whose data it read) → recovery is impossible if T1 aborts.

Example: T1: Write(A) → T2: Read(A) → T2: Commit → T1: Abort ■ Cannot recover

Relationship Hierarchy (VERY IMPORTANT FOR EXAM)

Recoverable ⊃ Cascadeless ⊃ Strict ⊃ Serial
• All Strict schedules are Cascadeless

• All Cascadeless schedules are Recoverable

Conflict Operations
Two operations conflict if they satisfy ALL three conditions:

1. Belong to different transactions

2. Access the same data item

3. At least one of them is a Write

Example: T1: Write(A) and T2: Read(A) → ✔ Conflict
 Topic 8: Discretionary Access Control (DAC)

Definition
Discretionary Access Control (DAC) is a security mechanism in which the owner of a resource has
the authority to decide who can access the resource and what actions they can perform.

Simple meaning: The owner controls access to their own data.

Key Features of DAC

• Owner-Based Control: Each resource (file, table) has an owner who controls access.
• Discretion (Choice): The owner has freedom to grant or revoke access to other users.
• Grant and Revoke: Grant = give permission | Revoke = remove permission
• Flexibility: Permissions can be changed easily at any time.
• Security Concern: If the owner gives wrong permissions → security risks can arise.

Discretionary Privileges
A privilege is a permission that allows a user to perform specific actions on data — i.e., 'what a user is
allowed to do'.

Privilege Meaning

SELECT / Read View data

INSERT / Write Add data

UPDATE Modify data

DELETE Remove data

EXECUTE Run a program or procedure

Levels of Discretionary Privileges

A. Account Level Privileges
Assigned to user accounts by the DBA. Independent of specific tables — apply to overall database
actions.

Common privileges: CREATE TABLE, ALTER, DROP, INSERT, UPDATE, DELETE, SELECT

Example: DBA gives user: SELECT (can view) + INSERT (can add) — but cannot DELETE tables.

B. Relation (Table) Level Privileges

Applied to specific tables or views. The creator (owner) of the table gets full control and can grant
permissions to others.
 Grant Option: Owner can allow others to pass permissions further (User A gets access and can give
access to User B).

Example: User creates 'Students' table → gives User A: read access, User B: update access.

Access Matrix Model

The Access Matrix Model represents who can access what and how using a table (matrix).

• Rows = Users (Subjects) | Columns = Resources (Objects) | Cells = Permissions

User File 1 File 2 File 3

Mary Read Write —

Sashi — Read Write

Rahul Write Read Append

Final Summary
Category Description

DAC Owner controls access

Privileges Permissions (read, write, execute, etc.)

Account Level Controlled by DBA

Table Level Controlled by object owner

Access Matrix Table showing access rights for all users/objects

■■ EXAM TIP: DAC = access control mechanism | Privileges = permissions | Owner = main
controller | DBA = system-level controller