Database Management System

Schedule

A schedule is the chronological order in which the operations (read, write, commit, abort) of a set of concurrent transactions are executed, preserving the order of operations within each transaction. A serial schedule runs transactions one after another with no interleaving; a non-serial schedule interleaves them.

Serializability

A non-serial schedule is serializable if its effect is equivalent to some serial schedule of the same transactions, so it leaves the database in a consistent state. Serializable schedules give concurrency along with correctness. The two kinds are:

• Conflict serializability: the schedule can be converted into a serial schedule by swapping non-conflicting adjacent operations. Two operations conflict if they belong to different transactions, access the same data item and at least one is a write.
• View serializability: the schedule is view equivalent to a serial schedule (same initial reads, same read-from relationships, same final writes). It is weaker than conflict serializability.

Testing conflict serializability: precedence graph

1. Create a node for each transaction $T_i$.
2. Add a directed edge $T_i\to T_j$ if an operation of $T_i$ conflicts with and precedes an operation of $T_j$ ($R_i(X)$ before $W_j(X)$; $W_i(X)$ before $R_j(X)$; $W_i(X)$ before $W_j(X)$).
3. If the graph has no cycle, the schedule is conflict serializable, and a topological order of the nodes gives an equivalent serial order. If there is a cycle, it is not serializable.

Example: $S$: $R_1(A), W_1(A), R_2(A), W_2(A), R_1(B), W_1(B)$. Conflicts on $A$: $T_1\to T_2$ ($W_1(A)$ before $R_2(A)$). No operation of $T_2$ precedes a conflicting operation of $T_1$ on $B$ (there is none from $T_2$ on $B$). The graph has only the edge $T_1\to T_2$, no cycle, so the schedule is serializable and equivalent to $T_1$ followed by $T_2$.

Advantages of a DBMS over the traditional file system

Additional benefits: backup and recovery, sharing among many users, standards enforcement, faster application development.

Data models

A data model is a collection of concepts for describing data, relationships, semantics and constraints.

1. Entity-Relationship (ER) model: real world described as entities, attributes and relationships, drawn as ER diagrams. Example: entities STUDENT(roll, name) and COURSE(code, title) with relationship ENROLLS.
2. Relational model: data in tables (relations) of rows (tuples) and columns (attributes), linked by keys. Example: Student(Roll, Name, Dept), Course(Code, Title), with Roll and Code as keys. Manipulated by relational algebra/SQL. Most widely used (MySQL, Oracle).
3. Hierarchical model: records in a tree of parent-child (one-to-many) links. Example: Department is the parent of Teachers and Courses. Fast, but many-to-many relationships are hard (IBM IMS).
4. Network model: a graph; a child may have several parents, linked by pointers (sets). Example: a Student is linked to many Courses and a Course to many Students. Flexible, but complex (IDMS).
5. Object-oriented/object-relational model: data stored as objects with attributes, methods, classes and inheritance. Example: class Person with subclass Student.
6. Semi-structured/document and NoSQL models: JSON documents, key-value, column and graph stores, e.g. MongoDB: {"roll":1,"name":"Ram","courses":["DBMS","CN"]}.

Concurrency control

Concurrency control is the set of techniques a DBMS uses to manage the simultaneous execution of transactions so that they do not interfere with each other and the database remains consistent (isolation). Without it, problems arise such as lost update, dirty read (uncommitted data), unrepeatable read and phantom read.

Methods

1. Lock-based protocols: binary locks, shared/exclusive locks, two-phase locking (basic, strict, rigorous).
2. Timestamp-based protocols: each transaction gets a timestamp; conflicting operations are ordered by timestamp (basic timestamp ordering, Thomas write rule).
3. Optimistic (validation-based) control: transactions run without locking and are validated before commit.
4. Multiversion concurrency control (MVCC): keeps several versions of each item so readers do not block writers.
5. Graph-based protocols and multiple granularity locking.

Binary lock versus shared/exclusive lock

Compatibility of shared/exclusive locks: S with S is allowed; S with X, X with S and X with X are not.

Normal form

Normalisation is the process of organising a relation's attributes into smaller well-structured relations to remove redundancy and the insertion, deletion and update anomalies, using functional dependencies (FDs). A normal form is a rule/standard a relation must satisfy to be considered at a given level of normalisation.

Types

• First Normal Form (1NF): all attribute values are atomic (no repeating groups or multivalued attributes). A table with Phone = {9841, 9851} violates it; split into one row per phone.
• Second Normal Form (2NF): in 1NF and no partial dependency: every non-key attribute depends on the whole candidate key. Example: Enroll(StudentID, CourseID, StudentName, Grade) with key (StudentID, CourseID): StudentName depends only on StudentID. Decompose into Student(StudentID, StudentName) and Enroll(StudentID, CourseID, Grade).
• Third Normal Form (3NF): in 2NF and no transitive dependency: non-key attributes do not depend on other non-key attributes. For every FD $X\to A$, either $X$ is a superkey or $A$ is a prime attribute. Example: Emp(EmpID, DeptID, DeptName) with EmpID → DeptID → DeptName; decompose into Emp(EmpID, DeptID) and Dept(DeptID, DeptName).
• Boyce-Codd Normal Form (BCNF): for every non-trivial FD $X\to Y$, $X$ is a superkey. Stronger than 3NF. Example: R(Student, Subject, Teacher) with Teacher → Subject: Teacher is not a key, so decompose into (Teacher, Subject) and (Student, Teacher).
• Fourth NF (4NF): in BCNF and no non-trivial multivalued dependency other than on a superkey.
• Fifth NF (5NF/PJNF): no join dependency that is not implied by the candidate keys.

Lossless-join decomposition

A decomposition of $R$ into $R_1, R_2$ is lossless if the natural join of the parts gives back exactly the original relation, with no lost or spurious tuples:

$R_1 \bowtie R_2 = R$

Condition (binary decomposition): the decomposition is lossless if and only if at least one of these holds, where $F^+$ is the closure of the FDs:

$R_1\cap R_2 \to R_1 \in F^+ \quad\text{or}\quad R_1\cap R_2 \to R_2 \in F^+$

That is, the common attributes must be a key (superkey) of at least one of the parts.

Example: R(A, B, C) with A → B. Decomposing into R1(A, B) and R2(A, C): common attribute A, and A → B so A is a key of R1; the decomposition is lossless. Decomposing into R1(A, B) and R2(B, C): common attribute B determines neither part, so joining may create spurious tuples; it is lossy.

Decomposition into BCNF is always lossless, and 3NF decomposition can be made both lossless and dependency preserving. Lossless join is essential so that normalisation does not lose information.

Data abstraction

Data abstraction is hiding the complex details of how data is stored and maintained and showing users only the information they need. It lets users work with a simple view while the DBMS manages the complicated physical structures. It gives data independence: a change at one level does not need changes at the higher level.

Three levels of abstraction

1. Physical (internal) level: the lowest level. It describes how data is actually stored: files, blocks, indexes, record placement, access paths, compression. Seen by the DBMS and system programmers. Described by the internal schema.
2. Logical (conceptual) level: describes what data is stored and the relationships among them: tables, attributes, data types, keys and constraints, for the whole database. Used by database administrators. Described by the conceptual schema. Example: Student(Roll int, Name varchar(30), Dept varchar(10)).
3. View (external) level: the highest level. Each user group sees only the part of the database relevant to it, as one or more views, hiding the rest and giving security. Example: a library clerk sees only student name and issued books, not fees. Described by external schemas.

Mappings exist between levels. Physical data independence is the ability to change the physical schema without altering the logical schema, and logical data independence is changing the logical schema without changing external views or application programs.

Entity

An entity is a real-world object or thing that can be distinctly identified and about which data is stored. It may be physical (a student, a car) or conceptual (a course, a bank account). It is described by its attribute values. Example: the student with Roll = 1, Name = Ram, Dept = CSIT is one entity.

Entity set

An entity set is the collection of all entities of the same type that share the same attributes, at a point in time. In an ER diagram it is drawn as a rectangle. Example: the set of all students of a college is the entity set STUDENT; the set of all courses is COURSE.

Differences

Entity sets can be strong (having a primary key) or weak (dependent on another entity set). The extension of an entity set changes as entities are added or deleted, while its type (the attributes) is the schema.

The HoD table is created first, because the Courses table refers to it. Dept is the primary key of HoD, so it can be the target of the foreign key in Courses.

CREATE TABLE HoD (
    Dept   VARCHAR(10)  PRIMARY KEY,
    Head   VARCHAR(50)  NOT NULL
);

CREATE TABLE Courses (
    CID     INT          PRIMARY KEY,
    Course  VARCHAR(50)  NOT NULL,
    Dept    VARCHAR(10)  NOT NULL,
    CONSTRAINT fk_courses_dept
        FOREIGN KEY (Dept) REFERENCES HoD(Dept)
        ON DELETE CASCADE
        ON UPDATE CASCADE
);

Constraints used

• Primary key: CID uniquely identifies a course; Dept uniquely identifies a department in HoD.
• Foreign key: Courses.Dept references HoD.Dept.
• Referential integrity: a course can only refer to a department that exists in HoD. Inserting a course with an unknown department is rejected. ON DELETE CASCADE deletes a department's courses when the department row is deleted, and ON UPDATE CASCADE propagates a change of the department code (ON DELETE RESTRICT could be used instead to prevent deletion).
• NOT NULL ensures the mandatory columns have values.

Example: INSERT INTO HoD VALUES ('CSIT','Dr. Sharma'); then INSERT INTO Courses VALUES (101,'DBMS','CSIT'); succeeds, but INSERT INTO Courses VALUES (102,'Physics','PHY'); fails because PHY is not in HoD.

Integrity means the data in the database is correct, consistent and valid: it protects the data from accidental errors and invalid values. Security means protecting the database from unauthorised access, disclosure, modification or destruction, i.e. from deliberate misuse.

Examples

• Integrity: a CHECK (marks BETWEEN 0 AND 100) constraint rejects marks of 150; a foreign key stops an enrolment for a student who does not exist; a primary key stops duplicate roll numbers.
• Security: GRANT SELECT ON Student TO clerk; lets the clerk only read the table; a student cannot update the Marks table; passwords and encrypted storage keep outsiders out.

Both are needed: security without integrity allows an authorised user to enter wrong data, and integrity without security lets anyone corrupt valid data.

Granularity of data items

Granularity is the size of the data item that a lock (or other concurrency control unit) protects. A data item can be a field (attribute value), a record (row), a disk block (page), a whole table (file), or the entire database. The granularities are arranged in a hierarchy: database, tables, pages, records, fields.

Effect on concurrency control

• Coarse granularity (large items such as a table or database): fewer locks to manage, less lock overhead and storage, and simple. But concurrency is low: a transaction locking a whole table blocks all others, even those needing different rows.
• Fine granularity (small items such as a record or field): high concurrency because many transactions can work on different parts of the same table at once. But there are more locks, so more memory, more lock-manager time and a higher chance of deadlock.

Therefore, the choice is a trade-off between concurrency and overhead. A transaction touching many records is best with coarse locks, and one touching a few records with fine locks.

Multiple granularity locking allows both. It uses intention locks: IS (intention shared), IX (intention exclusive) and SIX (shared + intention exclusive). To lock a node in the hierarchy, a transaction first places intention locks on all ancestors from the root down; conflicts at any level are detected by lock compatibility. Locks are released from the leaf upward. This lets the system lock at the best level for each transaction.

Two-phase locking (2PL)

Two-phase locking is a concurrency control protocol that guarantees conflict-serializable schedules. Every transaction acquires and releases locks in two distinct phases:

1. Growing (expanding) phase: the transaction may obtain locks (shared or exclusive) but may not release any lock.
2. Shrinking phase: the transaction may release locks but may not obtain any new lock.

The point at which the transaction obtains its last lock is the lock point. Once the first lock is released, the transaction is in the shrinking phase and cannot lock again. Ordering transactions by lock point gives an equivalent serial order, which proves serializability.

Example: $T_1$: lock-S(A); read(A); lock-X(B); write(B); unlock(A); unlock(B). All locks are taken before any unlock, so it is two-phase.

Variants

• Basic 2PL: as above. It does not prevent cascading rollbacks or deadlocks.
• Strict 2PL: a transaction holds all its exclusive locks until it commits or aborts, which avoids cascading rollbacks.
• Rigorous 2PL: holds all locks until commit/abort, so serialization order equals commit order.
• Conservative 2PL: acquires all locks before starting, which prevents deadlock but is hard to use.

Drawbacks: deadlock is possible (handled by detection, wait-die/wound-wait, or timeouts), starvation can occur, and locking reduces concurrency a little.

Approaches to database recovery

Recovery restores the database to the most recent consistent state after a failure (transaction, system or media failure), ensuring atomicity and durability.

1. Log-based recovery: every change is recorded in a log before it is applied. It has two forms:
   • Deferred database modification: writes are only recorded in the log until the transaction commits, then applied to the database. After a crash, committed transactions are redone; uncommitted ones are ignored (no undo needed).
   • Immediate database modification: updates may be written to the database before commit, after the log record is written (write-ahead logging). After a crash, committed transactions are redone and uncommitted ones undone.
2. Shadow paging: two page tables are kept, the current table and the shadow table. Updates go to new pages through the current table; the shadow table is left unchanged. On commit, the current table becomes the shadow; on failure, the current table is discarded and the shadow used. It needs no log, but causes fragmentation and garbage collection.
3. Checkpoints: periodically the system writes all buffers to disk and records a checkpoint in the log, so recovery only examines transactions active since the last checkpoint.
4. Backup and archival (media recovery): restore from a backup/dump copy and apply the archived log; also ARIES with analysis, redo and undo passes.

What the log must maintain

The log is a sequential file of records, kept on stable storage, which records every update:

• $\langle T_i,\ \text{start}\rangle$: transaction $T_i$ has started.
• $\langle T_i,\ X_j,\ V_1,\ V_2\rangle$: transaction $T_i$ changed data item $X_j$ from old value $V_1$ to new value $V_2$ (the old value is used for undo and the new one for redo).
• $\langle T_i,\ \text{commit}\rangle$: $T_i$ has committed.
• $\langle T_i,\ \text{abort}\rangle$: $T_i$ has aborted.
• $\langle \text{checkpoint}\rangle$ with the list of active transactions.

Each record also holds a unique transaction ID and a log sequence number. Under the write-ahead logging rule, the log record must reach stable storage before the corresponding data change is written to disk and before commit.

Primary key. A primary key is a minimal set of attributes that uniquely identifies every tuple (row) of a relation. It cannot be NULL and cannot repeat. A table has only one primary key (which may be composite).

Uses of a primary key:

• Uniquely identifies each record, so there are no duplicate rows.
• Enforces entity integrity (no NULL in key).
• Provides the fast access path (an index is normally built on it).
• Acts as the target that other tables refer to.

Foreign key. A foreign key is an attribute (or set of attributes) in one relation whose values must match the primary key (or a candidate key) values of another relation, or be NULL. It links two tables.

Example.

CREATE TABLE Department (
  DeptID   INT PRIMARY KEY,
  DeptName VARCHAR(40)
);

CREATE TABLE Student (
  RollNo  INT PRIMARY KEY,
  Name    VARCHAR(40),
  DeptID  INT,
  FOREIGN KEY (DeptID) REFERENCES Department(DeptID)
);

Here DeptID is the primary key of Department and a foreign key in Student. A student can only be given a DeptID that exists in Department.

Role of the foreign key.

• Establishes the relationship between tables (one department has many students).
• Enforces referential integrity: a student cannot refer to a non-existent department; inserting an invalid DeptID is rejected.
• Controls deletion and update of the parent row through actions such as ON DELETE CASCADE, SET NULL or RESTRICT.
• Allows tables to be joined (Student JOIN Department ON Student.DeptID = Department.DeptID) so data is stored once and not repeated, reducing redundancy.

Types of database users and their roles

1. Database Administrator (DBA). Has central control of the DBMS. Defines the schema, grants authorisation and access rights, monitors performance, tunes the system, takes backups and performs recovery, and manages security.
2. Database Designer. Identifies the data to be stored, chooses suitable structures and designs the conceptual and logical schema (ER model, normalisation) in consultation with end users.
3. Application Programmers (System Analysts). Write application programs in languages such as Java, PHP or C++ that use embedded SQL/APIs to access the database. Analysts determine the requirements of end users.
4. End Users. Use the data through the applications:
   • Naive (parametric) users: use prepared forms and menus, e.g. bank tellers, ticket clerks.
   • Casual (sophisticated) users: write ad hoc queries in SQL, e.g. managers, analysts.
   • Standalone users: maintain personal databases using ready-made packages.
5. Tool developers / DBMS system programmers. Build the DBMS tools, design software, report generators and the DBMS itself.

Data independence

Data independence is the ability to change the schema at one level of the three-schema architecture without having to change the schema at the next higher level.

• Physical data independence: the internal (physical) schema can be changed without changing the conceptual schema or application programs. Example: moving a file to another disk, changing from heap file to B+-tree index, or changing the file organisation does not require rewriting the STUDENT(Roll, Name, Address) queries.
• Logical data independence: the conceptual schema can be changed without changing external views or application programs. Example: adding a new attribute Email to STUDENT does not affect an existing program that uses only Roll and Name.

Logical independence is harder to achieve than physical independence because applications depend strongly on the logical structure.

Components of an ER diagram

1. Entity: a real-world object that can be distinguished from others (e.g. Student, Book). An entity set is a collection of similar entities.
2. Attribute: a property describing an entity or relationship (e.g. Name, ISBN).
3. Relationship: an association among entities (e.g. a Member borrows a Book).
4. Keys, cardinality and participation constraints that describe how entities take part in relationships.

Symbols used and their function

ER diagram for a college library

Entities and attributes:

• MEMBER(<u>MemberID</u>, Name, Address, Phone, Type)
• BOOK(<u>ISBN</u>, Title, Publisher, Year, Price)
• AUTHOR(<u>AuthorID</u>, Name)
• PUBLISHER(<u>PubID</u>, Name, Address)
• STAFF(<u>StaffID</u>, Name)

Relationships:

• MEMBER borrows BOOK (M : N), with attributes IssueDate, DueDate, ReturnDate.
• AUTHOR writes BOOK (M : N).
• PUBLISHER publishes BOOK (1 : N), total participation of BOOK.
• STAFF issues the loan (1 : N).

 [AUTHOR] M---<writes>---N [BOOK] N---<published by>---1 [PUBLISHER]
                            |
                            | M
                        <borrows>(IssueDate, DueDate, ReturnDate)
                            | N
                         [MEMBER]

Mapped to tables: MEMBER, BOOK(ISBN, Title, ..., PubID), AUTHOR, WRITES(AuthorID, ISBN), BORROWS(MemberID, ISBN, IssueDate, DueDate, ReturnDate).

Deadlock. A deadlock is a situation in which two or more transactions are each waiting for a lock held by another transaction in the set, so none of them can proceed.

Example: T1 holds a lock on A and requests B; T2 holds a lock on B and requests A. Both wait forever.

Handling: prevention (wait-die, wound-wait, conservative 2PL), detection (wait-for graph; a cycle means deadlock; abort a victim transaction) and timeouts.

Starvation. Starvation occurs when a transaction waits indefinitely because other transactions keep getting the resources (locks) it needs, or because it is repeatedly chosen as a deadlock victim, although the system as a whole is not deadlocked. It is avoided with a first-come-first-served lock queue, priority that increases with waiting time, and by not always choosing the same victim.

Timestamp-based protocol

Each transaction $T_i$ gets a unique timestamp $TS(T_i)$ when it starts (older transaction = smaller timestamp). The protocol orders conflicting operations in timestamp order, so the schedule is equivalent to the serial schedule in timestamp order, and no locks are used (so no deadlock).

For each data item $Q$ the system keeps:

• $R\text{-}TS(Q)$: largest timestamp of any transaction that successfully read $Q$.
• $W\text{-}TS(Q)$: largest timestamp of any transaction that successfully wrote $Q$.

Read($Q$) by $T_i$

• If $TS(T_i) < W\text{-}TS(Q)$: $T_i$ would read an already overwritten value, so reject and roll back $T_i$ (restart with a new timestamp).
• Otherwise, execute the read and set $R\text{-}TS(Q)=\max(R\text{-}TS(Q), TS(T_i))$.

Write($Q$) by $T_i$

• If $TS(T_i) < R\text{-}TS(Q)$: a later transaction already read the old value, so reject and roll back $T_i$.
• If $TS(T_i) < W\text{-}TS(Q)$: $T_i$ is trying to write an obsolete value, so reject and roll back (Thomas' write rule would instead just ignore the write).
• Otherwise, execute the write and set $W\text{-}TS(Q)=TS(T_i)$.

Properties: guarantees conflict serializability and is deadlock free, but may cause cascading rollbacks and starvation of a transaction that is repeatedly restarted.

Relationship. A relationship is an association among two or more entities. For example, the student Ram enrolls in the course DBMS.

Relationship set. A relationship set is a collection of relationships of the same type. Formally, if $E_1, E_2, \dots, E_n$ are entity sets, a relationship set $R$ is a subset of

$\{(e_1, e_2, \dots, e_n) \mid e_1 \in E_1, e_2 \in E_2, \dots, e_n \in E_n\}$

and each $(e_1,\dots,e_n)$ is a relationship instance. In an ER diagram the relationship set is drawn as a diamond.

Example. Entity sets STUDENT = {S1, S2, S3} and COURSE = {C1, C2}. The relationship set ENROLLS = {(S1,C1), (S1,C2), (S2,C1), (S3,C2)}. Each pair is one relationship; the whole set is the relationship set.

A relationship set may have descriptive attributes (e.g. Grade on ENROLLS), a degree (binary, ternary), and cardinality (1:1, 1:N, N:M). The number of entity sets in it is its degree; here the degree is 2 (binary).

We must join the three relations through TID and SID and select the school named "ABC".

SELECT T.TName, S.SName, S.SPhone
FROM   TEACHER T
JOIN   SCHOOL_TEACHER ST ON T.TID = ST.TID
JOIN   SCHOOL S          ON S.SID = ST.SID
WHERE  S.SName = 'ABC';

Equivalent form using the WHERE clause for the joins:

SELECT TName, SName, SPhone
FROM   TEACHER, SCHOOL, SCHOOL_TEACHER
WHERE  TEACHER.TID = SCHOOL_TEACHER.TID
  AND  SCHOOL.SID  = SCHOOL_TEACHER.SID
  AND  SName = 'ABC';

The query returns one row for every teacher who teaches in school ABC, along with the school's name and phone number.

Integrity. Database integrity means the accuracy, consistency and validity of the data stored in the database. Integrity constraints are rules that the DBMS enforces so that only correct data enters the database and that changes do not destroy consistency.

Types of integrity

1. Domain integrity. Values of an attribute must come from its defined domain (data type, range, format, NOT NULL, CHECK). Example: Age INT CHECK (Age >= 0).
2. Entity integrity. The primary key of a relation cannot be NULL and must be unique, so each row can be identified. Example: RollNo in STUDENT.
3. Referential integrity. A foreign key value must either be NULL or match an existing primary key value in the referenced table. Example: Student.DeptID must exist in Department.DeptID.
4. Key integrity (uniqueness). Candidate keys declared UNIQUE must not repeat.
5. User-defined (business) integrity. Application-specific rules enforced by assertions, triggers or stored procedures. Example: a withdrawal must not make the balance negative.

Functional dependency (FD). In a relation $R$, an attribute set $Y$ is functionally dependent on attribute set $X$, written $X \rightarrow Y$, if for any two tuples $t_1, t_2$

$t_1[X] = t_2[X] \;\Rightarrow\; t_1[Y] = t_2[Y]$

That is, the value of $X$ uniquely determines the value of $Y$. Example: in STUDENT(Roll, Name, Dept), $Roll \rightarrow Name$ because one roll number gives exactly one name.

Trivial functional dependency. $X \rightarrow Y$ is trivial if $Y \subseteq X$. It always holds. Example: $\{Roll, Name\} \rightarrow Roll$ and $Roll \rightarrow Roll$.

Non-trivial functional dependency. $X \rightarrow Y$ is non-trivial if $Y \not\subseteq X$, that is, $Y$ contains at least one attribute not in $X$. Example: $Roll \rightarrow Name$.

If additionally $X \cap Y = \emptyset$, it is called completely non-trivial. Only non-trivial dependencies are used in normalisation, since trivial ones give no information about the data.

Join (theta / equi join), $R \bowtie_{\theta} S$. The join combines tuples of two relations that satisfy a given condition $\theta$. It is the selection of the Cartesian product:

$R \bowtie_{\theta} S = \sigma_{\theta}(R \times S)$

With an equality condition it is an equi-join; both join columns appear in the result (so the common attribute appears twice).

Natural join, $R \bowtie S$. Natural join automatically joins on all attributes with the same name in both relations, tests equality on them, and keeps only one copy of the common attributes. No condition is written.

Example. EMP(EID, Name, DID) and DEPT(DID, DName).

• Equi-join: $EMP \bowtie_{EMP.DID = DEPT.DID} DEPT$ gives the columns (EID, Name, EMP.DID, DEPT.DID, DName), with DID appearing twice.
• Natural join: $EMP \bowtie DEPT$ gives (EID, Name, DID, DName), with DID appearing once.

Checkpoint. A checkpoint is a point in time at which the DBMS forces all modified buffers (dirty pages) and log records currently in main memory to stable storage, and writes a <checkpoint L> record in the log, where $L$ is the list of transactions active at that moment.

Steps:

1. Write all log records in memory to stable storage.
2. Write all modified buffer blocks to the disk.
3. Write a <checkpoint L> record to the log on stable storage.

How it helps recovery. Without checkpoints, after a crash the recovery manager would have to scan the entire log, which is slow, and would redo many transactions that have already been written to disk.

With a checkpoint:

• Transactions that committed before the checkpoint need no redo, because their changes are already on disk.
• The system scans the log backwards only to the most recent checkpoint record and finds the transactions in $L$ and those started after it.
• Transactions that were active at the crash and not committed are undone; those that committed after the checkpoint are redone.

Hence recovery time is reduced and the log before the checkpoint can be discarded or archived. Example: if $T_1$ commits before the checkpoint, $T_2$ is active at the checkpoint and commits before the crash, and $T_3$ is active at the crash, then $T_1$ is ignored, $T_2$ is redone and $T_3$ is undone.

Boyce-Codd Normal Form (BCNF). A relation $R$ is in BCNF if, for every non-trivial functional dependency $X \rightarrow Y$ that holds in $R$, $X$ is a super key of $R$. It is a stricter version of 3NF.

Example. CLASS(Student, Subject, Teacher) with the rules: each teacher teaches only one subject, and a student has one teacher per subject.

FDs: $\{Student, Subject\} \rightarrow Teacher$ and $Teacher \rightarrow Subject$.

Candidate keys: $\{Student, Subject\}$ and $\{Student, Teacher\}$. All attributes are prime, so the relation is in 3NF. However, $Teacher \rightarrow Subject$ has a determinant Teacher that is not a super key, so it violates BCNF.

Decomposition into BCNF:

• TEACHES(Teacher, Subject) with key Teacher
• ENROLL(Student, Teacher) with key (Student, Teacher)

Now every determinant is a key.

Difference between BCNF and 3NF

Every BCNF relation is in 3NF, but not every 3NF relation is in BCNF.

Database Management System (DBMS). A DBMS is software that allows users to define, create, store, retrieve, update and control a database. It sits between users/applications and the stored data, and provides data definition (DDL), manipulation (DML), security, integrity, concurrency control and backup/recovery. Examples: MySQL, Oracle, PostgreSQL, SQL Server.

DBMS architecture (three-schema / ANSI-SPARC architecture)

   User 1      User 2      User 3
     |           |           |
 +---------+ +---------+ +---------+
 | View 1  | | View 2  | | View n  |     EXTERNAL LEVEL
 +----+----+ +----+----+ +----+----+
      \           |           /
       \  external/conceptual mapping
        +-------------------+
        |  Conceptual schema |           CONCEPTUAL LEVEL
        +---------+---------+
                  | conceptual/internal mapping
        +---------+---------+
        |  Internal schema   |           INTERNAL LEVEL
        +---------+---------+
                  |
           [ Physical database ]

1. External (view) level: how individual users see the data; each user group has its own view showing only the relevant part. Provides security and simplicity.
2. Conceptual (logical) level: describes the whole database for the community of users: entities, attributes, relationships, constraints. It hides physical storage details.
3. Internal (physical) level: describes how data is physically stored: file structures, indexes, access paths, record placement.

The mappings between levels translate requests and results from one level to another.

Data independence. It is the capacity to change the schema at one level without changing the schema at the next higher level.

• Physical data independence: changing the internal schema (e.g. new index or storage device) does not affect the conceptual schema.
• Logical data independence: changing the conceptual schema (e.g. adding an attribute) does not affect external views or applications.

This is made possible by the three-level architecture and its mappings.

Entity. An entity is a real-world thing that can be distinctly identified, e.g. a student, a book, a loan. A collection of entities of the same type is an entity set.

Types of entities

1. Strong entity: has its own primary key, e.g. EMPLOYEE(EmpID, Name).
2. Weak entity: has no key of its own, depends on an owner (strong) entity through an identifying relationship; identified by owner key plus a partial key, e.g. DEPENDENT(Name, Age) of an employee.

Reducing an ER diagram to tables

Assume entities EMPLOYEE(EmpID, Name, Address, {Phone}, DOB), DEPARTMENT(DeptID, DName), PROJECT(PID, PName), weak entity DEPENDENT(DepName, Relation), with relationships WORKS_FOR (N:1), MANAGES (1:1), WORKS_ON (M:N, attribute Hours) and a specialization.

1. Strong entity becomes a table with its simple attributes; the key attribute becomes the primary key. Composite attributes are flattened into their component columns. EMPLOYEE(EmpID, Name, Address, DOB)
2. Multivalued attribute becomes a separate table with the owner key plus the attribute, the two forming the primary key. EMP_PHONE(EmpID, Phone)
3. Derived attributes (e.g. Age) are not stored.
4. Weak entity becomes a table including the primary key of its owner as a foreign key; primary key is (owner key + partial key). DEPENDENT(EmpID, DepName, Relation), with EmpID referencing EMPLOYEE.
5. 1 : N relationship: put the primary key of the "one" side as a foreign key in the "many" side table. EMPLOYEE(..., DeptID) for WORKS_FOR.
6. 1 : 1 relationship: place the foreign key in either table, preferably on the side with total participation. DEPARTMENT(DeptID, DName, ManagerID) for MANAGES.
7. M : N relationship: create a new table whose primary key is the combination of both entity keys and which contains the relationship attributes. WORKS_ON(EmpID, PID, Hours)
8. Specialization/generalization: either one table per entity with the superclass key repeated in subclasses, or one table for all with a type attribute.
9. N-ary relationship: a table with the keys of all participating entities.

Result: EMPLOYEE, EMP_PHONE, DEPARTMENT, PROJECT, DEPENDENT, WORKS_ON, each with proper primary and foreign keys.

Normalization. Normalization is the process of organising the attributes and relations of a database by decomposing relations using functional dependencies, so as to reduce redundancy and avoid update, insertion and deletion anomalies. Each step moves the relation to a higher normal form.

Why it is required

• Removes data redundancy and saves storage.
• Avoids insertion anomaly (cannot add data without other data), deletion anomaly (deleting one fact loses another) and update anomaly (must change many rows to update one fact).
• Keeps data consistent and makes the design clearer and easier to maintain.

First Normal Form (1NF). A relation is in 1NF if all attributes hold only atomic (indivisible) values; no repeating groups or multivalued attributes.

Not in 1NF: STUDENT(Roll, Name, Phone) with Roll 1, Ram, {9841, 9851}. In 1NF: rows (1, Ram, 9841) and (1, Ram, 9851), or split into STUDENT(Roll, Name) and PHONE(Roll, Phone).

Second Normal Form (2NF). A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on any candidate key (every non-key attribute depends on the whole key).

Example: ENROLL(Roll, CourseID, StudentName, Grade) with key (Roll, CourseID). $Roll \rightarrow StudentName$ is a partial dependency. Decompose into

• STUDENT(Roll, StudentName)
• ENROLL(Roll, CourseID, Grade)

Third Normal Form (3NF). A relation is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on the key. For every FD $X \rightarrow A$, either $X$ is a super key or $A$ is prime.

Example: EMP(EmpID, Name, DeptID, DeptName) with $EmpID \rightarrow DeptID$ and $DeptID \rightarrow DeptName$, so $EmpID \rightarrow DeptName$ is transitive. Decompose into

• EMP(EmpID, Name, DeptID)
• DEPT(DeptID, DeptName)

Each decomposition is lossless, and the final relations are in 3NF.

Schema. The schema is the overall logical design (description) of the database: the structure of tables, attributes, data types, keys and constraints. It is specified at design time and changes rarely. It is also called the intension of the database.

Example:

STUDENT(Roll INT, Name VARCHAR(30), Dept VARCHAR(10))

Schemas exist at three levels: physical (internal), logical (conceptual) and view (external) schema.

Instance. The instance is the actual collection of data stored in the database at a particular moment. It changes frequently as data is inserted, updated or deleted. It is also called the database state or extension.

Example, an instance of STUDENT at some time:

After inserting (3, Hari, BCA) the instance changes, but the schema remains the same.

Schedule. A schedule is a sequence of the operations of a set of concurrent transactions that preserves the order of operations within each transaction.

Conflicting operations. Two operations in a schedule conflict if (i) they belong to different transactions, (ii) they access the same data item, and (iii) at least one of them is a write. So read-write, write-read and write-write pairs conflict; read-read does not.

Conflict equivalence. Two schedules are conflict equivalent if the order of every pair of conflicting operations is the same in both. Swapping adjacent non-conflicting operations of different transactions gives a conflict-equivalent schedule.

Conflict schedule (conflict serializable schedule). A schedule is conflict serializable if it is conflict equivalent to some serial schedule. It can be tested using a precedence graph: draw a node per transaction and an edge $T_i \rightarrow T_j$ if an operation of $T_i$ conflicts with and precedes an operation of $T_j$. The schedule is conflict serializable if and only if the graph has no cycle.

Example.

Conflicts on $A$ and on $B$ all go from $T_1$ to $T_2$. The precedence graph has only the edge $T_1 \rightarrow T_2$, no cycle, so it is conflict serializable and equivalent to the serial schedule $T_1, T_2$.

If instead $R_1(A), W_2(A), W_1(A)$ occurred, we get $T_1 \rightarrow T_2$ and $T_2 \rightarrow T_1$, a cycle, so it is not conflict serializable.

Join the three relations on TID and SID, select school "ABC", then project the required attributes.

$\pi_{TName,\; No\_of\_Period}\Big(\sigma_{SName='ABC'}\big(TEACHER \bowtie SCHOOL\_TEACHER \bowtie SCHOOL\big)\Big)$

Here the natural join of TEACHER and SCHOOL_TEACHER is on TID, and the join with SCHOOL is on SID.

Step by step:

$R_1 = TEACHER \bowtie_{TEACHER.TID = SCHOOL\_TEACHER.TID} SCHOOL\_TEACHER$

$R_2 = R_1 \bowtie_{R_1.SID = SCHOOL.SID} SCHOOL$

$R_3 = \sigma_{SName='ABC'}(R_2)$

$Result = \pi_{TName,\; No\_of\_Period}(R_3)$

The result lists each teacher of school ABC with the number of periods taught.

Aggregation (ER model). A basic ER model cannot express a relationship between a relationship and an entity. Aggregation is an abstraction in which a relationship set (together with the entities it relates) is treated as a higher-level entity set, so that it can take part in another relationship. It models a "has-a / is-part-of" association.

Example. Employees work on projects, and a work assignment may need a machine to be allocated. Machinery is not related to employee or project alone, but to the combination "employee works on project".

 [EMPLOYEE] --- <WORKS_ON> --- [PROJECT]
                    |
        +-----------+-----------+   (aggregation: WORKS_ON treated as one entity)
                    |
               <USES>
                    |
              [MACHINERY]

Here the relationship WORKS_ON with its participants EMPLOYEE and PROJECT is aggregated into one abstract entity, which is then related to MACHINERY by the relationship USES.

Another example: a Doctor treats a Patient, and a Test is prescribed for that treatment relationship.

Advantages: avoids redundant relationships, expresses real-world constraints (a machine can be used only for an existing assignment), and gives a cleaner design.

Mapping to tables: WORKS_ON(EmpID, PID) and USES(EmpID, PID, MachineID) where (EmpID, PID) is a foreign key referencing WORKS_ON.

Functional dependency. For attribute sets $X, Y$ of a relation $R$, $X \rightarrow Y$ (Y is functionally dependent on X) means that whenever two tuples agree on $X$ they also agree on $Y$:

$t_1[X] = t_2[X] \Rightarrow t_1[Y] = t_2[Y]$

Example: $Roll \rightarrow Name$ in STUDENT. FDs are the basis of normalisation.

Second Normal Form (2NF). A relation is in 2NF if

1. it is in 1NF, and
2. every non-prime attribute is fully functionally dependent on every candidate key, i.e. there is no partial dependency (dependency on a proper subset of a composite key).

A relation with a single-attribute key in 1NF is automatically in 2NF.

Example. STUDENT_COURSE(Roll, CourseID, StudentName, CourseName, Marks) with key $\{Roll, CourseID\}$ and FDs

$Roll \rightarrow StudentName,\quad CourseID \rightarrow CourseName,\quad \{Roll, CourseID\} \rightarrow Marks$

StudentName and CourseName depend on only part of the key, so the relation is not in 2NF and has anomalies (student name repeated for every course; a course cannot be stored until a student takes it).

Decomposition to 2NF:

• STUDENT(Roll, StudentName)
• COURSE(CourseID, CourseName)
• RESULT(Roll, CourseID, Marks)

Now each non-key attribute depends on the whole key of its table.

Assertion. An assertion is a database object that expresses a condition which the database must always satisfy. It is checked whenever a change might violate it, and the change is rejected if the condition becomes false. It can involve several tables, unlike a CHECK constraint on one table.

Syntax:

CREATE ASSERTION assertion_name
CHECK (condition);

Example: the balance of every account must be non-negative and a branch's loans must not exceed its assets.

CREATE ASSERTION positive_balance
CHECK (NOT EXISTS (SELECT * FROM Account WHERE Balance < 0));

Trigger. A trigger is a stored procedure that is automatically executed by the DBMS in response to an event (INSERT, UPDATE or DELETE) on a table. It follows the Event-Condition-Action model: an event occurs, a condition is checked, and an action is executed. It is used for auditing, enforcing complex rules and maintaining derived data.

Syntax:

CREATE TRIGGER trigger_name
{BEFORE | AFTER} {INSERT | UPDATE | DELETE} ON table_name
FOR EACH ROW
BEGIN
   -- action
END;

Example: log every salary change.

CREATE TRIGGER salary_audit
AFTER UPDATE ON Employee
FOR EACH ROW
BEGIN
   IF NEW.Salary <> OLD.Salary THEN
      INSERT INTO Salary_Log(EmpID, OldSal, NewSal, ChangedOn)
      VALUES (OLD.EmpID, OLD.Salary, NEW.Salary, NOW());
   END IF;
END;

Difference. An assertion is a declarative condition that must always hold and only accepts or rejects a change; a trigger is procedural, fires on a specific event and can perform any action.

Concurrency control. Concurrency control is the set of techniques used by a DBMS to manage the simultaneous execution of transactions on shared data so that they do not interfere with each other and the database remains consistent. It ensures that the result of concurrent execution is equivalent to some serial execution (serializability), preserving the isolation property.

Without it, problems such as the lost update, dirty read (temporary update), unrepeatable read and phantom read occur.

Main techniques: lock-based protocols (two-phase locking), timestamp ordering, multiversion concurrency control and optimistic (validation-based) methods.

Advantages

• Maintains consistency and integrity of data when many users access it together.
• Guarantees isolation and serializability of transactions.
• Prevents lost updates, dirty reads and inconsistent retrievals.
• Allows higher throughput and better utilisation of CPU and disk, since transactions run in parallel instead of one by one.
• Reduces waiting and response time for short transactions behind long ones.
• Supports deadlock handling and fair access so that all users get their turn.

Buffer management. The buffer is a part of main memory that holds copies of disk blocks. Since reading from disk is far slower than memory, the DBMS keeps a pool of buffer frames, and the buffer manager is the subsystem that decides which disk blocks are in memory, brings blocks in and writes them out. The aim is to minimise disk I/O.

Working. When a program requests block $B$:

1. If $B$ is already in the buffer pool, return its address (a hit).
2. Otherwise, if there is a free frame, read $B$ from disk into it.
3. If there is no free frame, choose a block to replace (evict). If the victim was modified (dirty), write it back to disk first, then read $B$.

Replacement strategies

• LRU (least recently used): evict the block unused for the longest time.
• MRU (most recently used): evict the most recently used block; useful for repeated sequential scans (e.g. nested-loop join).
• FIFO and clock algorithms.
• A toss-immediate policy frees a block as soon as its last tuple is processed.

Other features

• Pinned blocks: blocks currently in use cannot be evicted until unpinned.
• Forced output: a block can be written to disk immediately (e.g. at commit or checkpoint) for recovery.
• Write-ahead logging: log records are written before the corresponding data blocks.

Good buffer management gives faster query processing and supports recovery.

Transaction. A transaction is a logical unit of work consisting of one or more database operations (reads and writes) that must be executed as a whole, taking the database from one consistent state to another. Example: transferring Rs 1000 from account A to B (read A, A = A - 1000, write A, read B, B = B + 1000, write B).

A transaction should satisfy the ACID properties: Atomicity, Consistency, Isolation and Durability.

States of a transaction

          +--------+  end   +---------------------+ commit +-----------+
 begin -->| Active |------->| Partially committed |------->| Committed |
          +---+----+        +----------+----------+        +-----------+
              |                        |
           failure                  failure
              v                        v
          +--------+   rollback   +---------+
          | Failed |------------->| Aborted |
          +--------+              +---------+

1. Active: the initial state; the transaction is executing its operations.
2. Partially committed: after its final statement has executed, but the changes may still be only in memory buffers.
3. Committed: after successful completion, the changes are permanently written to the database (durable). The transaction cannot be undone.
4. Failed: normal execution cannot continue, due to a hardware, logical or system error, or a violation of integrity.
5. Aborted: the transaction has been rolled back and the database restored to its state before the transaction started. The system can then restart the transaction (if the failure was not logical) or kill it.

A transaction is terminated when it ends in the committed or aborted state.

Schema: Customer(CustomerID, CustomerName, Address, Phone, Email), Owns(CustomerID, AccountNumber), Account(AccountNumber, AccountType, Balance).

(a) Names of all customers who live in Kathmandu

Relational algebra:

$\pi_{CustomerName}\big(\sigma_{Address='Kathmandu'}(Customer)\big)$

SQL:

SELECT CustomerName
FROM   Customer
WHERE  Address = 'Kathmandu';

(b) Total number of customers

Relational algebra (aggregate operator $\mathcal{G}$):

$\mathcal{G}_{COUNT(CustomerID)}(Customer)$

SQL:

SELECT COUNT(*) AS TotalCustomers
FROM   Customer;

(c) Names of customers with balance $\geq$ 100000

Relational algebra:

$\pi_{CustomerName}\Big(\sigma_{Balance \geq 100000}\big(Customer \bowtie Owns \bowtie Account\big)\Big)$

SQL:

SELECT DISTINCT C.CustomerName
FROM   Customer C
JOIN   Owns O    ON C.CustomerID = O.CustomerID
JOIN   Account A ON O.AccountNumber = A.AccountNumber
WHERE  A.Balance >= 100000;

(d) Average balance of each account type

Relational algebra (grouping on AccountType):

$_{AccountType}\mathcal{G}_{AVG(Balance)}(Account)$

SQL:

SELECT AccountType, AVG(Balance) AS AverageBalance
FROM   Account
GROUP BY AccountType;

Normalization is the process of organizing the attributes and relations of a database so that data redundancy is minimized and insertion, update and deletion anomalies are removed. A relation is decomposed into smaller, well-structured relations using functional dependencies, and the decomposition must be lossless-join and (preferably) dependency preserving.

Why normalization is important

• It reduces redundancy, so the same fact is stored only once and storage is saved.
• It removes insertion anomalies (a fact cannot be recorded without unrelated data), update anomalies (one fact stored in many rows must be changed in all of them) and deletion anomalies (deleting a row loses unrelated facts).
• It keeps data consistent and makes integrity constraints easier to enforce.
• It gives a clean, logically sound schema that is easier to maintain and extend.

First Normal Form (1NF)

A relation is in 1NF if every attribute holds only atomic (indivisible) values: no multivalued or composite attributes and no repeating groups.

Example (not in 1NF):

Converted to 1NF by giving each phone its own row:

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on any part of a candidate key (every non-key attribute is fully functionally dependent on the whole key).

Example: ENROLL(SID, CID, SName, Grade) with key (SID, CID). Here $SID \rightarrow SName$ is a partial dependency. Decompose into:

• STUDENT(SID, SName)
• ENROLL(SID, CID, Grade)

Now every non-key attribute depends on the full key.

Third Normal Form (3NF)

A relation is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on the key. Formally, for every non-trivial FD $X \rightarrow A$, either $X$ is a superkey or $A$ is a prime attribute.

Example: EMP(EID, EName, DeptID, DeptName) with $EID \rightarrow DeptID$ and $DeptID \rightarrow DeptName$. So $EID \rightarrow DeptName$ is transitive. Decompose into:

• EMP(EID, EName, DeptID)
• DEPT(DeptID, DeptName)

Thus each non-key attribute depends on "the key, the whole key and nothing but the key".

Two-phase locking (2PL) is a concurrency control protocol that guarantees conflict-serializable schedules. Every transaction is divided into two phases:

1. Growing (expanding) phase: the transaction may acquire locks but cannot release any lock.
2. Shrinking phase: the transaction may release locks but cannot acquire any new lock.

The point at which a transaction obtains its last lock is called its lock point. Any schedule produced by 2PL is equivalent to a serial schedule in the order of the lock points.

Types of locks

• Shared (read) lock, S or read-lock(X): several transactions may hold it on the same item; only reading is allowed.
• Exclusive (write) lock, X or write-lock(X): only one transaction may hold it; it allows both reading and writing, and conflicts with every other lock.

Compatibility: S-S is compatible; S-X, X-S and X-X are not.

Variants of 2PL

• Basic 2PL: the two-phase rule alone. It ensures serializability but does not prevent deadlock, and may cause cascading rollback because locks are released before commit.
• Conservative (static) 2PL: a transaction locks all the items it needs before it starts executing. If any item is unavailable it waits without holding any lock. It is deadlock-free but hard to apply since the read/write set must be known in advance.
• Strict 2PL: a transaction does not release any of its exclusive locks until it commits or aborts. This gives strict schedules (no cascading rollback), but deadlock is still possible.
• Rigorous 2PL: a transaction does not release any lock (shared or exclusive) until it commits or aborts. It is simpler than strict 2PL and the schedule is serializable in commit order.

Lock conversion

Lock conversion lets a transaction change the mode of a lock it already holds.

• Upgrade: S-lock to X-lock (e.g. read an item, later decide to write it). It can be done only in the growing phase and only if no other transaction holds a lock on the item.
• Downgrade: X-lock to S-lock. It can be done only in the shrinking phase.

Lock conversion increases concurrency while keeping the two-phase property.

Flat-file system

A flat-file system stores data in separate ordinary files (text, CSV, or application-specific files), each file being a simple sequence of records with no relationships built in. Each application program defines and manages its own files and file formats. Because related data lie in different files, the same information (e.g. a customer's address) is often duplicated in many files.

Problems of the flat-file approach: data redundancy and inconsistency, difficulty in accessing data (a new program is required for each new query), data isolation, no concurrent access control, weak security, no integrity constraints, and no crash recovery.

Advantages of the DBMS approach

• Controlled redundancy: data are stored once in a central database, saving space and avoiding inconsistency.
• Data independence: programs are insulated from changes in storage structure and file organization.
• Data sharing: many users and applications share the same data simultaneously.
• Data integrity: constraints (primary key, foreign key, domain, etc.) keep the data valid.
• Security: authorization and access rights restrict who can see or change what.
• Concurrency control: many users can access data at once without interference.
• Backup and recovery: the system restores the database after failures.
• Efficient querying: query languages such as SQL and indexes give fast, flexible access.
• Standards enforcement and reduced application development time.

Data abstraction is the process of hiding the details of how data are stored and maintained and showing users only the relevant view. It has three levels: physical (how data are stored), logical/conceptual (what data and relationships are stored), and view/external (the part of the database relevant to a user).

Data model is a collection of concepts used to describe the structure of a database: data types, relationships and constraints, together with a set of operations. Examples: ER model (conceptual), relational model (representational), object model, and physical models.

Schema is the description (overall design) of the database, specified during design and not expected to change frequently. For example, STUDENT(SID, Name, Dept). It is also called the intension. A database has a physical schema, a logical schema and external schemas (subschemas).

Instance is the collection of data stored in the database at a particular moment (also called an extension, occurrence or snapshot). It changes whenever data are inserted, deleted or updated.

Database state is the actual content of the database (set of all instances) at a particular time. A newly defined database has an empty state; the initial state is when data are first loaded; every update changes it to another current state. The DBMS ensures every state is a valid state, i.e. one that satisfies the schema's structure and constraints.

Conceptual data model

A conceptual (high-level) data model describes the database in terms of concepts close to the way users perceive data: entities, attributes and relationships. It hides storage details and is independent of any DBMS. The most widely used one is the Entity-Relationship (ER) model. It is used in the design phase to communicate between designers and users and is later mapped to a logical model such as the relational model.

Types of attributes in an ER diagram

1. Simple (atomic) attribute: cannot be divided further, e.g. Age, Roll_no.
2. Composite attribute: can be divided into smaller parts, e.g. Name (First, Middle, Last), Address (Street, City, District). Drawn as an oval connected to oval components.
3. Single-valued attribute: holds one value for an entity, e.g. DateOfBirth.
4. Multivalued attribute: may hold several values for one entity, e.g. Phone_numbers, Skills. Drawn as a double oval.
5. Derived attribute: its value is calculated from other attributes, e.g. Age from DateOfBirth. Drawn as a dashed oval.
6. Key attribute: uniquely identifies each entity of the set, e.g. SID. Its name is underlined.
7. Null-valued attribute: takes NULL when the value is unknown or not applicable, e.g. Apartment_no.
8. Complex attribute: combination of composite and multivalued attributes, e.g. Address_phone.

Relational model

The relational model, proposed by E. F. Codd (1970), represents the database as a collection of relations. Each relation is a table of rows and columns; the data are manipulated with relational algebra/calculus and SQL. It is based on set theory and predicate logic and enforces integrity through keys and constraints. Its simplicity and data independence made it the dominant model.

Terms

• Domain: the set of atomic values permitted for an attribute, e.g. the domain of Age is integers between 0 and 120; the domain of Grade is {A, B, C, D, F}. A domain has a name, data type and format.
• Attribute: a column of a relation; the name of the role played by a domain in the relation, e.g. SID, Name, Dept in STUDENT.
• Tuple: a row of a relation; an ordered list of values, one for each attribute, representing one real-world entity or relationship, e.g. (1, Ram, CSIT).
• Relation: a set of tuples with a relation schema $R(A_1, A_2, \dots, A_n)$; formally a subset of $dom(A_1) \times dom(A_2) \times \dots \times dom(A_n)$. It is a table with distinct rows and no significance in row order.

Example: STUDENT(SID, Name, Dept) has three attributes (degree 3); if it holds 100 rows, its cardinality is 100.

Tuple relational calculus (TRC) is a non-procedural (declarative) query language based on first-order predicate logic. A query states what to retrieve, not how to compute it. Variables range over tuples of relations.

General form of a query:

$\{\, t \mid P(t) \,\}$

It is read as "the set of all tuples $t$ such that the predicate $P$ is true for $t$". Here $t$ is a tuple variable, and $t[A]$ or $t.A$ gives the value of attribute $A$.

Formulas (atoms)

• $R(t)$: tuple $t$ belongs to relation $R$.
• $t[A]\ \theta\ s[B]$ or $t[A]\ \theta\ c$, where $\theta \in \{<, \le, =, \ne, >, \ge\}$ and $c$ is a constant.
• Formulas are built using the connectives $\land$ (and), $\lor$ (or), $\lnot$ (not), $\Rightarrow$ (implies).
• Quantifiers: existential $\exists t\,(P(t))$ and universal $\forall t\,(P(t))$. A variable bound by a quantifier is bound; otherwise it is free, and the free variable is the one in the result.

Examples with STUDENT(SID, Name, Dept, Year):

1. Students of the CSIT department:

$\{\, t \mid STUDENT(t) \land t.Dept = \text{'CSIT'} \,\}$

2. Only names of those students:

$\{\, t.Name \mid STUDENT(t) \land t.Dept = \text{'CSIT'} \,\}$

3. Names of students enrolled in some course, with ENROLL(SID, CID, Grade):

$\{\, t.Name \mid STUDENT(t) \land \exists e\,(ENROLL(e) \land e.SID = t.SID) \,\}$

Safety: an expression is safe if it produces a finite result (e.g. $\{t \mid \lnot STUDENT(t)\}$ is unsafe). TRC restricted to safe expressions has the same expressive power as relational algebra, and SQL is based on it.

Transaction

A transaction is a logical unit of database work consisting of one or more database operations (reads and writes) that must be executed as a whole. It begins with BEGIN TRANSACTION and ends with COMMIT (changes made permanent) or ROLLBACK (changes undone). Example: transferring Rs 1000 from account A to B (read A, A = A - 1000, write A, read B, B = B + 1000, write B).

ACID properties

1. Atomicity: the transaction is "all or nothing". Either all operations are reflected in the database or none are. If the transaction fails midway, its partial effects are undone. This is the responsibility of the recovery subsystem.
2. Consistency: a transaction takes the database from one consistent (valid) state to another, preserving all integrity constraints. In the transfer example, the sum A + B is unchanged. It is the responsibility of the programmer and the integrity-checking part of the DBMS.
3. Isolation: even when many transactions run concurrently, each appears to execute alone; intermediate results of one transaction are invisible to others. It is ensured by the concurrency control subsystem.
4. Durability (permanency): once a transaction commits, its changes persist even after a system crash or power failure. It is ensured by the recovery subsystem using logs and backups.

Concurrency control is the mechanism for managing the simultaneous execution of transactions so that they do not interfere with each other and the database stays consistent. It is needed because many users access the same data at the same time, and uncontrolled interleaving of operations leads to the following problems.

1. Lost update problem: two transactions read the same item and both update it; one update overwrites the other. Example: $T_1$ and $T_2$ both read $X = 100$; $T_1$ writes $X = 100 - 10$, then $T_2$ writes $X = 100 + 20$, so $T_1$'s update is lost.
2. Dirty read (temporary update) problem: a transaction reads a value written by another transaction that later aborts, so it used data that never existed.
3. Incorrect summary (aggregate) problem: one transaction computes an aggregate (e.g. sum of balances) while another is updating some of the items, so some values are read before and some after the update.
4. Unrepeatable read problem: a transaction reads the same item twice and gets different values because another transaction changed it in between.
5. Phantom problem: a re-executed query returns extra rows inserted by another transaction.

Therefore concurrency control is needed to:

• Preserve the isolation property and the consistency of the database.
• Ensure serializable schedules, i.e. the effect is the same as some serial execution.
• Allow high throughput and good resource utilization (e.g. CPU can work while another transaction waits for I/O) while keeping correctness.

It is implemented using locking (2PL), timestamp ordering, multiversion techniques and optimistic methods.

Why database recovery is essential

Failures such as transaction errors (division by zero, logical errors), system crashes (power loss, software bugs), disk failure, deadlock aborts and catastrophes (fire, theft) can leave the database inconsistent or lose committed work. Recovery restores the database to the most recent consistent state before the failure. It is essential to guarantee atomicity (no partial updates remain) and durability (committed updates are never lost), and to keep the data reliable and trustworthy.

Recovery technique based on immediate update

In the immediate update technique, a transaction's write operations are applied directly to the database as they execute, even before the transaction commits. Because uncommitted changes may reach the disk, a log is needed to undo them.

Log (write-ahead logging): a log record for an update is written to disk before the changed data item is written to the database. Records are:

• $[start, T]$
• $[write, T, X, old\_value, new\_value]$
• $[commit, T]$ / $[abort, T]$
• checkpoints

Both the old value (for UNDO) and the new value (for REDO) are stored.

Recovery procedure after a crash

• A transaction $T$ that has $[start, T]$ but no $[commit, T]$ in the log was active at the failure. It must be undone: its writes are reversed in the database by restoring the old values, going backward through the log.
• A transaction having both $[start, T]$ and $[commit, T]$ must be redone: its writes are reapplied from the log in forward order using the new values, since they might not have reached the disk.

This is the UNDO/REDO algorithm. If all updates are forced to disk before commit, only UNDO is needed (UNDO/NO-REDO).

Example: Log: $[start,T_1]$, $[write,T_1,A,50,40]$, $[commit,T_1]$, $[start,T_2]$, $[write,T_2,B,20,30]$, crash. Recovery: redo $T_1$ (A = 40), undo $T_2$ (B = 20).

Checkpoints limit how much of the log must be examined.

(a) Natural join

Natural join, written $R * S$ (or $R \bowtie S$), combines tuples of two relations $R$ and $S$ that have equal values on all attributes with the same name in both relations. The common attributes appear only once in the result. It is equivalent to an equijoin on the common attributes followed by removal of duplicate columns:

$R * S = \pi_{\text{attrs}(R)\,\cup\,\text{attrs}(S)}\big(\sigma_{R.A=S.A}(R \times S)\big)$

If there are no common attributes, the natural join becomes a Cartesian product.

Example: STUDENT(SID, Name) and ENROLL(SID, CID):

$STUDENT * ENROLL$ gives (1, Ram, C1) and (1, Ram, C2). Sita has no matching tuple and is dropped.

(b) Shadow paging

Shadow paging is a recovery technique that does not use a log. The database is divided into fixed-size pages, and a page table (directory) with $n$ entries points to the pages on disk.

• At the start of a transaction, the current page table is copied to a shadow page table, which is saved on disk and never modified during the transaction.
• When a page is to be written, a new copy of the page is made on a free disk block, the update is applied to the new copy, and only the current page table is updated to point to it. The old page stays unchanged (the shadow).
• Commit: the current page table becomes the new shadow page table (by atomically updating a pointer to it); old pages are freed.
• Abort/crash: the current table is discarded and the shadow table is used, so the database returns to the state before the transaction. No undo or redo is required.

Advantages: fast recovery, no log overhead. Disadvantages: data fragmentation and scattering of pages, overhead of copying page tables, garbage collection of old pages, and difficulty with concurrent transactions.

Entity type and entity set

An entity is a real-world object that is distinguishable from other objects (a customer, a ticket). An entity type is the schema or definition of a collection of entities having the same attributes, e.g. CUSTOMER(CustID, Name, Email, Phone). It is drawn as a rectangle in the ER diagram. An entity set is the collection of all entities of a particular entity type in the database at a given time, e.g. all the customers currently stored. The entity type is the intension (structure) and the entity set is the extension (data).

ER design for the airline ticket booking system

Entities and attributes:

• CUSTOMER(<u>CustID</u>, Name, Email, Phone, Address, Visit_count, Category)
• TICKET(<u>TicketID</u>, Seat_no, Class, Price, Booking_date)
• FLIGHT(<u>FlightNo</u>, Source, Destination, Dep_time, Arr_time, Fare)
• DISCOUNT(<u>DiscountID</u>, Min_tickets, Percentage)
• VISIT_LOG(<u>LogID</u>, Visit_time, IP_address)
• BLOCKED_VISITOR(<u>VisitorID</u>, IP_address, Reason, Blocked_date)

Relationships:

• CUSTOMER buys TICKET (1 : N; a customer buys many tickets, each ticket is bought by one customer; total participation of TICKET).
• TICKET is for FLIGHT (N : 1).
• TICKET gets DISCOUNT (N : 1); the discount applied depends on the number of tickets bought in one booking (count of tickets by the customer is compared with Min_tickets).
• CUSTOMER makes VISIT_LOG (1 : N); the number of visits of each customer is counted from this log and stored in Visit_count, which classifies buyers (e.g. Regular, Frequent).
• BLOCKED_VISITOR is checked by the system against each VISIT_LOG entry (via IP_address) and filters unwanted visitors so their access is denied; this controls traffic congestion.

Diagram (text form):

 [DISCOUNT] N---<gets>---N [TICKET] N---<for>---1 [FLIGHT]
                              |N
                              |
                          <buys>
                              |1
 [BLOCKED_VISITOR] ---<filters>--- [VISIT_LOG] N---<makes>---1 [CUSTOMER]

Rectangles are entities, diamonds are relationships, and underlined attributes are keys. Visit_count is a derived attribute (count of VISIT_LOG rows per customer), and Percentage of discount is looked up from DISCOUNT using the number of tickets bought.

Working: when a customer logs in, the system records a VISIT_LOG row; if the visitor's IP is in BLOCKED_VISITOR the request is rejected. Otherwise the customer selects a flight and number of tickets; the system finds the DISCOUNT row with the largest Min_tickets not exceeding the count, applies the percentage, and creates the TICKET records.

Schema: USER(UserID, User_name, Address), USES(UserID, BookID, Issued_date, Returned_date), BOOK(BookID, Book_name, Author, PublisherID), PUBLISHER(PublisherID, Publisher_name, Address).

(a) Names of all books issued to the user "Hari"

SQL:

SELECT B.Book_name
FROM   BOOK B, USES U, USER S
WHERE  S.User_name = 'Hari'
  AND  S.UserID = U.UserID
  AND  U.BookID = B.BookID;

Relational algebra:

$\pi_{Book\_name}\Big(\sigma_{User\_name='Hari'}(USER) \bowtie_{USER.UserID = USES.UserID} USES \bowtie_{USES.BookID = BOOK.BookID} BOOK\Big)$

(b) Names of all books published by "ABC publication"

SQL:

SELECT B.Book_name
FROM   BOOK B, PUBLISHER P
WHERE  P.Publisher_name = 'ABC publication'
  AND  B.PublisherID = P.PublisherID;

Relational algebra:

$\pi_{Book\_name}\Big(BOOK \bowtie_{BOOK.PublisherID = PUBLISHER.PublisherID} \sigma_{Publisher\_name='ABC\ publication'}(PUBLISHER)\Big)$

(c) Number of books published by the author "Ram"

SQL:

SELECT COUNT(*)
FROM   BOOK
WHERE  Author = 'Ram';

Relational algebra (using the aggregate operator $\mathcal{F}$):

$\mathcal{F}_{COUNT\ BookID}\big(\sigma_{Author='Ram'}(BOOK)\big)$

Desirable properties of transactions (ACID)

1. Atomicity: a transaction is executed entirely or not at all; if it fails, all its effects are rolled back (recovery subsystem).
2. Consistency: a transaction moves the database from one valid state to another, preserving integrity constraints.
3. Isolation: concurrent transactions do not see each other's intermediate results; the outcome is as if they ran serially (concurrency control subsystem).
4. Durability: after commit, the changes survive any later failure (recovery subsystem).

Conflict serializability

A schedule is the order in which operations of several transactions are interleaved. Two operations conflict if they:

• belong to different transactions,
• access the same data item, and
• at least one of them is a write.

So the conflicting pairs are read-write, write-read and write-write. Two schedules are conflict equivalent if the relative order of every pair of conflicting operations is the same in both. A schedule is conflict serializable if it is conflict equivalent to some serial schedule.

Test using a precedence (serialization) graph: create one node per transaction; draw an edge $T_i \rightarrow T_j$ if an operation of $T_i$ conflicts with, and precedes, an operation of $T_j$. The schedule is conflict serializable iff the graph has no cycle. A topological order of the graph gives an equivalent serial schedule.

Example 1 (serializable):

Conflicts on A: $T_1$ before $T_2$. Conflicts on B: $T_1$ before $T_2$. The only edge is $T_1 \rightarrow T_2$, with no cycle, so it is conflict serializable and equivalent to the serial schedule $T_1, T_2$.

Example 2 (not serializable): $R_1(A), W_2(A), W_1(A)$. $R_1(A)$ precedes $W_2(A)$, giving $T_1 \rightarrow T_2$; $W_2(A)$ precedes $W_1(A)$, giving $T_2 \rightarrow T_1$. The graph has a cycle, so the schedule is not conflict serializable.

Referential integrity

Referential integrity is a constraint on the relational model that requires a foreign key value in one relation (the referencing relation) to either be NULL or match an existing primary key (candidate key) value in the referenced relation. Formally, if $FK$ of $R_1$ references the primary key of $R_2$, then for every tuple $t_1$ in $R_1$, either $t_1[FK]$ is null or there exists a tuple $t_2$ in $R_2$ with $t_2[PK] = t_1[FK]$.

Example: in EMPLOYEE(EID, Name, DeptID) with DeptID a foreign key referencing DEPARTMENT(DeptID), an employee cannot be assigned to a department number that does not exist in DEPARTMENT.

In SQL:

FOREIGN KEY (DeptID) REFERENCES DEPARTMENT(DeptID)
    ON DELETE CASCADE ON UPDATE CASCADE

Violations can arise on insert into the referencing table, delete or update in the referenced table; the DBMS rejects the operation or takes an action (CASCADE, SET NULL, SET DEFAULT, RESTRICT).

Why it is needed

• It keeps relationships between tables consistent and avoids dangling (orphan) references, e.g. an order for a customer who does not exist.
• It prevents deletion of a parent row that still has child rows (or cascades correctly).
• It maintains the accuracy and reliability of data and makes joins meaningful.
• It enforces business rules at the database level instead of relying on application programs.

ANSI/SPARC three-schema architecture

The three-schema architecture, proposed by ANSI/SPARC, separates the user applications from the physical database. Its goals are to support data independence, multiple user views and a self-describing catalog. The database is described at three levels.

   External level:   View 1     View 2   ...   View n
                        \         |           /
                   external/conceptual mapping
                              |
   Conceptual level:    Conceptual schema
                              |
                   conceptual/internal mapping
                              |
   Internal level:       Internal schema
                              |
                       Stored database

1. Internal level (internal schema): describes the physical storage structure: file organization, record placement, indexes, access paths, data compression and encryption. It is closest to the physical storage.
2. Conceptual level (conceptual schema): describes the structure of the whole database for the community of users: entities, data types, relationships, constraints. It hides physical details and is typically described with a representational data model such as the relational model.
3. External level (external schemas / user views): each describes the part of the database a particular user group is interested in and hides the rest. Different users may have different views, which also provides security.

Mappings: the DBMS transforms requests and results between levels using the external/conceptual mapping and the conceptual/internal mapping.

Data independence

• Logical data independence: the conceptual schema can change (e.g. add an attribute) without changing external schemas or application programs (only the mapping changes).
• Physical data independence: the internal schema can change (e.g. new index, different file structure) without changing the conceptual schema.

Informal design guidelines for relation schemas

These are measures of quality for judging how good a relation schema is, before formal normalization.

1. Semantics of the attributes (clear meaning). Each relation schema should represent one entity type or one relationship type. Attributes of different entities should not be mixed in one relation, so that the meaning is easy to explain. For instance, combining employee and department attributes into one relation makes the semantics unclear.

2. Reducing redundant information and update anomalies. Design the schema so that no insertion, deletion or modification anomalies occur.

• Insertion anomaly: a new department cannot be recorded until an employee is assigned to it, or department details have to be repeated for each employee.
• Deletion anomaly: deleting the last employee of a department also deletes the department's details.
• Modification anomaly: changing a department's name needs updating in many tuples; inconsistency arises if one is missed.

If any anomaly is unavoidable, it must be clearly documented so programs handle it.

3. Reducing NULL values in tuples. Avoid attributes that are frequently NULL because they waste storage, make joins and aggregate functions ambiguous (meaning unknown/not applicable/absent is unclear). Put such attributes in a separate relation if they apply only to a few tuples.

4. Disallowing spurious tuples. Relations should be designed so that when decomposed relations are joined back with natural join, exactly the original tuples are obtained, with no extra (spurious) tuples. This is the lossless-join property. Relations should be joined only on attributes that are primary key/foreign key pairs.

Classification of DBMS based on the data model

The data model determines how the data are structured and manipulated. DBMSs are classified as follows.

1. Relational DBMS (RDBMS): data are stored as tables (relations) of rows and columns, related through keys, and queried with SQL. It is based on set theory and is the most widely used. Examples: MySQL, Oracle, PostgreSQL, SQL Server.
2. Hierarchical DBMS: data are organized as a tree of parent-child records; each child has exactly one parent (1 : N). It is fast for hierarchical access but inflexible. Example: IBM IMS.
3. Network DBMS: data are organized as a graph of records connected by links; a child may have several parents (M : N relationships supported through sets). Example: IDMS, based on the CODASYL model.
4. Object-oriented DBMS (OODBMS): data are stored as objects with attributes, methods, classes and inheritance, closely integrated with object-oriented programming. Examples: ObjectDB, db4o.
5. Object-relational DBMS (ORDBMS): relational systems extended with object features (user-defined types, inheritance, methods). Examples: PostgreSQL, Oracle.
6. NoSQL / other models: key-value (Redis), document (MongoDB), column-family (Cassandra) and graph (Neo4j) databases for large-scale, unstructured or semi-structured data.

Other classification criteria include number of users (single-user, multi-user), distribution (centralized, distributed) and purpose (general-purpose, special-purpose).

Data: known raw facts that can be recorded and have implicit meaning, such as names, numbers, dates, e.g. "Ram", 22, "Kathmandu". Data become information when processed and interpreted.

Database: an organized collection of logically related data, designed, built and populated for a specific purpose and representing some aspect of the real world (the miniworld). Example: the data of a college library with books, users and issues.

DBMS (Database Management System): a general-purpose software system that enables users to define, create, maintain, and control access to the database. It provides functions to define data types and structures and constraints, to construct (store) data, to manipulate (query, update, report), and to share data among users with protection and concurrency control. Examples: MySQL, Oracle, SQL Server.

Database system: the combination of the database, the DBMS software, and the application programs (and often the hardware and users) that together store and manage the data. In short, database system = database + DBMS software (+ applications and users).

Database catalog (system catalog / data dictionary): the part of the DBMS that stores the metadata, i.e. the description of the database: structure of each file, type and storage format of each data item, constraints, relationships, users and access rights. It is used by the DBMS software and by users who need information about the database structure. Its self-describing nature is a main characteristic of the database approach.

Natural join ($*$)

Natural join combines two relations $R$ and $S$ by joining tuples that have equal values on all attributes common to both relations (same name and domain). Equality is implicit, and the common attributes appear only once in the result.

$R * S = \pi_{attrs(R) \cup attrs(S)}\Big(\sigma_{R.A_1 = S.A_1 \land \dots \land R.A_k = S.A_k}(R \times S)\Big)$

where $A_1, \dots, A_k$ are the common attributes. If $R$ and $S$ have no common attribute, $R * S = R \times S$. Tuples with no match in the other relation are excluded (inner join).

Example

EMPLOYEE:

DEPARTMENT:

$EMPLOYEE * DEPARTMENT$ (common attribute DeptID):

Hari is excluded since D3 has no matching department. The SQL equivalent is SELECT * FROM EMPLOYEE NATURAL JOIN DEPARTMENT;.

Deferred update approach (NO-UNDO/REDO)

In the deferred update technique, a transaction does not write any change to the database on disk until it reaches its commit point. During execution, updates are recorded only in the transaction's local workspace (buffers) and in the log. After the transaction commits and the log has been force-written to disk, the updates are applied to the database.

Log records: $[start, T]$, $[write, T, X, new\_value]$ (only the new value is needed), $[commit, T]$, $[abort, T]$.

Rules

1. A transaction cannot change the database until it commits.
2. A transaction does not reach its commit point until all its update log records are written to the log on disk (write-ahead logging).

Recovery after a crash

• If a transaction failed before commit, nothing was written to the database, so no undo is needed; its log entries are simply ignored.
• If a transaction has both $[start, T]$ and $[commit, T]$ in the log, its changes may not have been applied. It is redone: for each $[write, T, X, new\_value]$ in forward order, set $X$ to the new value.
• Redo is idempotent, so a crash during recovery is harmless: recovery is simply restarted.

Hence the technique is called NO-UNDO/REDO.

Example: Log: $[start,T_1]$, $[write,T_1,A,40]$, $[commit,T_1]$, $[start,T_2]$, $[write,T_2,B,30]$, crash. $T_1$ is redone (A = 40), $T_2$ is ignored because B was never changed in the database.

Advantages: simple, no undo. Disadvantage: a transaction's writes must fit in memory buffers until commit, and concurrency is limited. Checkpoints reduce the amount of log to be scanned.

Deadlock

A deadlock is a situation in which two or more transactions are each waiting for a lock held by another transaction in the set, so none of them can proceed. It arises in lock-based concurrency control.

Example

$T_1$ holds A and waits for B; $T_2$ holds B and waits for A. Neither will release its lock, so both are blocked forever.

Necessary conditions: mutual exclusion, hold and wait, no preemption, and circular wait.

Wait-for graph: nodes are transactions; an edge $T_i \rightarrow T_j$ means $T_i$ waits for $T_j$. A cycle ($T_1 \rightarrow T_2 \rightarrow T_1$) indicates deadlock.

Handling deadlock

• Prevention: conservative 2PL (lock everything in advance); ordering of data items; timestamp-based schemes wait-die and wound-wait; no-waiting and cautious waiting.
• Detection and recovery: build the wait-for graph and check for cycles; if one exists, choose a victim transaction (preferably the cheapest, youngest) and abort/rollback it, avoiding starvation.
• Timeouts: a transaction that waits longer than a limit is aborted.

Specialization

Specialization is a top-down process in the enhanced ER (EER) model of defining a set of subclasses of an entity type (the superclass) on the basis of some distinguishing characteristic. Each subclass inherits all attributes and relationships of the superclass and may have additional local attributes or relationships.

Example: the superclass EMPLOYEE(EID, Name, Salary) is specialized into the subclasses SECRETARY(Typing_speed), ENGINEER(Eng_type) and TECHNICIAN(Grade), based on job type. The relationship between a subclass and superclass is an IS-A relationship. It is drawn with a circle and a U-shaped subset symbol pointing toward the superclass.

Constraints on specialization: disjointness (disjoint or overlapping) and completeness (total or partial).

Disjoint constraint

The disjointness constraint specifies that the subclasses of the specialization must be disjoint: an entity of the superclass can be a member of at most one of the subclasses. It is shown by writing d in the circle. If the subclasses can share members, the constraint is overlapping (written o).

Example: STUDENT is specialized into UNDERGRADUATE and GRADUATE based on the attribute Level (an attribute-defined specialization). A student is either undergraduate or graduate, never both, so the specialization is disjoint (d). By contrast, if PERSON is specialized into STUDENT and EMPLOYEE, one person may be both, so it is overlapping.

(a) ER diagram for the online Bookstore

Entities and attributes:

• CUSTOMER(<u>CustID</u>, Name, Email, Phone, Address)
• ORDER(<u>OrderID</u>, Order_date, Total_amount, Status)
• BOOK(<u>ISBN</u>, Title, Author, Publisher, Price, Stock)

Relationships:

• CUSTOMER places ORDER: 1 : N. A customer can place many orders; each order is placed by exactly one customer (total participation of ORDER).
• ORDER contains BOOK: M : N. An order has one or more books, and a book can appear in many orders. The relationship has its own attribute Quantity (and Unit_price at the time of sale).

 [CUSTOMER] 1 ----<places>---- N [ORDER] M ----<contains>---- N [BOOK]
  CustID(PK)                      OrderID(PK)   (Quantity)       ISBN(PK)
  Name, Email,                    Order_date,                    Title, Author,
  Phone, Address                  Total_amount                   Publisher, Price, Stock

Rectangles are entities, diamonds are relationships, underlined attributes are keys (CustID, OrderID, ISBN).

(b) Conversion to a relational schema

1. Each strong entity becomes a relation with its attributes and primary key.
2. The 1 : N relationship places is represented by adding the primary key of the "one" side (CustID) as a foreign key in the "many" side (ORDER).
3. The M : N relationship contains becomes a new relation having the primary keys of both entities as foreign keys, plus the relationship attribute. The combined keys form its primary key.

Resulting schema (PK = primary key, FK = foreign key):

• CUSTOMER(<u>CustID</u>, Name, Email, Phone, Address)
• BOOK(<u>ISBN</u>, Title, Author, Publisher, Price, Stock)
• ORDERS(<u>OrderID</u>, Order_date, Total_amount, Status, CustID)
  • PK: OrderID
  • FK: CustID references CUSTOMER(CustID)
• ORDER_ITEM(<u>OrderID</u>, <u>ISBN</u>, Quantity, Unit_price)
  • PK: (OrderID, ISBN)
  • FK: OrderID references ORDERS(OrderID)
  • FK: ISBN references BOOK(ISBN)

(The table is named ORDERS because ORDER is a reserved word in SQL.)

Schema: Student(SID, SName, Dept, Year), Course(CID, CName, Credit), Enroll(SID, CID, Grade).

a) Names of students from the "CSIT" department whose name starts with A

SQL:

SELECT SName
FROM   Student
WHERE  Dept = 'CSIT' AND SName LIKE 'A%';

Relational algebra:

$\pi_{SName}\big(\sigma_{Dept='CSIT' \land SName\ LIKE\ 'A\%'}(Student)\big)$

b) Student names and the course names they have enrolled in

SQL:

SELECT S.SName, C.CName
FROM   Student S, Enroll E, Course C
WHERE  S.SID = E.SID AND E.CID = C.CID;

Relational algebra:

$\pi_{SName,\,CName}\big(Student \bowtie Enroll \bowtie Course\big)$

c) Total students enrolled in each course

SQL:

SELECT CID, COUNT(SID) AS Total_students
FROM   Enroll
GROUP BY CID;

Relational algebra (grouping and aggregate $\mathcal{F}$):

$_{CID}\,\mathcal{F}_{COUNT\ SID}(Enroll)$

(To show course names, natural join with Course first, grouping on CID, CName.)

d) Update grade 'B' to 'A' for all students in "DBMS"

SQL:

UPDATE Enroll
SET    Grade = 'A'
WHERE  Grade = 'B'
  AND  CID IN (SELECT CID FROM Course WHERE CName = 'DBMS');

Relational algebra has no update operator; the update is expressed as a reassignment of the relation. Let $D = \pi_{CID}(\sigma_{CName='DBMS'}(Course))$:

$Enroll \leftarrow \big(Enroll - \sigma_{Grade='B'}(Enroll \bowtie D)\big) \cup \pi_{SID,\,CID,\,'A'}\big(\sigma_{Grade='B'}(Enroll \bowtie D)\big)$

That is, tuples with grade B in DBMS are removed and re-inserted with grade A.

e) Delete records of students whose Year is 2024

SQL (enrollments first, so the foreign key is not violated):

DELETE FROM Enroll
WHERE  SID IN (SELECT SID FROM Student WHERE Year = 2024);

DELETE FROM Student
WHERE  Year = 2024;

Relational algebra:

$Enroll \leftarrow Enroll - \big(Enroll \ltimes \sigma_{Year=2024}(Student)\big)$

$Student \leftarrow Student - \sigma_{Year=2024}(Student)$

where $\ltimes$ is the semi-join, i.e. enrollments whose SID belongs to a student with Year 2024.

Normalization is the process of organising the attributes and relations of a database so that data redundancy is minimised and insertion, deletion and update anomalies are removed. A relation is decomposed into smaller, well-structured relations using functional dependencies, and the decomposition must be lossless (and preferably dependency preserving). Each normal form (1NF, 2NF, 3NF, BCNF ...) is a stricter test than the one before it.

Unnormalized example. Consider the relation

STUDENT_COURSE(Roll, Name, Phone, CourseID, CourseTitle, Instructor)

where a student may have several phone numbers and take several courses. The key is (Roll, CourseID).

First Normal Form (1NF). A relation is in 1NF if every attribute holds only atomic (indivisible) values, with no repeating groups or multivalued attributes.

Here Phone holds two values in one cell, so the relation is not in 1NF. Placing each phone value in its own row (or in a separate relation PHONE(Roll, Phone)) gives:

STUDENT_COURSE(Roll, Name, Phone, CourseID, CourseTitle, Instructor) with one phone per row, or better STUDENT_COURSE(Roll, Name, CourseID, CourseTitle, Instructor) and PHONE(Roll, Phone).

Second Normal Form (2NF). A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on a proper subset of a candidate key (every non-key attribute is fully functionally dependent on the whole key).

In STUDENT_COURSE(Roll, Name, CourseID, CourseTitle, Instructor) with key (Roll, CourseID):

• Roll → Name (partial dependency)
• CourseID → CourseTitle, Instructor (partial dependency)

These violate 2NF. We remove them by decomposing:

• STUDENT(Roll, Name)
• COURSE(CourseID, CourseTitle, Instructor)
• ENROLL(Roll, CourseID)

Now every non-key attribute depends on the whole key of its relation.

Third Normal Form (3NF). A relation is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on the key; that is, for every non-trivial dependency $X \rightarrow A$, either $X$ is a superkey or $A$ is a prime attribute.

Suppose COURSE also stores the instructor's department:

COURSE(CourseID, CourseTitle, Instructor, Dept)

with $CourseID \rightarrow Instructor$ and $Instructor \rightarrow Dept$. Then $CourseID \rightarrow Dept$ holds only transitively through Instructor, so COURSE is not in 3NF. Decompose into:

• COURSE(CourseID, CourseTitle, Instructor)
• INSTRUCTOR(Instructor, Dept)

Final schema in 3NF: STUDENT(Roll, Name), PHONE(Roll, Phone), COURSE(CourseID, CourseTitle, Instructor), INSTRUCTOR(Instructor, Dept), ENROLL(Roll, CourseID).

Benefits: a student's name or an instructor's department is stored once, so it can be updated in one place (no update anomaly), a course can be recorded before any student enrols (no insertion anomaly), and deleting the last enrolment does not erase the course (no deletion anomaly).

A traditional file processing system stores data in separate application-specific files, each program defining and managing its own files. A database approach keeps all data in one integrated, shared collection managed by a DBMS.

In short, the file system suits small, simple, single-user applications, while the database approach suits larger multi-user systems that need integrity, security and flexibility.

Schema. The schema is the overall logical design or description of the database: the tables, attributes, data types, relationships and constraints. It is specified at design time and changes rarely. It is also called the intension of the database. Example: STUDENT(Roll INT, Name VARCHAR(30), Dept VARCHAR(10)). A database has a schema at three levels: external (subschemas or views), conceptual, and internal (physical).

Instance. An instance (or database state, extension) is the actual data stored in the database at a particular moment. It changes with every insertion, deletion or update, while the schema stays the same. Example: the rows (1, Ram, CSIT) and (2, Sita, BCA) in STUDENT form the current instance. The DBMS checks that every instance is valid with respect to the schema.

Data independence. Data independence is the ability to change the schema at one level without having to change the schema at the next higher level. It follows from the three-schema architecture, and is of two types:

• Physical data independence: the internal schema (file organisation, indexes, storage devices) can be modified without changing the conceptual schema or application programs. Example: adding an index or moving the file to another disk does not affect queries.
• Logical data independence: the conceptual schema (adding or removing an attribute or table) can be modified without changing the external views or application programs. It is harder to achieve than physical independence.

Data independence reduces maintenance cost because applications are insulated from changes in how and where data is stored.