📚 Fundamentals of Database Design

Brief Overview
This note covering Database Systems was created from a 334-page PDF (download link). It walks you
through the core concepts of data vs. information, database vs. DBMS, data abstraction layers, ER modeling,
relational theory, normalization, indexing, and transaction management, giving you a solid foundation before
diving into any class or textbook.

Key Points
Understand the distinction between raw data, processed information, and how DBMS organizes
them.
Learn the three‑level schema architecture and the notions of data independence.
Master ER diagrams, relational mapping, and the full normalization hierarchy up to 5NF.
Get acquainted with indexing structures, B‑trees, and concurrency control mechanisms.

📚 Basics of Data, Information, Database & DBMS

🔎 Data & Information
Data – characteristics or attributes (qualitative or quantitative) collected through observation.
Information – processed data placed in context, enabling understanding and decision‑making.

The diagram visualizes eight common data categories (Geographical, Cultural, Scientific, etc.), illustrating the
breadth of raw data that can later become information.
Binary streams are the fundamental “bits” that computers store as data.
🗂️ Database & DBMS
Database – a structured collection of data stored electronically for easy access, management, and
updates.
DBMS – software that provides efficient storage, retrieval, and management of data, ensuring safety,
integrity, concurrency, and support for querying/reporting.

Illustrates how databases organize data (cylinders) and present analytical results (pie chart).
Three stacked cylinders symbolise the layered functions of a DBMS.
⚖️ File System vs. DBMS (Feature Comparison)
Feature File System DBMS
Data Access Slower, unstructured queries Structured querying → faster
access
Data Isolation Separate files → isolation issues Integrated data → reduced
isolation
Data Integrity Prone to accidental alteration Built‑in integrity constraints
Atomicity Incomplete operations cause Transaction support ensures
inconsistency atomicity
Concurrent Access Anomalies from simultaneous Advanced concurrency control
edits

🏗️ Data Abstraction Levels

Physical Level – internal schema; details of how data are stored on hardware.
Logical (Conceptual) Level – entity sets, relationships, and constraints; DB schema.
View Level – user‑specific perspectives; subsets of the database.
Shows the three abstraction tiers, from physical storage to user views.
🔄 Data Independence
Ability to change the schema at one level without affecting higher levels.

Physical Data Independence – modify internal schema (e.g., add index) without altering
conceptual schema.
Logical Data Independence – change conceptual schema (e.g., add/remove entity) without
impacting external schemas or applications.
📦 Instance & Schema
Instance – snapshot of the database at a specific moment (current data).
Schema – blueprint describing the logical structure, tables, attributes, and relationships.

📊 OLAP vs. OLTP

Aspect OLAP (Analytical) OLTP (Transactional)
Primary Function Complex analysis & reporting Daily transaction processing
Design Star/snowflake (read‑optimized) Normalized (write‑optimized)
Query Complexity Aggregations, multi‑dimensional Simple CRUD
Data Volume Large, historical Many small, current
Response Time Slower Fast

🏛️ Database Architecture & DBA

📚 Types of Databases
 Commercial – e.g., Salesforce (CRM).
Multimedia – stores images, audio, video (e.g., Adobe Experience Manager).
Deductive – uses logic programming (e.g., Datalog).
Temporal – time‑based data (e.g., historical stock prices).
GIS – geographic information (e.g., ArcGIS).

👤 DBA (Database Administrator) Roles

DBAs define schemas, storage structures, access methods, modify organization, grant authorizations, and
enforce integrity constraints.

Illustrates the varied responsibilities of a DBA.

🏗️ DBMS Architecture
Shows major subsystems: Query Processor, Storage Manager, Recovery Manager, etc.
1. Query Processor
DML Compiler – translates DML to low‑level instructions.
DDL Interpreter – processes schema‑defining statements.
Embedded DML Pre‑compiler – converts embedded DML in applications.
Query Optimizer – selects the most efficient execution plan.
2. Storage Manager (Database Control System)
Authorization Manager – handles privileges.
Integrity Manager – enforces constraints.
Transaction Manager – maintains consistency during concurrent access.
File Manager – oversees file space & structures.
Buffer Manager – caches data between memory & disk.
3. Disk Storage
Data Files, Data Dictionary, Indices.

🗂️ Three‑Level DBMS Architecture

1. Internal Level – physical storage, compression, indexing.
2. Conceptual Level – logical schema (tables, attributes, relationships).
3. External Level – user‑specific views and interfaces.

📊 ER Modeling
🧩 ER Diagram Overview
Developed by Peter Chen (1976), the ER model visualizes real‑world entities and relationships for
database design.
Historical context of the ER model’s creator.
🏷️ Entity & Entity Set
Entity – a distinguishable object (concrete or abstract).
Entity Set – collection of entities sharing the same attributes; drawn as a rectangle.

Visual of an entity set symbol.

Types of Entities
Tangible – physically existent (e.g., Car, Pen).
Intangible – logical existence (e.g., Account, Video).
📏 Attributes
Attributes describe properties of an entity; each has a domain of permitted values.

Simple – indivisible (e.g., Age).

Composite – composed of multiple simple attributes (e.g., Address = Street + City + Zip).
Single‑valued – one value per entity instance.
Multi‑valued – multiple values (e.g., Phone Numbers).
Stored – permanently stored (e.g., Date_of_Birth).
Derived – computed from other attributes (e.g., Age = CurrentDate – Date_of_Birth).

Derived attribute “age” illustrated.

Representation
ER Diagram – ovals (attributes) attached to rectangles (entities).
Relational Model – columns in a table.

🔗 Relationship / Association
An association among two or more entities (different or same entity set).

Symbol – diamond in ER diagrams; foreign key or separate table in relational model.

Components – Name, Degree (number of participating entity sets), Structural constraints
(cardinality, participation).
Dropdown metaphor for choosing relationship types.
📁 Example ER Diagrams
Bank System

Shows entities like Bank, Branch, Customer, Account, Loan and their relationships.
University System

Depicts Professors, Departments, Courses, Students, etc.

University System (alternate)

More detailed view with programs, sections, textbooks.

Marketing / Retail System
 Illustrates Product, Order, Payment, Delivery, etc.

🗃️ Relational Model & Functional Dependencies

📐 Core Concepts
Relation – table with rows (tuples) and columns (attributes).
Key – minimal attribute set uniquely identifying a tuple.
Functional Dependency (FD) – X → Y means attribute set Y is functionally determined by X .

🧩 Armstrong’s Axioms
1. Reflexivity – if Y ⊆ X , then X → Y .
2. Augmentation – if X → Y , then XZ → Y Z .
3. Transitivity – if X → Y and $

🔗 Types of Relationships in ER Modeling

Unary (Self‑referential) Relationship – a single entity set participates twice; two entities of the same set
are related (e.g., a team member supervising another member).
 Binary Relationship – the most common; exactly two distinct entity sets are linked.

Ternary Relationship – involves three entity sets (e.g., Teacher – Subject – Course association).

Quaternary Relationship – involves four entity sets.

N‑ary Relationship – a relationship among n entity sets, where n can be any positive integer.

📐 Cardinality (Cardinality Ratios)

Expresses how many instances of one entity may be associated with instances of another.
Ratio Description Typical Example
1:1 (One‑to‑One) Each entity in A associates with An instructor advises at most one
at most one entity in B and student; a student has at most
vice‑versa. one advisor.
1:M (One‑to‑Many) An entity in A may relate to zero An instructor can advise many
or more entities in B; each B students, but each student has
relates to at most one A. only one advisor.
M:1 (Many‑to‑One) An entity in A relates to at most A student may have many
one B; each B may relate to zero instructors, but each instructor
or more A. advises at most one student.
M:N (Many‑to‑Many) Entities on both sides may relate A student may have many
to zero or more entities on the advisors and an advisor may
opposite side. advise many students.

📊 Participation Constraints
Total Participation – every entity of the participating set must appear in the relationship.

Partial Participation – some entities of the set may not participate.

These constraints are often visualized by double (total) or single (partial) lines connecting entity sets to the
relationship diamond.

🏛️ Strong vs. Weak Entity Sets

Strong Entity Set – possesses a primary key; each tuple is uniquely identifiable.

Weak Entity Set – lacks a sufficient set of attributes for a primary key; identified by a partial key
(discriminator) together with the primary key of an owning strong entity. Represented by a double
 rectangle in ER diagrams.

Weak Entity Dependencies

A weak entity is existence‑dependent on an identifying (owner) strong entity.
The identifying relationship (drawn with double diamonds) is many‑to‑one from the weak entity
to its owner, with total participation of the weak entity.
The primary key of the weak entity = owner’s primary key ∪ discriminator attributes.
Reasons to Use Weak Entities
1. Reflects logical dependence on another entity.
2. Enables automatic deletion when the owning strong entity is removed.
3. Prevents duplication and potential inconsistencies.

🔄 Converting an ER Diagram to a Relational Schema

ER Construct Relational Mapping
Strong Entity Set Create a table with its attributes; primary key =
entity’s key.
Weak Entity Set Create a table; include foreign key referencing
owner’s primary key plus discriminator attributes;
composite primary key = (owner PK, discriminator).
Unary Relationship Add a foreign‑key column in the same table
referencing its own primary key.
1:1 Relationship No separate table; place the primary key of the side
with total participation as a foreign key in the
other side.
1:N / N:1 Relationship Add the primary key of the “one” side as a foreign
key in the “many” side table.
M:N Relationship Create an associative table; include foreign keys of
both participating tables; composite primary key =
(FK₁, FK₂).
N‑ary Relationship (N ≥ 3) Create a relation containing foreign keys of all
participating entity tables; composite primary key =
combination of those foreign keys.
Multivalued Attribute Create a separate table; include foreign key to the
owning entity and the multivalued attribute;
composite primary key = (FK, attribute).
Composite Attribute Decompose into its simple component attributes
and store them as separate columns in the owning
entity’s table.
🧬 Generalization & Specialization
Generalization – bottom‑up merging of two or more lower‑level entities into a higher‑level (super)
entity, emphasizing shared characteristics.
Specialization – top‑down splitting of a higher‑level entity into more specific lower‑level entities,
emphasizing distinguishing attributes.
Both techniques aid schema simplification and improve query clarity.

📦 Aggregation
Aggregation abstracts a relationship (or set of relationships) as a higher‑level entity, allowing complex
relationships to be treated as single units in the diagram.

✅ Advantages & Disadvantages of ER Diagrams

Aspect Advantage Disadvantage
Transformation Direct mapping to relational May lose some constraint details.
tables.
Simplicity Easy to understand with minimal Complex projects can produce
training. overly intricate diagrams.
Expressiveness Visualizes entities, attributes, and Limited ability to represent
relationships clearly. advanced constraints (e.g.,
triggers, stored procedures).

🗄️ Relational Database Management System (RDBMS) Basics

An RDBMS (conceptualized by Edgar F. Codd, 1970) stores data in relations (tables) and enforces
integrity constraints, providing a foundation for most modern commercial and open‑source databases.

Core Terminology
Domain – set of atomic permissible values for an attribute (often defined by a data type).
Relation (Table) – a set of tuples (rows).
Tuple – a single row/record.
Arity / Degree – number of attributes (columns) in a relation.
Cardinality – number of tuples (rows) in a relation instance.

Relational Table Properties

1. Cells contain atomic values.
2. All values in a column share the same domain.
 3. Each row is unique.
4. Table names are unique within a schema.
5. Column names are unique within a table.
6. Row order is insignificant.
7. Column order is insignificant.

⚠️ Anomalies in Unnormalized Relations

Anomaly Type Description
Insertion Anomaly New information cannot be added without also
inserting unrelated data.
Deletion Anomaly Deleting a tuple may unintentionally remove other
needed information.
Modification Anomaly Updating a value requires changes in multiple
tuples, risking inconsistency.

📚 Normalization Overview
Normalization refines a database schema to eliminate redundancy and dependency anomalies. The hierarchy
of normal forms:
1. 1NF → 2NF → 3NF → BCNF → 4NF → 5NF
First Normal Form (1NF)
Each cell holds indivisible (atomic) values; no repeating groups or multivalued attributes.

Unique column names.

Primary key defined.
Duplicate rows removed.
Prime vs. Non‑Prime Attributes
Prime attribute – part of any candidate key.
Non‑prime attribute – not part of any candidate key.
Partial & Full Dependency
Partial Dependency: non‑prime attribute depends on a proper subset of a candidate key.
Full Dependency: non‑prime attribute depends on the whole candidate key.

Second Normal Form (2NF)

Relation is in 1NF and contains no partial dependencies (every non‑prime attribute fully depends on the
candidate key).

Third Normal Form (3NF)

 Relation is in 2NF and contains no transitive dependencies (non‑prime → non‑prime).

Direct definition: For every FD α → β, either α is a superkey or β is a prime attribute.

Boyce‑Codd Normal Form (BCNF)

Every determinant (α in α → β) must be a superkey.

All 2‑attribute relations are automatically in BCNF.

A relation with only prime attributes is always in 3NF, but not necessarily BCNF.
Fourth Normal Form (4NF)
Relation is in BCNF and contains no non‑trivial multivalued dependencies (MVDs).

Each MVD is decomposed into a separate table where it becomes trivial.

Fifth Normal Form (5NF) / Project‑Join Normal Form
Relation is in 4NF and cannot be further decomposed losslessly while preserving all join dependencies.

🔗 Dependency Preservation & Lossless Decomposition

Lossless (Non‑Additive) Join
Decomposition of R into R₁, R₂ is lossless iff R₁ ⋈ R₂ = R (the natural join reproduces exactly the
original relation).
Conditions for lossless join (binary decomposition):
1. Att(R₁) ∪ Att(R₂) = Att(R) (attribute union covers all of R).
2. Att(R₁) ∩ Att(R₂) ≠ ∅ (there is at least one common attribute).
3. The common attribute set is a key for at least one of the decomposed relations, i.e., (Att(R₁) ∩
Att(R₂)) → Att(R₁) or → Att(R₂).

Dependency Preserving Decomposition

Let R be decomposed into R₁,…,Rₙ with FD sets F₁,…,Fₙ.
The decomposition preserves dependencies iff (F₁ ∪ … ∪ Fₙ)⁺ = F⁺.
Note: Sometimes a lossless decomposition sacrifices dependency preservation for higher normal forms.

🗂️ Keys Summary
Key Type Definition
 Superkey Any attribute set whose closure determines all
attributes of the relation.
Candidate Key Minimal superkey (no proper subset is a superkey).
Primary Key One candidate key chosen by the DB administrator;
cannot contain NULLs.
Alternate Key Any candidate key not selected as the primary key.
Foreign Key Attribute(s) referencing the primary key of another
(or the same) table, enforcing referential integrity.
Composite Key Key consisting of multiple attributes.
Secondary Key Non‑primary key used to speed up searches; may
contain duplicate values.
Prime Attribute Attribute that belongs to any candidate key.

📂 Indexing & File Organization

File Organization
Type Characteristics Search Complexity
Ordered (Sorted) File Records sorted on a search key; O(log₂ n) block accesses
enables binary search.
Unordered (Heap) File Records appended without order; O(n) block accesses
only linear search possible.

Maintenance cost: ordered files require re‑ordering on insert/delete, while unordered files have cheaper
maintenance but slower searches.

Index Structures
Index record = (Key, Block‑pointer).
Index files are much smaller than the main data file because they store only the indexed attribute
and a pointer to the block containing the full record.
Index Types
Index Level Examples
Single‑level Primary Index, Clustering Index, Secondary Index
Multilevel Simple multilevel, B‑tree, B+‑tree
Primary Index – built on the primary key of a sorted main file; sparse (one entry per block).
Clustering Index – index on a non‑primary key that determines the

📂 Indexing Structures
🔹 Clustered Indexing
Definition: The main file is ordered on non‑key attributes.

Number of entries in the index file = number of unique values of the indexed attribute.
Example of both sparse and dense indexing.
🔹 Secondary Indexing
Definition: An additional index file built on an attribute other than the primary key, often because
frequent queries target that attribute.

Main file is unordered with respect to the secondary attribute.

Can be built on key or non‑key attributes.
Number of index entries = number of records in the main file → dense indexing.
Example Question (Secondary Indexing)
Ordered file with r = 30,000 records.
Block size B = 1024 B, record length R = 100 B (unspanned).
Ordering key = 9 B, block pointer = 6 B.
Task: Implement secondary indexing (details omitted – focus on concept).
⚖️ Dense vs. Sparse Indexing
Index Type Entry per Space Requirement Search Speed
Dense Every search‑key value Larger (more index Faster (direct lookup)
in the main file records)
Sparse Only some records (e.g., Smaller Slower (may need block
first record of each scan)
block)

Note: Dense and sparse are not mutually exclusive; a file can exhibit both characteristics depending on the
attribute and implementation.

🌳 B‑Tree Fundamentals
📐 Definition & Properties
An m‑way search tree where every node (except possibly the root) obeys:

Root: ≥ 0 and ≤ m children.

Internal nodes (≠ root): ≥ ⌈m/2⌉ and ≤ m children.
Leaf nodes: All on the same level (perfectly balanced).
Node Type MAX children MIN children MAX keys MIN keys
 Root m 0 m−1 —
Internal m ⌈m/2⌉ m−1 ⌈m/2⌉ − 1

Leaf m ⌈m/2⌉ − 1 m−1 ⌈m/2⌉ − 1

➕ Insertion Rules
1. Start with a single root (also a leaf) at level 0.
2. When a full leaf (contains m − 1 keys) receives another key, split it:
Middle key moves up to the parent.
Two new sibling nodes receive the remaining keys.
3. If the parent becomes full, it splits recursively, possibly propagating to the root.
4. Splitting the root creates a new level (tree height increases by 1).
🧩 Example Insertion (Order = 3)
Insert the sequence 5, 10, 12, 13, 14, 1, 2, 3, 4 into an empty B‑tree of order 3.
(Step‑by‑step tree evolution omitted – focus on the rule that each split promotes the median key.)

🗄️ Query Languages Overview

📖 Procedural Query Language
Users specify what data to retrieve and how to obtain it (e.g., Relational Algebra).

📖 Non‑Procedural Query Language

Users describe what data they need without detailing the retrieval method (e.g., Relational Calculus).

🔗 Relationship Among Languages

Relational model → RDBMS → RA, RC → SQL

RA (procedural) and RC (non‑procedural) form the mathematical foundation.

SQL combines elements of both, operating on an RDBMS.

📚 Relational Algebra (RA)

📌 Core Operators
Operator Symbol Arity Description
Select σ Unary Keeps tuples satisfying a
predicate.
 Project π Unary Keeps specified
attributes (columns).
Rename ρ Unary Gives a new name to the
result relation.
Union ∪ Binary Combines tuples from
two relations
(set‑union).
Set Difference − Binary Tuples in left relation
not in right.
Cartesian Product × Binary Pairs every tuple of the
first relation with every
tuple of the second.

📌 Derived Operators
Operator Symbol Derived From
Join ⋈ Cartesian product + selection
Intersection ∩ Set difference: r ∩ s = r − (r − s)
Division ÷ Uses ×, −, and π
Assignment = Directly names the result of an
expression

📊 Operator Classification
Unary: σ, π, ρ (operate on one relation).
Binary: ∪, −, × (operate on two relations).

📐 Relational Schema
Relation schema R(A₁, A₂, …, Aₙ) consists of a name R and an ordered list of attributes.

Each attribute Aᵢ represents a domain role.

Example: STUDENT (NAME, ID, CITY, COUNTRY, HOBBY).
A relational instance is the actual set of tuples at a specific point in time.

📂 Fundamental RA Operations
🔽 Project (Vertical Selection)
π selects specific columns; returns a relation without the omitted attributes.
 Minimum 1 column, maximum n − 1.
Syntax example: π customer_name (depositor).
🔽 Select (Horizontal Selection)
σ filters rows based on a predicate p.

Removes only tuples, never columns.

Example: σ balance < 1000 (account).
Selection Properties
Commutative:
σ p₁ ∧ p₂ (r) = σ p₂ ∧ p₁ (r) = σ p₁ (σ p₂ (r)) = σ p₂ (σ p₁ (r)).
Comparison operators: =, ≠, <, >, ≤, ≥.
Logical connectives: ∧ (and), ∨ (or), ¬ (not).
➕ Union (Binary)
r ∪ s = { t | t ∈ r or t ∈ s }.

Validity: Same arity and matching domains for corresponding attributes.

Properties:
Degree unchanged: Deg(R ∪ S) = Deg(R) = Deg(S).
Cardinality bounds: max(|R|, |S|) ≤ |R ∪ S| ≤ |R| + |S|.
➖ Set Difference (Binary)
r − s yields tuples present in r but not in s.

Same arity and domain requirements as Union.

✖️ Cartesian Product (Binary)
R₁ × R₂ = { rs | r ∈ R₁ ∧ s ∈ R₂ }.

Result schema concatenates attributes of R₁ followed by those of R₂.

Result cardinality = |R₁| × |R₂|.

🔁 Additional RA Constructs
🔄 Rename
ρ creates a new relation name (or renames attributes) for the result of an expression.

Syntax: ρx(A₁, A₂, …, Aₙ)(E).

📐 Set‑Intersection (Derived)
r ∩ s = r − (r − s).

Returns tuples common to both relations.

🔗 Natural Join
Binary operation that merges two relations on all common attributes, eliminating duplicate columns.

Associative and lossy (does not preserve all original information).

➗ Division
Used when querying “all X that are related to every Y in another set.

Formal expression: πStudent(R) − {πStudent[(πStudent(R) × S) − πStudent,Task(R)]}.

🛠️ SQL Primer
📖 Introduction
SQL (Structured Query Language) is a domain‑specific language for defining, manipulating, and
querying relational data.
Originated from relational algebra (procedural) and tuple relational calculus (non‑procedural).
📆 Evolution of Standards
SQL‑86, SQL‑89, SQL‑92, SQL‑99, SQL‑2003, SQL‑2006, SQL‑2008, SQL‑2011, SQL‑2016,
SQL‑2019, SQL‑2023.

📂 Classification of SQL Statements

Category Purpose Typical Commands
DDL (Data Definition) Create/alter/drop schema CREATE, ALTER, DROP,
objects TRUNCATE, COMMENT, GRANT,
REVOKE
DML (Data Manipulation) Retrieve or modify data INSERT, UPDATE, DELETE,
SELECT
‑ Procedural DML Specify how to get data (e.g., —
with explicit joins)
‑ Declarative DML Specify what data are needed —
DCL (Data Control) Transaction control & permissions COMMIT, ROLLBACK, GRANT,
REVOKE
 DQL (Data Query) Query data (subset of DML) SELECT
VDL (View Definition) Define virtual tables (views) CREATE VIEW, ALTER VIEW,
DROP VIEW

📋 CREATE TABLE Syntax

CREATE TABLE table_name (
column1 data_type [constraints],
column2 data_type [constraints],
column3 data_type [constraints],
...
);

Example

CREATE TABLE Students (

StudentID INT PRIMARY KEY,
FirstName VARCHAR(50),
LastName VARCHAR(50),
Age INT,
Email VARCHAR(100)
);

📊 Common Data Types

Numeric: INT, SMALLINT, BIGINT, DECIMAL(p,s), FLOAT, REAL.
String: VARCHAR(n), CHAR(n), TEXT.

🔧 ALTER TABLE Operations

Add column: ALTER TABLE Employees ADD PhoneNumber VARCHAR(15);
Modify column: ALTER TABLE Employees MODIFY COLUMN PhoneNumber VARCHAR(20);
Drop column: ALTER TABLE Employees DROP COLUMN PhoneNumber;
Rename column: ALTER TABLE Employees RENAME COLUMN PhoneNumber TO ContactNumber;
Rename table: ALTER TABLE Employees RENAME TO Staff;
Drop table: DROP TABLE table_name;
🔑 Foreign Key Definition
CREATE TABLE Orders (
OrderID INT PRIMARY KEY,
CustomerID INT,
OrderDate DATE,
FOREIGN KEY (CustomerID) REFERENCES Customers (CustomerID)
);
 Adding later: ALTER TABLE Orders ADD FOREIGN KEY (CustomerID) REFERENCES Customers
(CustomerID);
📥 INSERT Statements
INSERT INTO Students (StudentID, FirstName, LastName, Age)
VALUES
(1, 'Amit', 'Sh

## 🔗 Join Operations & Result Sets

> **Join** – combines tuples from two relations based on a join condition.

| Join Type | Symbol | Result (using R1 and R2) |

|----------|--------|--------------------------|
| **Inner Join** | `R1 ⋈ R2` |

A | B | C
---|---|---
1 | P | X
2 | Q | Y
3 | R | Y

|
| **Left Outer Join** | `R1 ⟕ R2` |

A | B | C
---|---|---
1 | P | NULL
2 | Q | X
3 | R | Y

|
| **Right Outer Join** | `R1 ⟖ R2` |

A | B | C
---|---|---
2 | Q | X
3 | R | Y
NULL | S | Z

|
| **Full Outer Join** | `R1 ⟗ R2` |

A | B | C
---|---|---
1 | P | NULL
2 | Q | X
3 | R | Y
NULL | S | Z
 |

The tables illustrate how unmatched rows are padded with **NULL** in outer joins.

---

## 🏷️Alias (Rename) Operation

> **Alias** – a temporary name given to a table or column for the duration of a query.

- Syntax: `old_name AS new_name` (usable in **SELECT** and **FROM** clauses).

- Does **not** modify the underlying database schema.

```sql
SELECT account_number, balance * 1.06 AS total_balance
FROM account;

📊 Aggregate Functions
Functions that take a set of values and return a single summarised value.

Function Description
AVG Arithmetic mean of numeric values.
MIN Smallest value.
MAX Largest value.
SUM Total of numeric values.
COUNT Number of rows (or non‑NULL values).
COUNT(*) counts all tuples, including those with NULLs.
All aggregates except COUNT ignore NULL values.

SELECT COUNT(*) FROM account;

SELECT AVG(balance) FROM account WHERE branch_name = 'south_delhi';

Equivalence Check:

SELECT AVG(balance) FROM account;

SELECT SUM(balance)/COUNT(balance) FROM account;

Both statements produce the same average when balance contains no NULLs.

📑 Ordering Tuples
 The ORDER BY clause sorts the result set.

SELECT DISTINCT branch_name

FROM branch
WHERE branch_city = 'Delhi'
ORDER BY branch_name ASC; -- alphabetical ascending

SELECT DISTINCT branch_name

FROM branch
WHERE branch_city = 'Delhi'
ORDER BY branch_name DESC; -- alphabetical descending

✏️ String Operations & Pattern Matching

Strings are delimited by single quotes: 'Computer'.
Equality is case‑sensitive by the SQL standard; some DBMS (MySQL, SQL Server) treat it
case‑insensitively unless configured otherwise.
Common String Functions (varies by DBMS)
Concatenation, substring extraction, length, upper/lower conversion, trimming.
Pattern Matching with LIKE
Pattern Meaning
% Matches any substring (including empty).
_ Matches exactly one character.
Examples:

-- Exactly 5‑character branch names

SELECT branch_name
FROM branch
WHERE branch_name LIKE '_____';

-- Names containing “kumar”

SELECT customer_name
FROM customer
WHERE customer_name LIKE '%kumar%';

Escape Character
 -- Treat % as a literal character
SELECT *
FROM table_name
WHERE column_name LIKE 'ab\%cd%' ESCAPE '\';

📂 GROUP BY & HAVING

GROUP BY groups rows that share the same values of specified attributes, enabling aggregate calculations
per group.

SELECT branch_name, AVG(balance) AS avg_bal

FROM account
GROUP BY branch_name;

HAVING filters groups after aggregation.

SELECT branch.branch_name, AVG(balance) AS avg_bal

FROM branch JOIN account ON branch.branch_name = account.branch_name
WHERE branch_city = 'gwalior'
GROUP BY branch.branch_name
HAVING AVG(balance) > 1500;

⏰ Triggers
Trigger – a special procedure that fires automatically in response to INSERT, UPDATE, or DELETE
operations on a table or view.

Enforces business rules, audits changes, or maintains derived data.

🧩 Embedded & Dynamic SQL

Embedded SQL – static SQL statements embedded in a host language (e.g., C, Java) and compiled
together.
Dynamic SQL – SQL statements constructed at runtime (e.g., via string concatenation) and
executed via APIs such as EXECUTE IMMEDIATE.
Offers flexibility but requires careful handling to avoid SQL injection.

📐 Relational Calculus
Tuple Relational Calculus (TRC)
Non‑procedural language; queries specify what to retrieve.

General form: { t | Condition(t) }

t ∈ R denotes that tuple t belongs to relation R.
Attribute access: t.A or t[A].
Example

{ t | Student(t) ∧ [Link] = 'CSE' }

Domain Relational Calculus (DRC)

Variables range over individual domain values rather than tuples.

General form: (x1, x2, …, xn | COND(x1, …, xn, …))

Example

{ (RollNo, Name, Branch) |

Student(RollNo, Name, Branch) ∧ Branch = 'CSE' }

✅ Safety & Expressive Power

Safe expressions produce only tuples built from values present in the database; unsafe
expressions may generate infinite results (e.g., { t | ¬(t ∈ Instructor) }).
When restricted to safe expressions, TRC, DRC, and the basic relational algebra (∪, −, ×, σ) are
equivalent in expressive power.
Neither calculus includes aggregation natively, though extensions are possible.

💾 Transactions & ACID Properties

A transaction is a set of logically related operations that must be executed as an atomic unit.

Property Meaning
Atomicity All operations succeed or none do.
 Consistency Transaction transforms the database from one
consistent state to another.
Isolation Concurrent transactions appear to execute serially.
Durability Once committed, changes survive crashes.

Transaction States
State Description
ACTIVE Transaction is executing.
PARTIALLY COMMITTED Final statement executed; still pending write‑ahead
log flush.
FAILED Encountered an error; cannot continue.
ABORTED Rolled back; database restored to pre‑transaction
state.
COMMITTED Successfully completed; changes made durable.

🔄 Schedules & Serializability

Schedule – interleaved execution of operations from multiple transactions.

Types of Schedules
Type Description
Serial Transactions run one after another; always safe.
Non‑Serial Operations interleaved; may be safe if serializable.

Conflict Serializability
Two operations conflict if they belong to different transactions, access the same data item, and at
least one is a WRITE.
A schedule is conflict‑serializable if it can be transformed into a serial schedule by swapping
non‑conflicting operations.

Precedence Graph Method

1. Build a directed graph G(V, E).
V = transactions.
Edge Ti → Tj exists if Ti’s write precedes Tj’s read/write on the same item, or Ti’s read
precedes Tj’s write.
2. If the graph is acyclic, the schedule is conflict‑serializable; a topological order gives a equivalent
serial order.
View Serializability
Weaker than conflict serializability.
Two schedules are view‑equivalent if:
1. They read the same initial values.
2. Each read of a value written by another transaction reads the same written value in both
schedules.
3. The final write on each data item is performed by the same transaction.
A schedule that is view‑equivalent to a serial schedule is view‑serializable.

🔧 Recoverability, Cascading, & Strictness

Property Definition
Recoverable If Ti reads a value written by Tj, then commit(Tj)
must occur before commit(Ti).
Cascadeless No transaction reads uncommitted data; i.e., a read
of a value written by Tj occurs only after
commit(Tj).
Strict Neither reads nor writes a data item that has been
written by an uncommitted transaction.

📜 Log‑Based Recovery
The transaction log records all actions to ensure durability and enable rollback.
Log Record Meaning
Transaction Ti begins.
Ti changes data item Xj from V1 to V2.
Ti successfully commits.
Ti is aborted (rolled back).
A write‑ahead log must be flushed before the actual data page is updated.

🗂️ Deferred vs. Immediate Database Modification

Aspect Deferred Immediate
Write Timing At commit only. As soon as the change occurs.
I/O Overhead Fewer writes (batched). More frequent writes.
Recovery Complexity Simpler (no uncommitted changes Requires undo of uncommitted
in DB). writes.
📚 Shadow Paging Recovery
Maintains two page tables:
1. Current page table – reflects the state during the transaction.
2. Shadow page table – points to the pre‑transaction state.
Modification: New page copies are created; the current table is updated to point to them.
Commit: Discard the shadow table; the current table becomes the permanent mapping.
Failure before commit: Switch back to the shadow table, instantly restoring the original state.

🌐 Data Fragmentation (Distributed Databases)

Fragmentation Type How it works Typical use case
Horizontal Divides a table into row subsets Parallel processing, locality of
based on a predicate (e.g., region reference.
= 'North').
Vertical Splits a table into column Different applications need
subsets; each fragment includes different attribute sets; reduces
the primary key for data transfer.
reconstruction.
Both techniques improve performance and scalability in distributed environments.

🔀 Distributed Databases & Fragmentation

Distributed database – a collection of data stored on multiple computers that may be geographically
dispersed but appear as a single logical database to users.

Data replication – copies of the same data item are kept at several sites.
Advantages Disadvantages
• Increased availability (fail‑over possible) • Higher storage costs
• Improved performance for read‑heavy • Greater maintenance complexity
workloads
• Enhanced reliability (fault tolerance) • Write operations become more complex
(need to keep copies consistent)
Data fragmentation – a relation is divided into smaller pieces (fragments) that are stored at
different sites.
Advantages Disadvantages
• Faster local data access (queries can be • Added complexity in design and
processed where the data reside) management
 • Enables distributed processing and load • Strong network dependency for
balancing reconstruction
• Supports localized administration • Reconstruction of the original relation may
(site‑specific policies) be costly
Hybrid (mixed) fragmentation – combines horizontal and vertical fragmentation to exploit the
benefits of both. It is useful when access patterns are heterogeneous, providing better
performance for complex queries.

🔐 Concurrency Control Overview

Concurrency‑control protocols generate schedules that satisfy conflict serializability while aiming for high
concurrency, short transaction response times, and ease of implementation.

Key desired properties:

Maximum concurrency – keep many transactions executing simultaneously.
Low transaction latency – minimize waiting time.
Simplicity – protocols should be easy to understand and implement.
Two main families:
1. Timestamp‑based methods – assign a global order to transactions before they enter the system.
2. Lock‑based methods – require a transaction to obtain a lock on a data item before accessing it.

⏱️ Timestamp Ordering Protocol

Transaction timestamps
Each transaction Ti receives a unique, immutable timestamp TS(Ti) when it enters the system.

If TS(Ti) < TS(Tj), then Ti is considered older than j.

Data‑item timestamps
For every data item Q the system maintains:
Timestamp Meaning
W‑timestamp(Q) Largest timestamp of any transaction that has
written Q successfully.
R‑timestamp(Q) Largest timestamp of any transaction that has read
Q successfully.

Read request handling

When Ti requests read(Q):
1. If TS(T ) < W‑timestamp(Q) → the value has been overwritten; Ti aborts.
i ​

2. Otherwise, the read succeeds and R‑timestamp(Q) ← max(R‑timestamp(Q), TS(T )) . i ​

Write request handling

When Ti issues write(Q):
1. If TS(T ) < R‑timestamp(Q) → a younger transaction has already read the old value; Ti aborts.
i ​

2. If TS(T ) < W‑timestamp(Q) → the write would be obsolete; Ti aborts.

i ​

3. If neither condition holds, the write succeeds and W‑timestamp(Q) ←

max(W‑timestamp(Q), TS(T )) . i ​

Thomas Write Rule (enhancement)

Allows obsolete writes (TS(T ) < W‑timestamp(Q)) to be ignored rather than causing aborts.
i ​

Because no later transaction can read a value that will never be produced, ignoring such writes
increases concurrency and can yield view‑serializable schedules that are not conflict‑serializable.

🔒 Lock‑Based Protocols
Lock modes
Mode Symbol Capability
Shared S Multiple transactions may read
simultaneously; no writes.
Exclusive X Single transaction may read &
write; blocks all other accesses.

Lock‑compatibility matrix
Requested \ Held S X
S ✔︎ (compatible) ✖︎

X ✖︎ ✖︎
A transaction must obtain the appropriate lock before accessing a data item.
If the requested lock conflicts with an existing lock, the request is delayed until the conflicting lock
is released.
Graph‑based vs. Validation‑based protocols
Graph‑based: builds a precedence graph of lock requests; does not guarantee serializability on its
own.
Validation‑based: suitable when most transactions are read‑only; validates a transaction after its
read phase before committing writes (see Section “Validation‑Based Protocol”).
🔄 Two‑Phase Locking (2PL) & Variants
Basic 2PL
Two‑Phase Locking – each transaction goes through a growing phase (acquires locks, no releases)
followed by a shrinking phase (releases locks, no new acquisitions).

Guarantees conflict serializability.

Does not guarantee freedom from deadlock or recoverability.
Variants
Variant Key Characteristics
Conservative 2PL All required locks are acquired before the
transaction begins; if any lock is unavailable, all
previously acquired locks are released and the
transaction waits.
Rigorous PL All exclusive locks are held until commit; shared
locks may be released early.
Strict 2PL Both shared and exclusive locks are retained until
commit (a simplified rigorous version).

Properties of 2PL (basic)

Conflict serializable – every schedule produced by 2PL is conflict‑serializable.
View serializable – also guaranteed.
Deadlock possible – cycles in the wait‑for graph may arise.
May cause cascading aborts and non‑recoverable schedules if not combined with additional
rules (e.g., strictness).
Comparative capability table (selected protocols)
Protocol Conflict View Recoverability Cascadeless Deadlock
Serializability Serializability Freedom
Basic 2PL ✔︎ ✖︎ ✖︎ ✖︎ ✖︎

Conservative ✔︎ ✔︎ ✖︎ ✖︎ ✖︎
2PL
Rigorous 2PL ✔︎ ✔︎ ✔︎ ✔︎ ✖︎

Strict 2PL ✔︎ ✔︎ ✔︎ ✔︎ ✖︎

Thomas Write ✖︎ ✔︎ ✖︎ ✔︎ ✔︎
Rule

📊 Multiple Granularity Locking (MGL)

 Multiple granularity locking allows locks at different hierarchical levels (e.g., database → table → page →
record) to improve concurrency while still protecting larger data structures.

Lock modes in MGL

Mode Meaning
IS (Intention‑Shared) Transaction intends to acquire shared locks at a
finer granularity.
IX (Intention‑Exclusive) Transaction intends to acquire exclusive locks at a
finer granularity.
S (Shared) Read‑only access to the item.
X (Exclusive) Read‑write access to the item.

Compatibility matrix
Requested \ Held IS IX S X
IS ✔︎ ✔︎ ✔︎ ✖︎

IX ✔︎ ✔︎ ✖︎ ✖︎

S ✔︎ ✖︎ ✔︎ ✖︎

X ✖︎ ✖︎ ✖︎ ✖︎
A transaction must acquire intention locks on all ancestors of the data item before obtaining the
final S or X lock on the item itself.

📋 Validation‑Based Protocol
Validation‑based concurrency control is effective when most transactions are read‑only, reducing
overhead compared to lock‑based schemes.

Execution phases
1. Read phase – transaction Ti reads required data items and writes updates to private (temporary)
variables; the database remains unchanged.
2. Validation phase – the system checks whether committing Ti would violate serializability (typically
by examining overlapping read/write sets of concurrent transactions).
If the test fails, Ti is aborted.
3. Write phase – for transactions that pass validation, the temporary updates are applied to the
database atomically.
Read‑only transactions skip this phase.
The protocol minimizes locking overhead and is especially suitable for environments with a high
proportion of read‑only workloads.