DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org

· Indexes

DATABASE MANAGEMENT
SYSTEMS
Comprehensive Study Notes — Part II
3NF vs BCNF | Decomposition | Multiple Granularity | Serializability | Validation Protocol | File
Organization | Indexes

1. How 3NF Differs from BCNF

Normalization is the process of organizing a database to reduce repeated data and prevent
update errors. 3NF (Third Normal Form) and BCNF (Boyce-Codd Normal Form) are two levels
of normalization. Both deal with functional dependencies, but they have a key difference in what
they allow.

What is a Functional Dependency?

A functional dependency A → B means that if two rows have the same value for A, they must
also have the same value for B. A is called the determinant and B is the dependent attribute.

What is a Candidate Key?

A candidate key is a minimal set of attributes that can uniquely identify each row in a table. A
table may have more than one candidate key, but only one is chosen as the primary key.

3NF — Third Normal Form

A table is in 3NF if it satisfies the following: for every functional dependency X → Y in the table,
either X is a superkey (contains a candidate key), OR Y is a prime attribute (part of some
candidate key).

In simple words, 3NF allows a non-key attribute to determine another non-key attribute, as long
as the dependent attribute is part of a candidate key. This is the exception 3NF makes.

Example: Consider the table: Enrollment(StudentID, CourseID, InstructorID, InstructorPhone)

Page 1 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

Functional dependencies:
• (StudentID, CourseID) → InstructorID [composite key determines instructor]
• InstructorID → InstructorPhone [instructor determines phone]

The second dependency InstructorID → InstructorPhone is a problem because InstructorID is

not a superkey. However, 3NF still accepts this table if InstructorID happens to be part of some
candidate key. If it is not, the table violates 3NF.

BCNF — Boyce-Codd Normal Form

A table is in BCNF if it satisfies: for every functional dependency X → Y in the table, X must be
a superkey. No exceptions are allowed.

BCNF is stricter than 3NF. It removes every case where a non-superkey attribute determines
another attribute, even if the dependent attribute is prime.

Example: Consider the table: CourseAllocation(Student, Course, Instructor)

Rules:
• One instructor teaches only one course
• One student can enroll in a course taught by only one instructor

Functional dependencies:
• (Student, Course) → Instructor
• Instructor → Course

Candidate keys: (Student, Course) and (Student, Instructor)

The dependency Instructor → Course violates BCNF because Instructor alone is not a superkey
(it cannot uniquely identify a row). However, this table is in 3NF because Course is a prime
attribute (part of the candidate key (Student, Course)).

Key Difference: The Trade-Off

Feature 3NF BCNF
Strictness Less strict More strict
Rule Superkey OR prime attribute Superkey only — no
exceptions
Allows non-superkey Yes, if dependent is prime Never
determinants?
Lossless decomposition Always possible Always possible

Page 2 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

Dependency preservation Always preserved May NOT be preserved

Redundancy Some redundancy may Less redundancy
remain
Used when Dependency preservation Maximum data integrity
needed needed

Why BCNF May Lose Dependency Preservation

When we decompose a table to achieve BCNF, some functional dependencies may no longer
be checkable within a single table. We may need to join tables to verify them, which increases
complexity.

This is the main reason 3NF is sometimes preferred over BCNF in practice — 3NF guarantees
that all functional dependencies are preserved after decomposition, while BCNF does not.

Summary:
3NF makes one exception: it allows non-superkey determinants if the result is a prime
attribute. BCNF makes no exceptions — every determinant must be a superkey. BCNF is
stronger but may sacrifice dependency preservation.

Page 3 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

2. Properties of Decompositions
Decomposition is the process of breaking a large table (relation) into two or more smaller tables
to remove redundancy and fix anomalies. However, not every decomposition is good. A good
decomposition must satisfy certain important properties.

Why Do We Need Decomposition?

When a table is not in a good normal form (like 3NF or BCNF), it may have problems such as:
• Insertion anomaly: Cannot add data without adding unrelated data
• Deletion anomaly: Deleting one fact accidentally deletes another
• Update anomaly: Changing one value requires updating many rows
Decomposition breaks the table into smaller parts that avoid these problems. But the
decomposition must be done carefully.

Property 1: Lossless Join Decomposition

A decomposition is lossless if we can reconstruct the original table by joining the decomposed
tables without gaining any extra (false) rows. No information is lost and no fake rows are
created.

Example: Original table R(A, B, C) with dependency A → B

Decompose into R1(A, B) and R2(A, C)
Original R: R1(A,B): R2(A,C):
A B C A B A C
1 x p 1 x 1 p
1 x q 2 y 1 q
2 y r 2 r

R1 JOIN R2 on A = Original R → Lossless!

A decomposition is lossy if the join produces extra rows that were not in the original table. This
is dangerous because it creates incorrect query results.

Rule for Lossless Join:

For a binary decomposition R into R1 and R2, the join is lossless if the common attributes of
R1 and R2 form a superkey of either R1 or R2.

Page 4 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

Property 2: Dependency Preservation

A decomposition preserves dependencies if every functional dependency from the original table
can still be checked within one of the decomposed tables — without needing to join them.

If a dependency is split across two tables, it cannot be enforced directly. Every time we insert or
update data, we would need to join the tables to verify the constraint, which is slow and error-
prone.

Example: Original table R(A, B, C) with dependencies: A → B, B → C

Decompose into R1(A, B) and R2(B, C)
• R1 contains A → B ✓ (can be checked in R1)
• R2 contains B → C ✓ (can be checked in R2)
Both dependencies are preserved — this is a good decomposition.

Now consider decomposing into R1(A, B) and R2(A, C). The dependency B → C is split —
neither R1 nor R2 contains both B and C together. This decomposition does NOT preserve B →
C.

Property 3: No Redundancy
The decomposed tables should not contain repeated data. Each fact should be stored in exactly
one place. If the same data appears in multiple tables after decomposition, updates will require
changing multiple tables, leading to inconsistency.

A good decomposition ensures each sub-table is in a higher normal form (3NF or BCNF), which
naturally reduces redundancy.

Property 4: Minimal Loss of Information

A good decomposition should not lose any meaningful information. Every attribute from the
original table must appear in at least one sub-table. No original data should be dropped or
ignored during decomposition.

Summary of Properties
Property What It Means Why It Matters
Lossless Join Original table can be Prevents false rows and data
reconstructed by joining sub- corruption
tables
Dependency Preservation All FDs can be checked Ensures constraints can be
within a single sub-table enforced easily
No Redundancy Each fact stored only once Prevents update and deletion

Page 5 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

across sub-tables anomalies

Minimal Loss No original attribute or data is Keeps all information intact
discarded

Key Fact:
Both lossless join and dependency preservation are always achievable with 3NF
decomposition. BCNF decomposition always gives lossless join but may lose dependency
preservation.

Page 6 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

3. Multiple Granularity
In a database, locking is used to prevent two transactions from conflicting with each other. But
not all locks need to be on individual rows. Sometimes it is more efficient to lock a large group of
data (like a whole table) all at once. This concept is called Multiple Granularity Locking.

Definition
Multiple Granularity refers to a locking scheme where data can be locked at different levels of
size (granularity) — from a single row at the finest level, up to the entire database at the
coarsest level. The word 'granularity' means the size of the unit being locked.

Granularity Hierarchy
The database is organized in a tree-like hierarchy:
DATABASE
|
TABLE (Relation)
|
PAGE (Disk Block)
|
ROW (Tuple / Record)

• Database: Locking the entire database. No other transaction can access anything.
• Table: Locking a whole table. All rows in that table are locked.
• Page: Locking a disk block (a group of rows stored together on disk).
• Row (Tuple): Locking a single record. The finest level of locking.

Why Multiple Granularity?

Consider a transaction that needs to update all 10 million rows in a table. If it locks each row
individually, it must perform 10 million lock operations — very slow. Instead, it can lock the
entire table with one lock operation — much faster.

On the other hand, a transaction that only needs to update 3 specific rows should not lock the
whole table — that would block all other transactions unnecessarily. It should lock only those 3
rows.

Multiple Granularity gives the flexibility to choose the right level of locking based on what the
transaction needs.

Page 7 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

Types of Locks Used

Regular shared (S) and exclusive (X) locks are used at leaf level. But to manage locking across
multiple levels, special intention locks are introduced:

Lock Type Symbol Meaning

Intention Shared IS Transaction intends to place
S lock on some child node
Intention Exclusive IX Transaction intends to place
X lock on some child node
Shared S Transaction reads the entire
node and all its children
Shared + Intention Exclusive SIX Transaction reads
everything, but will write to
some children
Exclusive X Transaction writes to the
entire node and all its
children

How It Works — Example

Scenario: Transaction T1 wants to update a specific row in Table A.
1. T1 acquires IS lock on the Database (signals intent below)
2. T1 acquires IS lock on Table A (signals intent below)
3. T1 acquires IS lock on the Page containing the row
4. T1 acquires X lock on the specific Row

Scenario: Transaction T2 wants to read all rows in Table A.

5. T2 acquires IS lock on the Database
6. T2 acquires S lock on Table A (locks the whole table for reading)
Now if T1's X lock on a row conflicts with T2's S lock on the whole table, the system detects the
conflict through the intention locks already placed at the table level.

Lock Compatibility Matrix

IS IX S SIX X
IS ✓ ✓ ✓ ✓ ✗
IX ✓ ✓ ✗ ✗ ✗
S ✓ ✗ ✓ ✗ ✗
SIX ✓ ✗ ✗ ✗ ✗

Page 8 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

X ✗ ✗ ✗ ✗ ✗

Advantages of Multiple Granularity

• Reduces lock overhead for bulk operations (lock one table instead of millions of rows)
• Allows fine-grained locking for short targeted operations
• Increases concurrency — different transactions can work on different parts of the same
table

Key Point:
Intention locks are placed top-down (from database to row) before the actual lock. Locks
are released bottom-up (from row back to database). This protocol ensures no two
conflicting locks exist anywhere in the hierarchy.

Page 9 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

4. Serializability
When many transactions run at the same time (concurrently), their operations get mixed
together. The final result of this mixed execution must be correct — meaning it should be as if
the transactions ran one after another, not mixed. This idea is called Serializability.

Definition
A schedule is a sequence of operations (reads and writes) from multiple transactions. A
schedule is said to be serializable if its result is equal to the result of some serial execution of
the same transactions. A serial execution means transactions run completely one after another
with no overlapping.

Serial vs Concurrent Schedule

Serial Schedule (T1 then T2): Concurrent Schedule (Mixed):
T1: Read A T1: Read A
T1: Write A T2: Read A
T1: Read B T1: Write A
T1: Write B T2: Write A
T2: Read A T1: Read B
T2: Write A T2: Read B
T1: Write B
T2: Write B

A serial schedule is always correct but slow — all other transactions wait. A concurrent
schedule is faster, but may give wrong results if not managed properly.

Types of Serializability

1. Conflict Serializability
Two operations conflict if they are from different transactions, operate on the same data item,
and at least one is a write.
• Read-Write conflict: One reads while another writes the same item
• Write-Read conflict: One writes while another reads the same item
• Write-Write conflict: Both write to the same item

A schedule is conflict serializable if we can swap non-conflicting operations to convert it into a

serial schedule.

Page 10 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

Precedence Graph (Conflict Graph): Used to test conflict serializability.

7. Create a node for each transaction
8. Draw an edge from Ti to Tj if an operation in Ti conflicts with and comes before an
operation in Tj
9. If the graph has no cycle, the schedule is conflict serializable

Schedule: T1 reads A, T2 writes A, T2 reads B, T1 writes B

T1 reads A, then T2 writes A → Edge: T1 → T2

T2 reads B, then T1 writes B → Edge: T2 → T1

Precedence Graph: T1 → T2 → T1 (CYCLE!)

This schedule is NOT conflict serializable.

2. View Serializability
A schedule is view serializable if it is view equivalent to some serial schedule. View equivalence
has three conditions:
10. Initial reads: If Ti reads initial value of A in the serial schedule, Ti must read initial value
of A in the concurrent schedule too.
11. Updated reads: If Ti reads a value written by Tj in one schedule, the same must happen
in the other.
12. Final writes: The last write to every data item must be done by the same transaction in
both schedules.

Every conflict serializable schedule is also view serializable, but not the other way around. View
serializability is harder to test (NP-complete problem), so conflict serializability is used in
practice.

Type Test Method Practical Use

Conflict Serializable Precedence graph — no Widely used in databases
cycle
View Serializable Check 3 view equivalence Rarely used — too complex
conditions to test

Key Point:
All serial schedules are serializable. The goal of concurrency control is to allow concurrent
execution while guaranteeing the result equals some serial execution.

Page 11 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

5. Validation-Based Protocol (Optimistic Concurrency

Control)
Validation-Based Protocol is a concurrency control method that assumes conflicts between
transactions are rare. Instead of locking data and blocking other transactions, it lets transactions
run freely and only checks for conflicts just before the transaction finishes (commits). This is
also called Optimistic Concurrency Control (OCC).

Why Optimistic?
Lock-based methods are pessimistic — they assume conflicts will happen and block
transactions in advance. Validation-based methods are optimistic — they assume conflicts are
unlikely, let transactions run without restrictions, and only validate at the end. If no conflict is
found, the transaction commits. If a conflict is found, the transaction is rolled back and restarted.

Three Phases of Validation-Based Protocol

Phase 1: Read Phase

The transaction reads all data it needs from the database. All write operations are performed
only on a local copy (temporary copy in memory) — not directly on the actual database. No
locks are taken at this stage.

Each transaction keeps track of:

• Read Set: All data items it has read
• Write Set: All data items it intends to write

Transaction T:
Read: A = 1000 (from actual DB, store locally)
Compute: A = A - 200 = 800
Write: A = 800 (stored only in local/temp copy, NOT in DB yet)

Phase 2: Validation Phase

Before the transaction writes its results to the actual database, the system checks whether any
conflict occurred during the transaction's lifetime. Each transaction is assigned a timestamp
when it enters validation.

For a transaction Ti to pass validation, for all previously committed transactions Tj (where TS(Tj)
< TS(Ti)), one of the following must be true:

Page 12 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

13. Tj completes all three phases before Ti starts its Read Phase → No overlap at all, no
conflict possible.
14. Tj completes its Write Phase before Ti starts its Write Phase, AND the Write Set of Tj
does not overlap with the Read Set of Ti → Ti did not read anything that Tj modified.
15. Tj completes its Read Phase before Ti completes its Read Phase, AND the Write Set of
Tj does not overlap with the Read or Write Sets of Ti → No conflict.

If none of these conditions hold, Ti fails validation and is rolled back.

T1 (older): Read Set = {A, B}, Write Set = {A}

T2 (newer): Read Set = {A, C}, Write Set = {C}

Check: T1's Write Set {A} overlaps with T2's Read Set {A}?
→ YES, A is in both. T2 must be rolled back!

Phase 3: Write Phase

If validation succeeds (no conflicts found), the transaction writes all its local changes to the
actual database. The transaction is then committed and the changes become permanent.

If validation fails, all local changes are discarded. The transaction is restarted from Phase 1.

Summary of Three Phases

Phase What Happens Database Modified?
Read Phase Read actual DB, compute No
changes in local copy
Validation Phase Check if any conflict with No
other transactions
Write Phase Write local changes to actual Yes
DB (only if valid)

Advantages
• No locking — transactions never wait for locks, so there are no deadlocks
• High concurrency — many transactions can run simultaneously
• Best performance when conflicts are rare (read-heavy systems)

Disadvantages
• Wasted work: If a transaction fails validation after doing a lot of work, it must restart from
scratch

Page 13 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

• Starvation: A long transaction may keep failing validation and restarting (called livelock)
• Not efficient when conflicts are frequent — constant restarts degrade performance

Best Used For:

Systems with mostly read operations and few writes, such as reporting systems, analytics
databases, or online catalogs where conflicts are rare.

Page 14 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

6. Types of File Organization

File organization refers to the way records (data) are physically stored on disk. The way data is
arranged affects how fast it can be found, inserted, deleted, or updated. Choosing the right file
organization depends on the type of queries the database needs to handle.

1. Heap File Organization (Unordered)

In heap file organization, records are stored in no particular order. New records are simply
placed at the end of the file (or in any empty space). This is the simplest storage method.

• Insertion: Very fast — just add the record at the end

• Search: Slow — must scan every record one by one (full table scan)
• Deletion: Record is marked as deleted but space is not immediately freed

Example: Student records stored as they are enrolled — no particular order.

Block 1: [Aarav, 101] [Zara, 205] [Bhanu, 310]
Block 2: [Charan, 415] [Esha, 102] [Divya, 220]
No sorting — records appear in insertion order

Best for: Bulk loading, write-heavy systems, or small tables where full scans are acceptable.

2. Sequential (Sorted) File Organization

Records are stored in sorted order based on a chosen key field (called the ordering field or sort
key). All records are physically arranged in this order on disk.

• Search: Efficient — binary search can be used, reducing search time

• Range queries: Very fast — records in a range are stored together
• Insertion: Slow — new records must be inserted in the correct sorted position, requiring
shifting of other records

Example: Employee records sorted by EmployeeID:

Block 1: [101, Aarav] [105, Bhanu] [110, Charan]
Block 2: [115, Divya] [120, Esha] [125, Farhan]
Records are in sorted order of EmployeeID

Best for: Read-heavy systems with frequent range queries and sorted access.

Page 15 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

3. Hash File Organization

A hash function is applied to the key field of each record. The result (hash value) determines
which disk block (called a bucket) the record is stored in. Records with the same hash value go
to the same bucket.

• Search: Very fast for exact match queries — apply hash and go directly to the bucket
• Range queries: Not supported — records are spread randomly across buckets
• Insertion: Fast — apply hash and insert into the bucket

Example: Hash function: StudentID mod 3

StudentID 101 → 101 mod 3 = 2 → Bucket 2
StudentID 102 → 102 mod 3 = 0 → Bucket 0
StudentID 105 → 105 mod 3 = 0 → Bucket 0
StudentID 106 → 106 mod 3 = 1 → Bucket 1

Best for: Exact match lookups, such as finding a record by primary key.

4. Clustered File Organization

Related records from different tables that are often accessed together are stored in the same
disk block. This is used when two tables are frequently joined.

Block 1: [Dept 10, Aarav] [Dept 10, Bhanu] [Dept 10, Charan]
Block 2: [Dept 20, Divya] [Dept 20, Esha]
Employees in the same department are stored together

Best for: Queries that join two tables on the same key (e.g., Department JOIN Employee).

5. Indexed Sequential File Organization (ISAM)

Records are stored in sorted order (sequential), and a separate index structure is maintained to
allow fast direct access. Combines the benefits of sorted order (for range queries) and index (for
direct access).
Best for: Mixed workloads needing both range scans and direct lookups.

Comparison of File Organizations

Type Search Insert Range Query Space
Heap Slow (full scan) Fast Slow Compact
Sequential Fast (binary) Slow Fast Compact
Hash Very Fast Fast Not Supported Extra buckets
Clustered Fast (for joins) Moderate Fast Good

Page 16 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

ISAM Fast Moderate Fast Index overhead

Page 17 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

7. Primary and Secondary Indexes

An index is a data structure that allows the database to find records quickly without scanning
every row. It works like a book's index — instead of reading every page to find a topic, you look
it up in the index and jump to the right page.

What is an Index?
An index is a separate, smaller file that contains key values and pointers (block addresses)
pointing to where the actual records are stored on disk. When a query searches for a specific
value, the database uses the index to find the location and goes directly to it.

Primary Index
A primary index is built on the ordering field of an ordered (sorted) file. The file is already sorted
by a specific key (called the ordering key), and the index is based on that same key.

Primary indexes are also called dense or sparse:

• Dense Index: One index entry for every record in the file
• Sparse Index: One index entry for every block (disk page) of records

Example: Employee table sorted by EmployeeID:

Data File (sorted by EmpID):

EmpID Name Department Salary
101 Aarav HR 45000
105 Bhanu IT 60000
110 Charan IT 55000
115 Divya Finance 70000
120 Esha Finance 68000
125 Farhan HR 47000

Primary Index File (Sparse — one entry per block, assuming 3 records per block):
Index Key (EmpID) Pointer to Block
101 Block 1 (contains 101, 105, 110)
115 Block 2 (contains 115, 120, 125)

Page 18 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

To find Employee with EmpID = 120: Look at index → 115 points to Block 2 → scan Block 2 →
find 120. Only 1 disk block read instead of scanning all blocks.

Properties of Primary Index

• Built on the physical ordering field of the file
• Usually sparse — one entry per block, so the index is small
• Only one primary index per table (because data can only be physically sorted one way)
• Very fast for searches on the ordering key

Secondary Index
A secondary index is built on a non-ordering field — a field that is NOT used to physically sort
the records. It allows fast access to records based on a field other than the primary sort key.

Since the data file is not sorted by this field, the secondary index must be dense — it has one
entry for every single record (not just one per block), because records with the same secondary
key value may be scattered across many blocks.

Example: Building a secondary index on Department for the same Employee table:

Data File (still sorted by EmpID — Department is unsorted):

Block EmpID Name Department
Block 1 101 Aarav HR
Block 1 105 Bhanu IT
Block 1 110 Charan IT
Block 2 115 Divya Finance
Block 2 120 Esha Finance
Block 2 125 Farhan HR

Secondary Index File (on Department):

Index Key (Department) Pointers to Records
Finance Block 2 Row 1, Block 2 Row 2
HR Block 1 Row 1, Block 2 Row 3
IT Block 1 Row 2, Block 1 Row 3

To find all HR employees: Look at secondary index under 'HR' → pointers say Block 1 Row 1
and Block 2 Row 3 → go directly to those locations. No full scan needed.

Page 19 of 20
DBMS Study Notes — Part II | 3NF/BCNF · Decomposition · Granularity · Serializability · Validation · File Org
· Indexes

Bucket Mechanism for Secondary Index

When multiple records share the same secondary key value (e.g., many employees in HR), an
intermediate bucket structure is used. The index points to a bucket, and the bucket contains
pointers to all matching records. This keeps the index file small and structured.
Secondary Index: Bucket: Data File:
HR → [Bucket Ptr] ──────► [Ptr1, Ptr2] ──► Block 1, Row 1 (Aarav)
──► Block 2, Row 3 (Farhan)

Comparison: Primary vs Secondary Index

Feature Primary Index Secondary Index
Built on Ordering key (sort key) Non-ordering key (any other
field)
Density Sparse (one entry per block) Dense (one entry per record)
Number allowed Only one per table Multiple allowed per table
File sorting required Yes — data must be sorted No — data is not sorted by
by this key this key
Index size Small Larger
Access speed Very fast Fast, but slightly slower due
to buckets
Example use Search by EmpID Search by Department,
Name, etc.

Summary:
Primary index is built on the field by which data is physically sorted — one entry per block.
Secondary index is built on any other field — one entry per record. A table can have only
one primary index but many secondary indexes. Both use pointers to locate records quickly
without full table scans.

Page 20 of 20