### Unit I: Introduction to Database Systems

#### Characteristics of Database Approach

The database approach represents a paradigm shift from traditional file-based systems to
a centralized, integrated method of data management. One of the primary characteristics
is data sharing, where multiple users and applications can access the same data
simultaneously without redundancy. This is achieved through a Database Management
System (DBMS), which acts as an intermediary, ensuring controlled access and
consistency. Another key feature is data independence, which separates the logical
structure of data from its physical storage, allowing changes in onewithout a ecting the
other. This promotes flexibility and reduces maintenance costs.

Persistence is another hallmark, as data remains stored even after program execution
ends, unlike transient data in memory. The approach enforces integrity constraints to
maintain accuracy and validity, preventing invalid entries. Security mechanisms, such as
user authentication and authorization, protect sensitive information. Additionally, the
database approach supports complex querying and transaction management, enabling
e icient retrieval and manipulation of large datasets. Overall, these characteristics make
the database approach suitable for modern applications, minimizing data anomalies and
enhancing scalability compared to file systems, where data isolation leads to
inconsistencies and ine iciencies.

#### Data Models

Data models serve as abstract frameworks for representing real-world data, its
relationships, and constraints in a database. They provide a blueprint for designing
databases, ensuring clarity and consistency. Hierarchical data models organize data in a
tree-like structure with parent-child relationships, ideal for one-to-many associations,
such as organizational charts. However, they lack flexibility for complex many-to-many
links.

Network models extend this by allowing multiple parents per child, using sets and pointers
for navigation, as seen in CODASYL systems. While more versatile, they are procedurally
complex. The relational model, proposed by E.F. Codd, uses tables (relations) with rows
and columns, linked via keys, o ering simplicity and mathematical rigor through operations
like joins. Entity-Relationship (ER) models focus on entities, attributes, and relationships at
a conceptual level, aiding design before implementation.

Object-oriented models incorporate concepts like classes, inheritance, and encapsulation

for handling complex data types, such as in multimedia databases. Each model has its
applicability: relational for structured data, object-oriented for applications requiring
polymorphism. Theoretically, data models bridge user requirements and system
implementation, evolving with needs like big data, where NoSQL models (e.g., document or
graph) handle unstructured information.

#### Database System Architecture

Database system architecture is typically conceptualized through the three-schema

architecture, which promotes modularity and data independence. At the internal (physical)
level, it describes how data is stored on hardware, including file structures, indexing, and
access methods like hashing or B-trees. This level optimizes storage e iciency and
performance but is hidden from users.

The conceptual (logical) level abstracts physical details to represent the entire database
structure, encompassing entities, relationships, and constraints using data models like ER
or relational. It serves as a unified view for the organization, independent of storage
mechanics. The external (view) level provides customized subsets of the conceptual
schema for specific users or applications, such as queries or reports, enhancing security
by exposing only relevant data.

Supporting components include the DBMS engine, which handles query processing,
transaction management, and recovery. The data dictionary stores metadata, while
interfaces like SQL facilitate interaction. This architecture ensures scalability, as changes
(e.g., hardware upgrades) at one level minimally impact others, fostering maintainability in
multi-user environments and aligning with ANSI/SPARC standards for standardization.

#### Data Independence

Data independence is the capability to modify database schemas without a ecting
applications or other schemas, crucial for evolving systems. It comprises physical and
logical independence. Physical data independence allows alterations to storage structures
(e.g., changing file organizations from sequential to indexed) without modifying the
conceptual schema or user views. This is facilitated by mappings between physical and
logical levels, shielding applications from hardware changes.

Logical data independence permits changes to the conceptual schema (e.g., adding
attributes or relations) without impacting external views, achieved through view definitions
and mappings. This protects applications from structural evolutions, such as normalization
adjustments.

In theory, data independence reduces redevelopment costs and enhances portability,

contrasting with file systems where data and programs are tightly coupled. It underpins
modern DBMS, enabling seamless upgrades and supporting data abstraction principles.

#### Entity Relationship (ER) Modeling: Entity Types, Relationships, Constraints

Entity-Relationship (ER) modeling is a conceptual tool for database design, representing

real-world objects and their interactions. Entity types are categories of objects with
common attributes, classified as strong (independent, e.g., Employee with unique ID) or
weak (dependent on another, e.g., Dependent linked to Employee). Entities have attributes
like simple (atomic, e.g., Name), composite (e.g., Address with Street and City), or
multivalued (e.g., Phone Numbers).

Relationships connect entity types, defined by degree (binary for two entities, ternary for
three), cardinality (one-to-one, one-to-many, many-to-many), and participation (total or
partial). For instance, a "Works_For" relationship might be one-to-many with total
participation from Employee to Department.

Constraints ensure model integrity, including key constraints (unique identifiers),

referential (linking weak to strong entities), and domain (value restrictions). ER diagrams
use rectangles for entities, diamonds for relationships, and ovals for attributes, aiding
visualization. This model translates to relational schemas, promoting clear design and
reducing ambiguities in complex systems.

### Unit II: Relational Data Model

#### Relational Model Concepts

The relational model, introduced by E.F. Codd in 1970, views data as relations (tables)
comprising tuples (rows) and attributes (columns). Each relation has a schema defining
attribute domains and a unique name. Tuples are unordered, and attributes are atomic,
adhering to the first normal form. Keys, such as superkeys (any unique identifier set) or
candidate keys (minimal superkeys), ensure uniqueness.

The model is based on set theory and predicate logic, allowing declarative querying without
specifying access paths. Integrity rules, like entity (no null primary keys) and referential
(foreign keys matching primaries), maintain consistency. Advantages include simplicity,
data independence, and scalability, making it foundational for modern DBMS like Oracle or
MySQL, though it may struggle with unstructured data.

#### Relational Constraints

Relational constraints enforce rules on data to preserve integrity and prevent anomalies.
Domain constraints limit attribute values to specific types or ranges (e.g., Age as integer
18-65). Key constraints include primary keys (unique, non-null) and unique keys (allowing
nulls).

Referential integrity ensures foreign keys reference existing primary keys or are null,
avoiding dangling references. Entity integrity prohibits nulls in primary keys. Additional
constraints like check (e.g., Salary > 0) or not null further validate data. These are
implemented via DDL in SQL, theoretically supporting Codd's rules for relational
completeness and ensuring reliable operations in multi-table environments.

#### Relational Algebra

Relational algebra is a procedural query language providing operators for manipulating
relations, forming the theoretical basis for SQL. Core operators include selection (σ) for
filtering rows (e.g., σ_{Salary > 50000}(Employee)), projection (π) for selecting columns
(e.g., π_{Name, Dept}(Employee)), and set operations like union (∪) for combining
compatible relations, intersection (∩) for common tuples, and di erence (-) for subtraction.

Join operations merge relations: theta-join (⋈_condition) for conditional links, equi-join for
equality, and natural join (*) for common attributes. Cartesian product (×) combines all
tuples, while division (÷) identifies associations. Aggregate functions extend it for
summaries. Algebra ensures closure (outputs are relations) and equivalence to relational
calculus, enabling optimization in query processing.

#### SQL Queries

SQL (Structured Query Language) is a declarative standard for interacting with relational
databases, divided into DDL, DML, DCL, and TCL. Basic queries use SELECT for retrieval
(e.g., SELECT * FROM Employee WHERE Salary > 50000), with clauses like FROM (tables),
WHERE (conditions), GROUP BY (aggregation), HAVING (group filters), and ORDER BY
(sorting).

Joins include INNER (matching rows), LEFT/RIGHT (including unmatched), and FULL.
Subqueries nest queries (e.g., SELECT Name FROM Employee WHERE Dept = (SELECT
Dept FROM Manager)). DDL commands like CREATE TABLE define structures, ALTER
modifies, DROP removes. DML includes INSERT, UPDATE, DELETE. SQL's power lies in its
expressiveness, supporting views, indexes, and transactions, standardized by ANSI/ISO for
portability.

### Unit III: Database Design

#### Mapping ER/EER Model to Relational Database

Mapping transforms conceptual ER/EER models to relational schemas for implementation.

Strong entities become tables with primary keys from identifiers (e.g., Employee table with
EmpID). Attributes map to columns, multivalued to separate tables with foreign keys.
Binary relationships: One-to-one adds foreign key to one side; one-to-many places foreign
key on many-side; many-to-many creates associative tables with both primaries as
composite key. Weak entities form tables with owner's primary as foreign/partial key. EER
extensions like specialization map to tables per subclass (with superclass key) or single
table with type discriminator. Aggregation treats composites as entities. This mapping
ensures lossless translation, preserving semantics and facilitating normalization.

#### Functional Dependencies

Functional dependencies (FDs) define attribute relationships where a determinant set X

uniquely determines Y (X → Y). Trivial FDs have Y subset of X; full require entire X; partial
allow subsets. Transitive FDs involve chains (X → Y → Z implies X → Z).

Armstrong's axioms (reflexivity, augmentation, transitivity) infer all FDs from a set,
computing closures for equivalence. FDs guide normalization by identifying redundancies;
e.g., in a table with EmpID → Name, Dept, ensuring no anomalies. They form the basis for
design theory, ensuring minimal redundancy.

#### Lossless Decomposition

Lossless decomposition divides a relation into smaller ones reconstructible via natural join
without spurious tuples. It preserves information, tested by ensuring at least one
subschema has a key for the original or common attributes satisfying FDs.

For example, decomposing R(A,B,C) with FD A → B into R1(A,B) and R2(A,C) is lossless as A
is common key. It contrasts lossy decompositions causing data loss. Theoretically, it's
essential for higher normal forms, balancing redundancy reduction with query e iciency.

#### Normal Forms (up to BCNF)

Normal forms are progressive rules to eliminate redundancies via decomposition. 1NF
requires atomic attributes, no repeating groups. 2NF eliminates partial dependencies on
composite keys (non-prime attributes depend on whole key). 3NF removes transitive
dependencies (non-prime on non-prime).

BCNF strengthens 3NF by requiring all determinants as superkeys, addressing anomalies

where candidates are not primaries (e.g., decomposing to eliminate non-superkey
determinants). Each form builds on the previous, with BCNF being stricter, potentially
leading to more tables but better integrity. Normalization trades o with denormalization
for performance in practice.

### Unit IV: Transaction Processing

#### ACID Properties

ACID properties ensure reliable transaction execution in databases. Atomicity treats

transactions as indivisible units—all succeed or none via commit/rollback. Consistency
preserves database invariants, transitioning from one valid state to another.

Isolation makes concurrent transactions appear sequential, hiding intermediate states.

Durability guarantees committed changes persist despite failures, using logs. These
properties, coined by Gray and Reuter, underpin transaction management, enabling robust
applications in banking or e-commerce.

#### Concurrency Control

Concurrency control manages simultaneous transactions to prevent interference, ensuring

serializability (equivalent to serial execution). Techniques include locking (acquiring
shared/exclusive locks), timestamping (ordering by timestamps), and optimistic control
(validating at commit).

Schedules are serial (no interleaving) or serializable (conflict or view). Conflicts arise from
read-write or write-write on same data. Control prevents lost updates, dirty reads, etc.,
maintaining isolation levels like repeatable read. It's vital for multi-user systems, balancing
throughput and correctness.
#### Locking Protocols

Locking protocols use locks to synchronize access: shared (S) for reads, exclusive (X) for
writes, with compatibility (S with S, not X). Two-Phase Locking (2PL) has growing (acquire)
and shrinking (release) phases, ensuring serializability but risking deadlocks.

Strict 2PL releases only at commit, conservative pre-acquires all. Granularity varies from
database to row level for finer control. Protocols enforce isolation, with trade-o s in
performance and deadlock potential.

#### Deadlock Detection and Prevention

Deadlocks occur when transactions cyclically wait for locks, detected via wait-for graphs
(cycles indicate deadlock) or timeouts. Prevention schemes include wait-die (older waits,
younger aborts), wound-wait (older preempts), or no-wait (abort on unavailability).

Resource ordering assigns priorities to avoid cycles. Recovery involves victim selection
(least work) and rollback. Prevention is proactive, detection reactive, both essential for
high-concurrency systems to maintain liveness.

### Unit V: File Structure and Indexing

#### Operations on Files

File operations in DBMS include open/close for access, read/write for data manipulation,
insert/delete/update for records, and search for retrieval. Sequential operations scan
linearly, random use direct access via keys. These are managed by the file manager,
interacting with storage for e iciency, crucial for persistence and performance.

#### File of Unordered and Ordered Records

Unordered (heap) files store records arbitrarily, fast for inserts but slow for searches (full
scans). Ordered (sorted) files maintain sequence by key, enabling binary search but costly
for inserts (shifting required). Heaps suit append-heavy workloads; ordered for query-
intensive, with trade-o s in space and time.

#### Overview of File Organizations

File organizations structure data for access: Sequential for batch processing, direct
(hashing) for random access via key transformation, indexed for combining both. Multilevel
uses hierarchies. Choice depends on operations—sequential for scans, hashed for
equality searches—optimizing I/O costs in secondary storage.

#### Indexing Structures for Files (Primary Index, Secondary Index, Clustering Index)

Indexes are auxiliary structures mapping keys to locations for fast retrieval. Primary indexes
on ordering keys, sparse (one per block), point to sorted files. Secondary on non-key
attributes, dense (per record), for unsorted files, allowing duplicates.

Clustering indexes group similar key records physically, e icient for ranges. All reduce
search time from linear to logarithmic, with overhead in space and updates.

#### Multilevel Indexing Using B and B+ Trees

Multilevel indexing hierarchies minimize accesses for large files. B-trees are balanced,
multi-way trees with ordered keys, allowing variable children, self-balancing via
splits/merges. Nodes hold keys and pointers, leaves data.

B+ trees enhance with all keys in leaves linked for sequential access, internal nodes for
navigation. Both o er O(log n) operations, ideal for disks (minimize seeks), used in DBMS
like MySQL for robust, dynamic indexing.