System Development Module

Part III: Database Systems

SECTION A: FUNDAMENTALS OF DATABASE

Chapter One: Introduction to Database Systems

 1.1 Introduction
o Data vs. Database: Data consists of known facts with implicit
meaning. A Database is a collection of related data (a self-
describing collection of integrated records).
o Scale:
 Personal Database: Simple structure, small size, used by a
single person (e.g., contacts on a phone).
 Enterprise Database: Huge, models information flow of large
organizations.
o DBMS (Database Management System): Software tools for defining,
constructing, manipulating, and sharing databases (e.g., MySQL,
MS Access, SQL Server).
 1.2 Database System versus File System
o File System Limitations: Traditional file processing lacks critical
features, leading to:
 Data redundancy and inconsistency (duplicate data).
 Difficulty in accessing data.
 Data isolation.
 Integrity and Atomicity problems.
 Concurrent access anomalies.
 1.3 Characteristics of the Database Approach
o Self-describing nature: Contains the database and the meta-data
(description of structure/constraints).
o Data Abstraction: Hides implementation details from the user to
provide a conceptual view.
o Insulation: Separation between programs and data (allows
changing data storage without rewriting programs).
o Multiple Views: Supports different perspectives (subsets) of data
for different users.
o Multiuser Transaction Processing: Allows concurrent access and
data sharing.
 1.4 Actors on the scene
 o Database Administrator (DBA): Responsible for authorizing access,
monitoring use, acquiring resources, and coordinating the
database environment.

Chapter Two: Database System Architecture

 2.1 Data Models

o High-level (Conceptual): Close to user perception (e.g., Entity-
Relationship Model).
o Low-level (Physical): Describes storage details on the computer
media (for computer specialists).
o Representational (Implementation): Understandable by users but
close to computer organization (e.g., Relational Model).
 2.2 Schemas and Instances
o Database Schema: The description of the database (design phase,
changes infrequently).
o Database State (Instance/Snapshot): The data in the database at a
specific moment in time.
 2.3 Three-schema Architecture
o Internal Level: Describes physical storage structures and access
paths (Physical Data Model).
o Conceptual Level: Describes the whole database structure
(entities, relationships) for users, hiding physical details.
o External (View) Level: Describes a part of the database for specific
user groups.
 2.4 Data Independence
o Logical Data Independence: Ability to change
the Conceptual schema without changing External schemas or
application programs.
o Physical Data Independence: Ability to change the Internal schema
without changing the Conceptual schema.

Chapter Three: Database Modeling

 3.1 Database Modeling: Using concepts like entities and attributes to

represent data logic.
 3.2 Phases of Database Design
1. Requirement Analysis: Collecting information on data volume and
business needs.
2. Conceptual Database Design: Selecting a model (like ER) to suit
requirements.
 3. Logical Database Design (Data Model Mapping): Translating
conceptual design into a specific implementation model (e.g.,
Tables, Foreign Keys).
4. Physical Design: Implementation of storage structures (indexes,
file organization).
 3.3 ERD (Entity Relationship Diagram)

o Entities: Objects with physical or conceptual existence

(represented by Rectangles).
 Weak Entity: Does not have a key attribute; identified by a
relationship to a Strong Entity.
o Attributes: Properties describing entities.
 Types: Simple (Atomic), Composite (divisible), Multivalued
(double oval), Derived (dashed oval), Key (underlined).
o Relationships: Associations between entities (Diamonds).
 Degree: Unary (1 entity), Binary (2 entities), Ternary (3
entities).
o Cardinality: 1:1 (One-to-One), 1:N (One-to-Many), M:N (Many-to-
Many).
o Participation: Total (double line) vs. Partial.

 3.4 Mapping ER-models to Relational Tables

o Strong Entity: Create a table with all attributes.

o Weak Entity: Create a table; include Owner's Primary Key as
Foreign Key.
o 1:1 Relationship: Include Foreign Key in one relation (preferably
the one with total participation).
o 1:N Relationship: Include Primary Key of the "1" side as a Foreign
Key in the "N" side table.
o M:N Relationship: Create a new "link" table containing Foreign
Keys from both participating entities.

 3.5 Enhanced Entity Relationship (EER) Model

o Subclasses/Superclasses: Handling inheritance and hierarchical

interdependencies.
o Specialization: Dividing a superclass into subclasses based on
distinct attributes.
o Generalization: Combining shared characteristics of classes into a
superclass.
  3.6 & 3.7 The Relational Database Model

o Structure: Collection of relations (tables).

o Terminology: Table (Relation), Row (Tuple), Column (Attribute),
Domain (Atomic values).

 3.8 Relational Constraints

o Domain Constraints: Values must be atomic and match the data

type.
o Key Constraints: Primary Keys must be unique and not null.
o Referential Integrity: Foreign Key values must match a Primary
Key in the referenced table or be null.

Chapter Four: Functional Dependency and Normalization

 4.1 Functional Dependency

(FD): Constraint X→YX→Y means XX uniquely determines YY.
 4.2 Types of FD
o Partial Dependency: A non-prime attribute depends on part of a
composite key.
o Full Dependency: Attribute depends on the entire key.
o Transitive Dependency: A→BA→B and B→CB→C,
therefore A→CA→C.
 4.3 Database Anomalies
o Insertion Anomaly: Cannot add data because the primary key is
unknown.
o Deletion Anomaly: Deleting a record causes unintended loss of
related data.
o Update Anomaly: Updating one record requires updating multiple
duplicates to avoid inconsistency.
 4.4 Normalization (Normal Forms)
o 1NF: Eliminate repeating groups; all attributes must be atomic.
o 2NF: Must be in 1NF + Remove Partial Dependencies (Non-prime
attributes must depend on the full primary key).
o 3NF: Must be in 2NF + Remove Transitive Dependencies (Non-
prime attributes must not depend on other non-prime attributes).

Chapter Five: Record Storage and Primary File Organization

 5.2 Data Types: Exact (CHAR, INT) vs. Approximate (FLOAT, REAL).
  5.3 Storage Categories
o Primary: RAM/Cache (Fast, Volatile, Limited).
o Secondary: HDD/SSD (Slower, Non-volatile, High capacity).
o Tertiary: Optical disks/Tapes (Archival).
 5.4 File Organizations
o Heap (Unordered): Records placed in no specific order
(appended).
o Sorted (Sequential): Records ordered by a sorting key.
o Hashed: Placement determined by a hash function on a key.
 5.5 Indexing
o Dense Index: Entry for every search key value.
o Sparse Index: Entry for only some data records (requires clustered
data).
o Primary Index: On the ordering key field (unique values).
o Clustering Index: On a non-key ordering field (duplicate values
allowed).
o Secondary Index: On a non-ordering field (can be dense).

Chapter Six: Relational Algebra and Calculus

 6.1 Relational Algebra (Procedural):

o Selection (σσ): Selects rows.
o Projection (ππ): Selects columns.

Set Operations: Union (∪∪), Intersection (∩∩), Difference (−−).

o Cross-product (xx): Combines two relations.
o
 6.2 Relational Calculus (Non-procedural): Describes what information is
needed, not how to get it. Includes Tuple Relational Calculus.

Chapter Seven: SQL

 DDL (Definition): CREATE, DROP, ALTER, TRUNCATE, RENAME.

 DML (Manipulation): SELECT, INSERT, DELETE, UPDATE.

SECTION B: ADVANCED DATABASE

Chapter 1: Query Processing and Optimization

 1.5 Why Optimization? To find the most efficient execution strategy

(minimize I/O and CPU) from hundreds of possibilities.
 o Example: A bad query strategy might read 1 million records; an
optimized one might read 50.
 1.7 Query Decomposition:
o Analysis: Syntactic/Lexical check.
o Normalization: Converting WHERE clauses to Normal Forms.
o Semantic Analysis: Ensuring the query makes sense (e.g.,
checking if tables exist).
o Simplification: Detecting redundant logic.
 1.8 Approaches to Optimization
o Heuristic Approach: Uses rules to reorder operations.
 Main Heuristic: Apply operations that reduce the size of
intermediate results (Select/Project) as early as possible.
 Query Trees: Graphical representation of the execution plan.
o Cost-Based Approach: Estimates cost (I/O, Storage, CPU,
Communication) to pick the cheapest plan.
 1.9 Pipelining:
o Evaluates operations simultaneously by passing tuples directly to
the next operation without storing temporary tables.
o Demand Driven (Lazy): Pull model (parent requests tuples).
o Producer Driven (Eager): Push model (child produces tuples into a
buffer).

Chapter 2: Security and Authorization

 2.1 Data Integrity:

o Constraints: Required Data (Not Null), Domain, Entity Integrity
(PK), Referential Integrity (FK), Enterprise Constraints (Business
rules).
 2.2 Security Mechanisms:
o Authentication: Usernames/Passwords.
o Privileges: SELECT, INSERT, UPDATE, DELETE.
o SQL Commands:
 GRANT <privilege> ON <object> TO <user>
 REVOKE
 WITH GRANT OPTION (Allows a user to pass permissions to
others).
o Views: Virtual tables used to hide sensitive data (users access the
view, not the table).
 2.3 Backup and Recovery:
o Disaster Recovery: Planning for fire, water, power failure.
o Record Classification: Vital, Important, Useful, Nonessential.

Chapter 3: Transaction Processing Concepts

  3.1 Transaction Basics: A logical unit of database processing
(Read/Write operations).
 3.2 Transaction States: Active →→ Partially
Committed →→ Committed (or Failed →→ Aborted).
 ACID Properties:
o Atomicity: All or nothing.
o Consistency: Moves DB from one valid state to another.
o Isolation: Transactions do not interfere with each other.
o Durability: Committed changes remain despite failure.
 3.3 Concurrency Problems:
o Lost Update: Two transactions update the same item; one
overwrite is lost.
o Dirty Read: Reading data written by a transaction that later
fails/aborts.
o Incorrect Summary: Aggregating data while it is being updated.
 3.4 Serializability:
o Serial Schedule: Transactions run one after another (safe but
slow).
o Serializable Schedule: Interleaved execution that produces the
same result as a serial schedule.
o Conflict Equivalent: Swapping non-conflicting operations to match
a serial order.
o Testing: Using Precedence Graphs (if cycle exists →→ not
serializable).
 3.5 SQL Levels: Read Uncommitted, Read Committed, Repeatable
Read, Serializable.

Chapter 4: Concurrency Controlling Techniques

 4.2.1 Locking:
o Shared Lock (S): Read-only.
o Exclusive Lock (X): Read and Write.
o Two-Phase Locking (2PL):
1. Growing Phase: Acquire locks, cannot release.
2. Shrinking Phase: Release locks, cannot acquire.
 Deadlock Prevention Protocols:
o Wait-Die: Older transaction waits for younger; Younger transaction
dies if it wants older's lock.
o Wound-Wait: Older transaction "wounds" (aborts) younger;
Younger transaction waits for older.
 4.2.3 Timestamp Ordering:
 o Uses transaction timestamps to serialize execution.
o Thomas's Write Rule: Ignores obsolete write operations (if a
younger transaction has already written the value).
 4.2.5 Validation (Optimistic): Assumes little conflict. Checks serializability
only at commit time (Phases: Read, Validation, Write).
 4.2.6 Multiple Granularity: Locking at different levels (DB, File, Page,
Row) using Intention Locks (IS, IX).

Chapter 5: Database Recovery Techniques

 5.2 Storage Types:

o Volatile: Lost on crash (RAM).
o Non-volatile: Survives crash (Disk).
o Stable: Theoretical storage that survives all failures (mirrored
disks).
 Recovery Strategies:
o Log-Based Recovery:
 Deferred Update: No writing to DB until commit (No Undo
needed).
 Immediate Update: Writes to DB allowed before commit
(Requires Undo).
 Shadow Paging: Maintains two page tables (Current and
Shadow); switches on commit.
 WAL (Write-Ahead Logging): The log record must be written to stable
storage before the data is written to the database disk.
 Checkpoints: Synchronizing the log and DB to reduce recovery time.
 ARIES Algorithm:
o Uses LSN (Log Sequence Number).
o Phases: Analysis, Redo (Repeating History), Undo.
o Handles "Steal/No-Force" buffer management.

Chapter 6: Distributed Databases

 6.1 Concepts:
o DDBMS: Manages distributed data transparently.
o Transparency Types: Location, Naming, Replication,
Fragmentation.
 6.2 Data Storage:
o Replication: Storing copies at multiple sites (increases availability,
slows updates).
o Fragmentation:
 Horizontal: Splitting rows (Selection).
  Vertical: Splitting columns (Projection).
 6.3 System Types:
o Homogeneous: Same DBMS software at all sites.
o Heterogeneous (Federated): Different DBMSs, managed by a
global schema or middleware.
 6.4 Query Processing: Goal is to minimize data transfer over the network
(e.g., using semijoins).
 6.5 Distributed Concurrency Control:
o Primary Site: One site manages all locks (bottleneck risk).
o Voting Method: Distributed locking via majority vote.
 6.6 Client-Server Architecture:
o 2-Tier: Client ↔↔ DB Server.
o 3-Tier: Client ↔↔ Application/Web Server ↔↔ DB Server
(improves security and logic separation).