Database Management System

Why indexing is essential

An index is a data structure (such as a B+ tree or hash table) that stores search-key values together with pointers to the records having that key. Without an index, the DBMS must scan the whole file sequentially to find a record, which is slow for large tables. An index:

• speeds up the retrieval of records by search key (equality and range queries), reducing disk block accesses;
• speeds up sorting, joins and ORDER BY/GROUP BY operations;
• helps to enforce uniqueness of keys.

The cost is extra storage and slower inserts, updates and deletes, since the index must be maintained.

Dense index versus sparse index

Example: a file sorted on roll number, with records 101, 102, 103, 104, 105, 106, stored 3 per block.

• Dense index: entries 101, 102, 103, 104, 105, 106, each pointing to its own record.
• Sparse index: entries 101 (block 1) and 104 (block 2). To find 105, the entry 104 is located (the largest entry $\le$ 105), block 2 is read and scanned to find 105.

A Database Management System (DBMS) is software that allows users to define, create, store, maintain, retrieve and control access to a database. It acts as an interface between the database and users or application programs. Examples: MySQL, Oracle, SQL Server, PostgreSQL.

Merits (advantages) of using a DBMS

1. Reduced data redundancy: data is stored in one place, avoiding duplication of data across files.
2. Data consistency: since redundancy is controlled, all users see the same, up-to-date data.
3. Data sharing: many users and applications can share the same data at the same time.
4. Data integrity: integrity constraints (primary key, foreign key, check, not null) keep the data correct and valid.
5. Data security: authentication, authorization and privileges control who can see or change what.
6. Data independence: physical and logical structure can be changed without changing the application programs.
7. Backup and recovery: the DBMS restores the database after a failure or a crash.
8. Concurrency control: the DBMS manages simultaneous access so that transactions do not interfere.
9. Easy and efficient data access: query languages like SQL give quick, flexible retrieval.
10. Standards and reduced application development time.

Drawbacks are the cost of software and hardware, complexity, and need for trained staff.

A data model is a collection of concepts and tools for describing the structure of a database: the data, the relationships between data, the semantics and the constraints. It gives the means to achieve data abstraction.

Types of data models

1. Hierarchical model: data is organised as a tree of records.
2. Network model: data is organised as a graph of records.
3. Relational model: data is stored in tables (relations) of rows and columns.
4. Entity-Relationship (E-R) model: a high-level conceptual model using entities, attributes and relationships.
5. Object-oriented / object-relational model: data is stored as objects with attributes and methods.
6. Semi-structured models such as XML/JSON, and document or key-value models for NoSQL.

Hierarchical versus network data model

A query is represented as an expression tree of relational algebra operators, and the optimizer must decide how to evaluate the tree. There are two approaches.

Materialized evaluation

Operations of the expression are evaluated one at a time, usually from the lowest level of the tree upward. The result of each operation is stored (materialized) in a temporary relation on disk, and is used as the input to the next operation.

• Example: for $\pi_{name}(\sigma_{dept="CS"}(Student \bowtie Enroll))$, first the join is computed and written to a temporary relation $T_1$; then $\sigma$ is applied to $T_1$ giving $T_2$; finally $\pi$ is applied.
• Advantage: simple and always applicable.
• Disadvantage: the cost includes writing and reading the temporary relations, which takes extra disk I/O and space.

Pipelined evaluation

Several operations are evaluated simultaneously in a pipeline: the output tuples of one operation are passed directly as input to the next operation without being stored in a temporary relation.

• It can be demand-driven (lazy: the parent requests the next tuple from the child) or producer-driven (eager: operators produce tuples into buffers until full).
• Example: the selection and projection above can be applied to each tuple coming out of the join, with no temporary relation.
• Advantage: no temporary file I/O, lower cost, quicker first results.
• Disadvantage: not applicable to blocking operators such as sorting and some joins that need the whole input, and pipelined operators cannot always use the best algorithm (e.g. a merge join needs sorted inputs).

Summary: materialization stores intermediate results; pipelining avoids storage, so it is usually cheaper when possible.

When transactions run concurrently without proper control, the interleaving of their operations can give incorrect results. Two such problems are the lost update and the dirty read.

1. Lost update problem

This happens when two transactions read the same data item and both update it based on the old value, so the update of one is overwritten by the other.

Example: let $A = 100$ initially. $T_1$ withdraws 10 and $T_2$ deposits 50.

The correct final value is $100 - 10 + 50 = 140$, but the database has 150: the update of $T_1$ is lost.

2. Dirty read (temporary update) problem

This happens when a transaction reads a value written by another transaction that has not yet committed. If the writer later aborts and rolls back, the reader has used a value that never officially existed.

Example:

$T_2$ read the uncommitted value 80 and wrote 90 based on it. After $T_1$ rolls back, the correct value should be 110, but the database holds an inconsistent value. This may also cause cascading rollbacks.

These problems are prevented by concurrency control (locking, timestamp ordering) and appropriate isolation levels.

Timestamp ordering protocol is a concurrency-control method that decides the serialisability order of transactions in advance using timestamps, without locks.

Timestamps

• Each transaction $T_i$ gets a unique timestamp $TS(T_i)$ when it enters the system (system clock or logical counter). An older transaction has a smaller timestamp.
• Each data item $Q$ keeps two values:
  • $W\text{-}TS(Q)$: the largest timestamp of any transaction that successfully wrote $Q$.
  • $R\text{-}TS(Q)$: the largest timestamp of any transaction that successfully read $Q$.

The protocol ensures that conflicting operations are executed in timestamp order, so the schedule is equivalent to the serial schedule in timestamp order.

Rules

Transaction $T_i$ issues read($Q$):

• If $TS(T_i) < W\text{-}TS(Q)$: $T_i$ would read a value that has already been overwritten, so the read is rejected and $T_i$ is rolled back (restarted with a new timestamp).
• Otherwise the read is executed and $R\text{-}TS(Q) = \max(R\text{-}TS(Q), TS(T_i))$.

Transaction $T_i$ issues write($Q$):

• If $TS(T_i) < R\text{-}TS(Q)$: a younger transaction has already read the value that $T_i$ is producing now, so the write is rejected and $T_i$ is rolled back.
• If $TS(T_i) < W\text{-}TS(Q)$: $T_i$ is writing an obsolete value, so the write is rejected and $T_i$ is rolled back. (Thomas' write rule simply ignores this obsolete write.)
• Otherwise the write is executed and $W\text{-}TS(Q) = TS(T_i)$.

Example: let $TS(T_1) = 5$, $TS(T_2) = 10$. If $T_2$ writes $Q$ ($W\text{-}TS = 10$) and later $T_1$ tries to read $Q$, then $5 < 10$, so $T_1$ is rolled back.

Properties: it guarantees conflict serialisability and is free from deadlock, since transactions never wait. It may cause starvation of a transaction that is repeatedly restarted, and it can produce cascading rollbacks or non-recoverable schedules unless extra checks (such as waiting for commit) are made.

A stored procedure is a named collection of precompiled SQL statements (with optional control-flow logic) that is stored in the database and can be executed by calling its name with parameters.

Advantages

1. Better performance: it is parsed and compiled once, and the execution plan is cached.
2. Reduced network traffic: only the call is sent to the server instead of many SQL statements.
3. Reusability and modularity: the business logic is written once and used by many applications.
4. Security: users can be given permission to execute the procedure without direct access to the underlying tables; it also helps against SQL injection when parameterised.
5. Easy maintenance: a change in the logic is made in one place only.
6. Consistency and transaction control of operations.

Disadvantages

1. Hard to debug and test compared with application code.
2. Business logic in the database makes it vendor specific (the procedural syntax differs among DBMSs), so portability is reduced.
3. Heavy use increases the load on the database server.
4. Version control and deployment are more difficult.

Creating and executing a stored procedure (MySQL)

DELIMITER //
CREATE PROCEDURE GetStudentsByDept (IN dept_name VARCHAR(30))
BEGIN
    SELECT roll_no, name
    FROM Student
    WHERE department = dept_name;
END //
DELIMITER ;

Execution:

CALL GetStudentsByDept('Computer');

In SQL Server the equivalent is:

CREATE PROCEDURE GetStudentsByDept @dept VARCHAR(30)
AS
BEGIN
    SELECT roll_no, name FROM Student WHERE department = @dept;
END;

EXEC GetStudentsByDept 'Computer';

It can be removed using DROP PROCEDURE GetStudentsByDept;.

Assumptions

The hospital has patients, doctors, departments, wards/rooms, nurses and treatments (appointments).

Entities and attributes (primary keys underlined by *)

• PATIENT(PatientID*, Name, Address, Phone, DOB, Gender)
• DOCTOR(DoctorID*, Name, Specialization, Phone, Salary)
• DEPARTMENT(DeptID*, DeptName, Location)
• WARD(WardNo*, WardType, Capacity)
• NURSE(NurseID*, Name, Shift)
• APPOINTMENT (relationship attributes: Date, Time, Diagnosis, Fee)

Relationships, cardinalities and participation

ER diagram (text form: rectangle = entity, diamond = relationship, == = total participation, -- = partial participation)

 (Name)(Phone)                      (DeptName)(Location)
      \   |                             \   |
      [ DOCTOR ] ==N=== <WORKS_IN> ==1== [ DEPARTMENT ]
        |   \                                   ||
        M    \--1-- <HEADS> -- partial ---------+ (total)
        |
     <TREATS>  (Date, Diagnosis, Fee)
        |
        N  (total)
        |
     [ PATIENT ] --N-- <ADMITTED_TO>(AdmitDate) --1-- [ WARD ] --1-- <ASSIGNED_TO> --N== [ NURSE ]
      PatientID, Name,   (partial)         (partial)   WardNo,                          (total)
      Address, Phone, DOB                              WardType

Notes

• Total participation (double line) means every entity instance must take part in the relationship; for example every DOCTOR must work in some DEPARTMENT.
• Partial participation (single line) means participation is optional, for example a PATIENT need not be admitted to a WARD.
• Converted to relations, the N:1 relationships become foreign keys on the N side (Doctor.DeptID, Patient.WardNo, Nurse.WardNo) and the M:N relationship TREATS becomes a table Treats(DoctorID, PatientID, Date, Diagnosis, Fee).

Importance of normalization

Normalization is the process of organising the attributes and tables of a relational database to minimise redundancy and avoid anomalies, by decomposing relations using functional dependencies. Its importance:

1. Reduces data redundancy and saves storage.
2. Removes insertion, update and deletion anomalies.
3. Keeps the data consistent and maintains integrity.
4. Gives a clear, logical design, with decomposition that is lossless and (ideally) dependency preserving.
5. Makes queries and maintenance of the database easier.

First Normal Form (1NF)

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

Not in 1NF:

1NF:

Second Normal Form (2NF)

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

Example: Enroll(StudentID, CourseID, StudentName, Grade) with key $(StudentID, CourseID)$. Here $StudentID \to StudentName$ is a partial dependency, so it is not in 2NF. Decompose:

• Student(StudentID, StudentName)
• Enroll(StudentID, 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; i.e. for every non-trivial $X \to A$, either $X$ is a superkey or $A$ is a prime attribute.

Example: Student(StudentID, Name, DeptID, DeptName) with $StudentID \to DeptID$ and $DeptID \to DeptName$. $DeptName$ is transitively dependent on $StudentID$, so it is not in 3NF. Decompose:

• Student(StudentID, Name, DeptID)
• Department(DeptID, DeptName)

Each step produces relations that are free of more kinds of anomalies. For instance, after the 3NF split, a department name is stored once, and changing it needs only one update.

Schemas:

• Restaurant(Rname, Rlocation, Rfund)
• Cook(Cname, Cspeciality)
• Worksat(Cname, Rname, Workinghrs, Shift)
• Food(Fname, Cname, Catagory)

(a) Name and location of all restaurants

SQL:

SELECT Rname, Rlocation FROM Restaurant;

Relational algebra:

$\pi_{Rname,\,Rlocation}(Restaurant)$

(b) Working hours of cook named "Sita"

SELECT Workinghrs FROM Worksat WHERE Cname = 'Sita';

$\pi_{Workinghrs}(\sigma_{Cname='Sita'}(Worksat))$

(c) Names of foods cooked by "Ramesh"

SELECT Fname FROM Food WHERE Cname = 'Ramesh';

$\pi_{Fname}(\sigma_{Cname='Ramesh'}(Food))$

(d) Names of restaurants where food of category "breakfast" is available (using join)

A cook who works at a restaurant and cooks breakfast food makes that food available there.

SELECT DISTINCT w.Rname
FROM Worksat w
JOIN Food f ON w.Cname = f.Cname
WHERE f.Catagory = 'breakfast';

$\pi_{Rname}\big(Worksat \bowtie_{Worksat.Cname = Food.Cname} \sigma_{Catagory='breakfast'}(Food)\big)$

(e) Names of cooks who work at "KFC"

SELECT Cname FROM Worksat WHERE Rname = 'KFC';

$\pi_{Cname}(\sigma_{Rname='KFC'}(Worksat))$

A database is an organised collection of related data stored so that it can be easily accessed, managed and updated. For example, a college database holds data about students, teachers, courses and results. A DBMS (Database Management System) is the software (MySQL, Oracle, PostgreSQL, SQL Server) used to define, create, store, retrieve and control access to the database.

Importance of DBMS

1. Reduced data redundancy and inconsistency: data is stored centrally, so the same fact is not repeated in many files.
2. Data sharing: many users and applications can use the same data at the same time.
3. Data independence: programs are insulated from changes in the physical storage or logical structure of data.
4. Data integrity: integrity constraints (primary key, foreign key, check, not null) keep data correct and valid.
5. Security: access is controlled through user accounts, privileges and roles.
6. Backup and recovery: the DBMS restores the database to a consistent state after a crash or failure.
7. Concurrency control: transactions of many users are executed without interfering with each other.
8. Efficient access: indexing, query optimisation and a query language (SQL) give fast retrieval of data.
9. Standards and reduced development time: common standards and ready-made services make application development quicker.

Union compatibility. Two relations $R(A_1,\dots,A_n)$ and $S(B_1,\dots,B_m)$ are union compatible (type compatible) if

1. they have the same number of attributes, i.e. $n = m$, and
2. the corresponding attributes have the same domain (data type), i.e. $\text{dom}(A_i)=\text{dom}(B_i)$ for every $i$.

Attribute names may differ. The operations union ($\cup$), intersection ($\cap$) and difference ($-$) can be applied only to union-compatible relations. The result takes the attribute names of the first relation.

Here Director(Fname, Lname) and Actor(First name, Last name) both have two string attributes, so they are union compatible.

Director $\cap$ Actor (tuples present in both):

Actor $\cup$ Director (all distinct tuples, duplicates removed; the result uses the attribute names of Actor):

Both clauses organise the output of a query, but they do different jobs.

Consider Employee(eid, name, dept, salary).

ORDER BY example: list employees by salary, highest first.

SELECT name, dept, salary
FROM Employee
ORDER BY salary DESC;

GROUP BY ... HAVING example: show departments whose average salary is more than 30000.

SELECT dept, COUNT(*) AS total, AVG(salary) AS avg_sal
FROM Employee
GROUP BY dept
HAVING AVG(salary) > 30000;

Both together: the same result sorted by average salary.

SELECT dept, AVG(salary) AS avg_sal
FROM Employee
GROUP BY dept
HAVING AVG(salary) > 30000
ORDER BY avg_sal DESC;

Normalization is the process of organising the attributes and tables of a relational database to reduce redundancy and avoid insertion, deletion and update anomalies.

Why it is needed

• It removes redundant data, which saves storage.
• It avoids update anomalies (the same fact must be changed in many rows), insertion anomalies (a fact cannot be stored without another) and deletion anomalies (deleting one fact loses another).
• It keeps data consistent and makes the design clearer and easier to maintain.

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: Student(Roll, Name, Phones) with Phones = {9801, 9802} is not in 1NF. Giving each phone its own row, Student(Roll, Name, Phone), makes it 1NF.

Second Normal Form (2NF). A relation is in 2NF if it is in 1NF and every non-key attribute is fully functionally dependent on the whole primary key, with no partial dependency on part of a composite key. Example: Enroll(Roll, CourseID, StudentName, Grade) with key (Roll, CourseID). Here $Roll \rightarrow StudentName$ is a partial dependency, so it is not in 2NF. Decompose into Student(Roll, StudentName) and Enroll(Roll, CourseID, Grade).

Measuring the cost of a query

The query optimiser chooses the execution plan with the least estimated cost. Cost is mainly measured as the total resource consumption:

1. Disk (secondary storage) access cost: number of blocks read and written. This usually dominates because disk is far slower than memory.
2. CPU cost: time for processing tuples, comparisons and computations.
3. Memory (buffer) usage cost: space for sorting, hashing and temporary results.
4. Communication cost: data transfer in distributed or client-server systems.
5. Storage cost of intermediate results.

Total cost = disk access + CPU + memory + communication. The estimate uses catalog statistics such as number of tuples, blocks per relation, distinct values and available indexes, together with the selectivity of conditions. Typically, cost of a plan $\approx$ (number of block transfers $\times t_T$) + (number of seeks $\times t_S$).

Query expression tree

The query is: project $Fname, Lname, Address$ over a selection with condition $Dname=\text{"Research"} \wedge Dnumber=Dno$ applied to the join of Employee and Works_on (the cross-product of Department and the join of Employee and Works_on in the question). In relational algebra:

$\pi_{Fname,\,Lname,\,Address}\big(\sigma_{Dname=\text{"Research"}\ \wedge\ Dnumber=Dno}(\text{Department} \times (\text{Employee} \bowtie \text{Works\_on}))\big)$

The tree has relations as leaves and operators as internal nodes, evaluated bottom up:

        π Fname, Lname, Address
                 |
   σ Dname="Research" ∧ Dnumber=Dno
                 |
                 ×
               /   \
       Department    ⋈
                    /  \
              Employee  Works_on

Execution starts at the leaves (Department, Employee, Works_on), joins/products form intermediate relations, then the selection filters tuples and the projection at the root gives the final result. The optimiser may rewrite the tree by pushing the selection $Dname=\text{"Research"}$ down to Department and replacing selection plus product by a join, which lowers the cost.

Wait-for-graph construction. A wait-for graph $G=(V,E)$ is a directed graph used by the lock manager to detect deadlock.

• Vertices $V$: the active transactions.
• Edge $T_i \rightarrow T_j$: added when $T_i$ requests a lock on a data item that is currently locked by $T_j$ in a conflicting mode, so $T_i$ must wait for $T_j$.
• The edge is removed when $T_j$ releases the lock and $T_i$ obtains it.

Deadlock detection. The system checks the graph periodically. If the graph contains a cycle, a deadlock exists and every transaction in the cycle is deadlocked. If there is no cycle, there is no deadlock. To recover, a victim transaction in the cycle is chosen (usually the cheapest one to roll back) and aborted, which breaks the cycle.

Example. Consider this schedule:

Edges: $T_1 \rightarrow T_2$, $T_2 \rightarrow T_3$, $T_3 \rightarrow T_1$.

The graph has the cycle $T_1 \rightarrow T_2 \rightarrow T_3 \rightarrow T_1$, so the schedule is deadlocked. Aborting $T_3$ (say) releases C, lets $T_2$ proceed, then $T_1$, and the deadlock is resolved.

Read and write operations in a transaction. A transaction accesses the database through two basic operations, working between disk and main-memory buffers:

• read(X): if the block containing item $X$ is not in the main-memory buffer, it is first read from disk; then the value of $X$ is copied into a local variable of the transaction.
• write(X): the value of the local variable is copied into $X$ in the buffer (after bringing the block in if needed). The buffer is written to disk later, either immediately or at a time chosen by the buffer manager, and only guaranteed durable after commit.

For example, a transfer of Rs 500 from A to B is: read(A); A := A - 500; write(A); read(B); B := B + 500; write(B).

States of a transaction.

1. Active: the initial state; the transaction is executing its operations.
2. Partially committed: after the final statement has executed, but changes may still be only in memory.
3. Committed: after successful completion; all changes are permanently recorded in the database.
4. Failed: after normal execution can no longer proceed (hardware, logical error, deadlock).
5. Aborted: after the transaction is rolled back and the database restored to its state before the transaction began. The system may then restart or kill the transaction.

Transitions: Active → Partially committed → Committed; Active or Partially committed → Failed → Aborted.

Schema: Sailors(sid, sname, rating, age), Boats(bid, bname, colour), Reserves(sid, bid, reservedate).

(a) Name, rating and age of all sailors

$\pi_{sname,\,rating,\,age}(Sailors)$

SELECT sname, rating, age FROM Sailors;

(b) Name and colour of blue boats

$\pi_{bname,\,colour}(\sigma_{colour='blue'}(Boats))$

SELECT bname, colour FROM Boats WHERE colour = 'blue';

(c) Names of boats reserved on 2021/07/20

$\pi_{bname}\big(Boats \bowtie (\sigma_{reservedate='2021/07/20'}(Reserves))\big)$

SELECT DISTINCT b.bname
FROM Boats b JOIN Reserves r ON b.bid = r.bid
WHERE r.reservedate = '2021-07-20';

(d) Names of boats and sailors who have reserved green boats

$\pi_{bname,\,sname}\big(\sigma_{colour='green'}(Boats) \bowtie Reserves \bowtie Sailors\big)$

SELECT b.bname, s.sname
FROM Sailors s
JOIN Reserves r ON s.sid = r.sid
JOIN Boats b ON r.bid = b.bid
WHERE b.colour = 'green';

(e) Left and right outer joins between Sailors and Reserves

$Sailors \;⟕_{Sailors.sid=Reserves.sid}\; Reserves \qquad Sailors \;⟖_{Sailors.sid=Reserves.sid}\; Reserves$

-- Left outer join: all sailors, with reservation data where it exists
SELECT s.sid, s.sname, r.bid, r.reservedate
FROM Sailors s LEFT OUTER JOIN Reserves r ON s.sid = r.sid;

-- Right outer join: all reservations, with sailor data where it exists
SELECT s.sid, s.sname, r.bid, r.reservedate
FROM Sailors s RIGHT OUTER JOIN Reserves r ON s.sid = r.sid;

The left join keeps sailors who never reserved a boat (with NULLs for the Reserves columns); the right join keeps all Reserves rows, with NULLs for the Sailors columns if no matching sailor exists.

(a) ER diagram: Library Management System

Entities and attributes (primary keys underlined by "PK"):

• MEMBER(member_id PK, name, address, phone)
• BOOK(isbn PK, title, price, edition)
• AUTHOR(author_id PK, name, country)
• PUBLISHER(pub_id PK, name, city)
• LIBRARY_CARD(card_no PK, issue_date, expiry_date)
• COPY (weak entity)(copy_no partial key, shelf_location, condition), identified by the owning BOOK (identifying relationship HAS_COPY, double rectangle/diamond)

Relationships:

• MEMBER 1 : 1 LIBRARY_CARD (HOLDS): each member holds exactly one card, each card belongs to one member.
• PUBLISHER 1 : N BOOK (PUBLISHES): a publisher publishes many books, each book has one publisher.
• BOOK M : N AUTHOR (WRITTEN_BY): a book has many authors and an author writes many books.
• BOOK 1 : N COPY (HAS_COPY, identifying, total participation of COPY): a book has many physical copies; a copy cannot exist without its book.
• MEMBER M : N COPY (BORROWS, attributes issue_date, due_date, return_date): a member borrows many copies over time and a copy is borrowed by many members over time.

(b) Conversion to relational tables

• MEMBER(<u>member_id</u>, name, address, phone)
• LIBRARY_CARD(<u>card_no</u>, issue_date, expiry_date, member_id) with member_id FK to MEMBER, UNIQUE (1:1)
• PUBLISHER(<u>pub_id</u>, name, city)
• BOOK(<u>isbn</u>, title, price, edition, pub_id) with pub_id FK to PUBLISHER (1:N, key on the many side)
• AUTHOR(<u>author_id</u>, name, country)
• BOOK_AUTHOR(<u>isbn</u>, <u>author_id</u>) with both FKs (M:N relationship table)
• COPY(<u>isbn</u>, <u>copy_no</u>, shelf_location, condition) with isbn FK to BOOK (weak entity: PK is owner key plus partial key)
• BORROWS(<u>member_id</u>, <u>isbn</u>, <u>copy_no</u>, <u>issue_date</u>, due_date, return_date) with member_id FK to MEMBER and (isbn, copy_no) FK to COPY (M:N relationship table)

Stored procedure. A stored procedure is a named, precompiled group of SQL (and procedural) statements stored in the database and executed on demand with CALL. It can take input/output parameters.

Trigger. A trigger is a special stored program that is executed automatically by the DBMS when a specified event (INSERT, UPDATE, DELETE) occurs on a table, either BEFORE or AFTER the event. It cannot be called directly and takes no parameters.

Applications in a database.

• Stored procedures: reuse of business logic, reduced network traffic, faster execution (precompiled), better security (users get EXECUTE rights without table access), consistency of operations.
• Triggers: enforcing complex integrity rules, validating or modifying incoming data, auditing and logging changes, maintaining derived/summary data, and cascading actions.

Stored procedure example (MySQL).

DELIMITER //
CREATE PROCEDURE GetStudentsByDept(IN dept VARCHAR(30))
BEGIN
    SELECT * FROM Student WHERE department = dept;
END //
DELIMITER ;

CALL GetStudentsByDept('BCA');

BEFORE INSERT trigger (validate/modify data before it is stored):

CREATE TRIGGER before_student_insert
BEFORE INSERT ON Student
FOR EACH ROW
BEGIN
    IF NEW.marks < 0 THEN
        SET NEW.marks = 0;
    END IF;
    SET NEW.name = UPPER(NEW.name);
END;

AFTER INSERT trigger (record an audit entry once the row is inserted):

CREATE TRIGGER after_student_insert
AFTER INSERT ON Student
FOR EACH ROW
BEGIN
    INSERT INTO Student_Log(student_id, action, action_time)
    VALUES (NEW.id, 'INSERTED', NOW());
END;

NEW refers to the row being inserted. A BEFORE trigger can change NEW values; an AFTER trigger sees the committed row and is used for logging and side effects.

DBMS. A Database Management System is software that lets users define, create, store, retrieve, update and control access to a database, which is an organised collection of related data. Examples: MySQL, Oracle, PostgreSQL, SQL Server.

Advantages

• Reduced data redundancy and inconsistency: data is stored centrally, not duplicated across files.
• Data sharing: many users and applications can access the same data concurrently.
• Data integrity: integrity constraints (keys, checks) keep data valid.
• Security: authentication and authorisation restrict who can see or change data.
• Backup and recovery: the system restores data after failures.
• Data independence: programs are insulated from changes in storage structure.
• Concurrency control and transactions: ACID properties keep multi-user access correct.
• Standard query language: SQL gives easy ad-hoc querying.

Disadvantages

• High cost: software, hardware and trained staff (DBA) are expensive.
• Complexity: design and administration are complex.
• Performance overhead: generality makes it slower than a tailor-made file system for simple tasks.
• Single point of failure: a failure of the centralised DBMS affects all applications.
• Large size and resource needs: needs considerable memory and disk space.
• Conversion cost: migrating from an existing file system is difficult and costly.

The three-schema (ANSI/SPARC) architecture separates the user view of the database from its physical storage. It has three levels:

1. External level (view level): the highest level. It describes the part of the database relevant to each user or application group as external schemas (views). Different users see different views and hidden data is not shown, which also gives security.
2. Conceptual level (logical level): describes the whole database for the community of users: entities, attributes, relationships, data types and constraints. There is one conceptual schema, independent of physical storage details. The DBA works at this level.
3. Internal level (physical level): describes how data is physically stored: file structures, indexes, access paths, record placement, compression.

Mappings. The DBMS maps requests between levels: external/conceptual mapping and conceptual/internal mapping.

Data independence.

• Logical data independence: the conceptual schema can change (add an attribute) without changing external schemas or programs.
• Physical data independence: the internal schema can change (new index, different file organisation) without changing the conceptual schema.

The Database Administrator (DBA) is the person (or team) with central control over the DBMS and the data it holds.

Roles and responsibilities

• Schema definition: creating the original database schema using DDL.
• Storage structure and access method definition: choosing file organisation, indexes and access paths.
• Schema and physical organisation modification: altering the schema or storage as requirements change.
• Granting authorisation: creating user accounts and giving access rights, enforcing security policy.
• Integrity checking: specifying integrity constraints and ensuring data quality.
• Backup and recovery: regular backups, and recovery plans after hardware or software failure.
• Performance monitoring and tuning: watching response times, optimising queries, indexing, and resource use.
• Concurrency and deadlock management: making sure multiple users can work correctly.
• Liaison with users: gathering requirements, training users and helping developers.
• Capacity planning and upgrades: installing and upgrading DBMS software and hardware.

States of a transaction

• Active: the initial state; the transaction is executing.
• Partially committed: the final statement has been executed, but the changes may not yet be on disk.
• Committed: the transaction completed successfully and its changes are permanent.
• Failed: normal execution cannot continue because of an error.
• Aborted: the transaction has been rolled back and the database restored to its state before the transaction; it may then be restarted or terminated.

Flow: Active → Partially committed → Committed; Active/Partially committed → Failed → Aborted.

ACID properties

• Atomicity: all operations of a transaction happen, or none do. If a failure occurs midway, all changes are rolled back (handled by the recovery manager).
• Consistency: a transaction takes the database from one consistent state to another, preserving all integrity constraints. For a transfer of Rs 500 from A to B, the sum $A+B$ stays unchanged.
• Isolation: concurrent transactions behave as if executed one after another; intermediate results are invisible to others (concurrency control).
• Durability: once committed, the changes survive any later system failure (ensured by logs and recovery).

Use of an ER diagram. An Entity-Relationship diagram is a graphical conceptual model of the data. It is used to:

• Model the real-world entities, their attributes and relationships before implementation.
• Communicate the design between designers, developers and non-technical users.
• Specify keys, cardinalities and participation constraints.
• Serve as the basis for converting to relational tables.

ER diagram for a university (rectangles = entities, ellipses = attributes, diamonds = relationships):

Entities and attributes:

• STUDENT(student_id PK, name, address, dob)
• COURSE(course_id PK, title, credit_hours)
• TEACHER(teacher_id PK, name, qualification, salary)
• DEPARTMENT(dept_id PK, dept_name, location)

Relationships:

• DEPARTMENT 1 : N STUDENT (ENROLLED_IN): a department has many students; each student belongs to one department (total participation of student).
• DEPARTMENT 1 : N TEACHER (WORKS_FOR).
• DEPARTMENT 1 : N COURSE (OFFERS).
• STUDENT M : N COURSE (REGISTERS, attributes: semester, grade).
• TEACHER M : N COURSE (TEACHES) or 1:N if each course has one teacher.
• TEACHER 1 : 1 DEPARTMENT (HEADS): one teacher heads a department.

Draw each entity as a rectangle with its key attribute underlined, connect each pair through a diamond, and mark the cardinalities (1, N, M) on the connecting lines.

Normalization. Normalization is the process of organising the attributes and tables of a relational database, using functional dependencies, to minimise redundancy and avoid insertion, update and deletion anomalies. A large table is decomposed into smaller well-structured tables, without losing information.

Importance

• Removes data redundancy and saves storage.
• Prevents insertion, update and deletion anomalies.
• Keeps data consistent and improves integrity.
• Makes the schema easier to maintain and extend.

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

Not in 1NF: Student(Roll, Name, Phone) with Phone = {9841.., 9851..}. In 1NF: Student(Roll, Name, Phone) with one phone number per row: (1, Ram, 9841..), (1, Ram, 9851..), with key (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 part of a composite candidate key.

Example: Enroll(StudentID, CourseID, StudentName, Grade), key (StudentID, CourseID). Here StudentID → StudentName is a partial dependency. Decompose:

• Student(StudentID, StudentName)
• Enroll(StudentID, 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 superkey or $A$ is a prime attribute).

Example: Student(StudentID, Name, DeptID, DeptName) with StudentID → DeptID → DeptName (transitive). Decompose:

• Student(StudentID, Name, DeptID)
• Department(DeptID, DeptName)

Stored procedure vs trigger

Why concurrency control is needed. When many transactions execute at the same time, uncontrolled interleaving can cause:

• Lost update: two transactions overwrite each other's updates.
• Dirty read: a transaction reads data written by an uncommitted transaction that later aborts.
• Unrepeatable read: a repeated read in one transaction returns different values.
• Incorrect summary / phantom: aggregates see partial updates.

Concurrency control ensures isolation and serializability, so that the database stays consistent while throughput is maintained.

Timestamp-based protocol. Each transaction $T_i$ gets a unique timestamp $TS(T_i)$ when it starts (older = smaller). Each data item $Q$ keeps:

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

Rules:

• $T_i$ issues read(Q):
  • If $TS(T_i) < W\text{-}TS(Q)$, it would read an already-overwritten value, so the read is rejected and $T_i$ is rolled back.
  • Otherwise, the read executes and $R\text{-}TS(Q) = \max(R\text{-}TS(Q), TS(T_i))$.
• $T_i$ issues write(Q):
  • If $TS(T_i) < R\text{-}TS(Q)$, a younger transaction already read the value that would be overwritten, so the write is rejected and $T_i$ is rolled back.
  • If $TS(T_i) < W\text{-}TS(Q)$, the write is obsolete, so it is rejected and $T_i$ is rolled back (Thomas' write rule would simply ignore it).
  • Otherwise, the write executes and $W\text{-}TS(Q) = TS(T_i)$.

A rolled-back transaction is restarted with a new timestamp. The protocol guarantees conflict-serializable schedules in timestamp order and is deadlock-free, since no transaction waits.

Data model. A data model is a collection of concepts and tools for describing the data, data relationships, data semantics and consistency constraints of a database. It provides the means to achieve abstraction of the database structure.

Types of data models

1. Conceptual (high-level) models: close to the way users perceive data, e.g. the Entity-Relationship (ER) model and object-based models.
2. Representational (record-based / implementation) models: hide some storage detail but can be implemented directly:
   • Hierarchical model: data in tree structure with parent-child links (1:N).
   • Network model: graph structure where a child can have several parents (M:N through sets).
   • Relational model: data in tables (relations) of rows and columns; most widely used.
3. Physical (low-level) models: describe how data is stored in files, with record formats, orderings and access paths.

Other models: object-oriented, object-relational, semi-structured (XML/JSON), document and graph models.

Structure of a database. A database is organised as:

• Tables (relations): each representing an entity set, made of rows (tuples/records) and columns (attributes/fields).
• Schema: the logical design, including attribute names, data types, keys and constraints (primary key, foreign key).
• Instance: the data stored at a given moment.
• Indexes, views and metadata (data dictionary) to speed access, present user-specific data, and describe the data itself.

Overall, the DBMS structure follows the three-schema architecture (external, conceptual and internal levels), and has components such as the DDL/DML compilers, query processor, storage manager, transaction manager and buffer manager.

Database. A database is an organised collection of logically related data, stored so that it can be easily accessed, managed and updated. It represents some part of the real world, e.g. a college's students and courses.

DBMS. A Database Management System is software that creates, stores, retrieves, updates and controls access to the database, and acts as an interface between users/applications and the data. Examples: MySQL, Oracle, SQL Server, PostgreSQL.

Benefits of a DBMS

• Controlled redundancy: data is stored once, saving space and avoiding inconsistency.
• Data consistency and integrity: constraints (primary key, foreign key, check) keep data accurate and valid.
• Data sharing: multiple users and applications access the same data simultaneously.
• Data independence: changes in storage or logical structure do not require rewriting application programs.
• Security: user authentication, access privileges and views restrict unauthorised access.
• Backup and recovery: logs and backups restore the database after a crash.
• Concurrency control: transaction management with ACID properties lets many users work safely.
• Efficient querying: SQL, indexing and query optimisation give fast retrieval.
• Standards and decision support: uniform standards, and better, timely information for decision making.
• Reduced application development time through common services.

SQL constraints are rules applied to table columns to limit the type of data that can be stored, ensuring accuracy and integrity.

• NOT NULL: the column cannot hold NULL values.
• UNIQUE: all values in the column (or column set) are distinct; NULL is allowed.
• PRIMARY KEY: uniquely identifies each row; combines NOT NULL and UNIQUE; only one per table.
• FOREIGN KEY: a column referencing the primary key of another table; keeps referential integrity (with ON DELETE/ON UPDATE actions).
• CHECK: restricts values by a condition, e.g. age >= 18.
• DEFAULT: supplies a default value when none is given.

Example:

CREATE TABLE Student (
    id      INT PRIMARY KEY,
    name    VARCHAR(50) NOT NULL,
    email   VARCHAR(80) UNIQUE,
    age     INT CHECK (age >= 16),
    country VARCHAR(20) DEFAULT 'Nepal',
    dept_id INT,
    FOREIGN KEY (dept_id) REFERENCES Department(dept_id)
);

Relational algebra. Relational algebra is a procedural query language consisting of a set of operations that take one or two relations as input and produce a new relation as output. It is the theoretical foundation of SQL.

Fundamental operations

• Selection ($\sigma$): selects rows satisfying a condition. $\sigma_{age>20}(Student)$.
• Projection ($\pi$): selects specified columns and removes duplicates. $\pi_{name,age}(Student)$.
• Union ($\cup$): all tuples in $R$ or $S$ or both; relations must be union-compatible. $R \cup S$.
• Set difference ($-$): tuples in $R$ but not in $S$. $R - S$.
• Cartesian product ($\times$): every tuple of $R$ combined with every tuple of $S$. $R \times S$.
• Rename ($\rho$): renames a relation or attributes. $\rho_{S(a,b)}(R)$.

Additional operations

• Intersection ($\cap$): tuples in both $R$ and $S$.
• Join ($\bowtie$): combines related tuples; theta join with an arbitrary condition, equi-join with equality, natural join on common attributes, and outer joins (left, right, full) that keep unmatched tuples. $R \bowtie_{R.a=S.a} S = \sigma_{R.a=S.a}(R \times S)$.
• Division ($\div$): tuples of $R$ associated with all tuples of $S$, e.g. students who have taken all courses.
• Aggregation ($\mathcal{G}$): functions like SUM, AVG, COUNT, MAX, MIN with grouping.

Candidate key vs primary key

• A candidate key is any minimal set of attributes that uniquely identifies every tuple of a relation. A relation can have several candidate keys.
• The primary key is the one candidate key chosen by the designer to identify tuples. There is exactly one per relation, and it cannot be NULL.

Example: in Student(RollNo, Email, Name), both RollNo and Email are candidate keys; RollNo is chosen as the primary key and Email is an alternate key.

Foreign key. A foreign key is an attribute (or set of attributes) in one relation (the referencing/child table) whose values must match the primary key (or a candidate key) of another relation (the referenced/parent table), or be NULL. It links tables and enforces referential integrity: a child row cannot refer to a non-existent parent row.

CREATE TABLE Department (dept_id INT PRIMARY KEY, dname VARCHAR(30));
CREATE TABLE Student (
    roll INT PRIMARY KEY,
    name VARCHAR(40),
    dept_id INT,
    FOREIGN KEY (dept_id) REFERENCES Department(dept_id)
        ON DELETE CASCADE ON UPDATE CASCADE
);

The referential actions (CASCADE, SET NULL, RESTRICT) define what happens to child rows when a parent row is deleted or updated. A foreign key may repeat in the child table, and a table can have several foreign keys.

Stored procedure. A stored procedure is a named, precompiled set of SQL statements (with control-flow logic) stored in the database server and executed by calling its name. It may take input (IN), output (OUT) or input-output (INOUT) parameters.

Use in a database

• Encapsulates business logic once so many applications can reuse it.
• Reduces network traffic, since one call replaces many statements.
• Faster, because it is compiled and cached.
• Improves security: users can be granted EXECUTE permission without direct table access.
• Easier maintenance: change the logic in one place.

Example (MySQL). Add a new student and return the total count:

DELIMITER //
CREATE PROCEDURE AddStudent(IN p_id INT, IN p_name VARCHAR(50), OUT total INT)
BEGIN
    INSERT INTO Student(id, name) VALUES (p_id, p_name);
    SELECT COUNT(*) INTO total FROM Student;
END //
DELIMITER ;

CALL AddStudent(101, 'Sita', @cnt);
SELECT @cnt;

To remove it: DROP PROCEDURE AddStudent;

Purposes of concurrency control

• Ensure isolation and consistency when transactions run concurrently.
• Prevent problems such as lost update, dirty read, unrepeatable read and phantom.
• Guarantee serializable schedules, equivalent to some serial execution.
• Allow high throughput and resource use while avoiding interference.
• Avoid or handle deadlocks and maintain database integrity.

Two-phase locking (2PL) protocol. Each transaction acquires and releases locks in two distinct phases:

1. Growing phase: the transaction may obtain locks (shared lock-S for reading, exclusive lock-X for writing) but may not release any.
2. Shrinking phase: the transaction may release locks but cannot obtain any new lock.

The point at which a transaction obtains its final lock is the lock point. Once it releases its first lock, it enters the shrinking phase.

Lock compatibility: S is compatible with S only; X conflicts with S and X. Lock upgrade (S to X) is allowed in the growing phase and downgrade in the shrinking phase.

Properties

• 2PL guarantees conflict serializability; transactions can be serialized in lock-point order.
• It does not prevent deadlock, and does not avoid cascading rollbacks.

Variants

• Strict 2PL: holds all exclusive locks until commit/abort, so avoiding cascading rollbacks.
• Rigorous 2PL: holds all locks (shared and exclusive) until commit/abort.
• Conservative 2PL: acquires all locks before starting, so it is deadlock-free.

Database security. Database security means protecting the database against threats to its confidentiality, integrity and availability, through measures that prevent unauthorised access, modification, destruction or disclosure of data. It is implemented using:

• Authentication (user ID/password) and authorisation (privileges via GRANT/REVOKE).
• Access control (discretionary and mandatory), views to hide data.
• Encryption of stored and transmitted data.
• Auditing and logging, backups, and firewalls.
• Protection against threats such as SQL injection.

Steps of query processing

1. Parsing and translation: the query is checked for syntax, validated against the data dictionary (tables, columns, privileges), and converted into an internal form, i.e. a relational algebra expression/parse tree.
2. Optimization: the optimizer generates alternative equivalent evaluation plans (e.g. different join orders, index use), estimates their cost (disk I/O, CPU) using statistics, and selects the cheapest plan.
3. Evaluation (execution): the query execution engine runs the chosen plan, accessing the stored data through the storage manager, and returns the result to the user.

Flow: SQL query → Parser/Translator → Relational algebra → Optimizer (with statistics) → Execution plan → Evaluation engine → Output.

(a) Functional dependencies. A functional dependency $X \rightarrow Y$ means that each value of $X$ determines exactly one value of $Y$.

• Fully functional dependency: $Y$ depends on the whole of a composite key $X$ and on no proper subset of it. For example, in $\text{Enrol}(\underline{StudentID, CourseID}, Grade)$, $\{StudentID, CourseID\} \rightarrow Grade$ is full, because neither attribute alone determines the grade.
• Partial functional dependency: $Y$ depends on only a part of a composite candidate key. For example, in $\text{Enrol}(\underline{StudentID, CourseID}, Grade, StudentName)$, $StudentID \rightarrow StudentName$ is partial, because the name depends on just one part of the key.

(b) Second Normal Form (2NF). A relation is in 2NF if it is in 1NF (atomic values only) and every non-prime attribute is fully functionally dependent on every candidate key, so there are no partial dependencies. Only relations with a composite key can violate 2NF.

Example: $R(\underline{StudentID, CourseID}, StudentName, CourseTitle, Grade)$ with $StudentID \rightarrow StudentName$ and $CourseID \rightarrow CourseTitle$.

Both are partial dependencies, so we decompose:

• $Student(\underline{StudentID}, StudentName)$
• $Course(\underline{CourseID}, CourseTitle)$
• $Enrol(\underline{StudentID, CourseID}, Grade)$

This removes the update, insertion and deletion anomalies caused by repeating names and titles.

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

Example: $Employee(\underline{EmpID}, EmpName, DeptID, DeptName)$ with $EmpID \rightarrow DeptID$ and $DeptID \rightarrow DeptName$. Here $EmpID \rightarrow DeptName$ holds only transitively through $DeptID$, so we decompose:

• $Employee(\underline{EmpID}, EmpName, DeptID)$
• $Department(\underline{DeptID}, DeptName)$

Each fact is now stored once, and the decomposition is lossless and dependency preserving.

(a) Join operations. A join combines rows of two tables on a condition. Take $Student(SID, Name, DID)$ and $Dept(DID, DName)$.

• Inner join (equi/natural join): returns only matching rows. SELECT S.Name, D.DName FROM Student S INNER JOIN Dept D ON S.DID = D.DID; Result: (Ram, Computer), (Sita, Science).
• Left outer join: all rows of the left table, with NULL for non-matches. The query above with LEFT JOIN gives the two rows plus (Hari, NULL).
• Right outer join: all rows of the right table. It gives the two matches plus (NULL, Law).
• Full outer join: all rows from both sides, so it gives all four rows above.
• Cross join: the Cartesian product, which here has $3 \times 3 = 9$ rows.
• Self join: a table joined to itself using aliases, for example to find employees and their managers.
• Natural join: an equi-join on all common attribute names, with the duplicate column dropped.

(b) ER diagram for the shipment company.

Entities and attributes:

• RetailCenter (CenterID, Name, Address)
• ShippedItem (ItemID, Weight, Description, ReceivedDate, DestinationAddress)
• TransportationEvent (EventID, Type [flight/truck], ScheduledDeparture, ScheduledArrival, FromLocation, ToLocation). Because events follow a regular schedule, this entity can be seen as a Schedule entity of recurring services.

Relationships:

• RetailCenter 1 --- receives --- N ShippedItem. Every item is received at the single center, so the participation of ShippedItem is total.
• ShippedItem M --- travels_via --- N TransportationEvent. An item may use one or more events (total participation of item), and an event carries many items. The relationship attribute is LoadedDate or SequenceNo, which gives the order of the legs.

[RetailCenter]--1--<receives>==N==[ShippedItem]==M--<travels_via>--N--[TransportationEvent]

Here == denotes total participation and -- denotes partial participation. Since there is a single retail center, receives may be dropped in a simplified model, and ShippedItem then becomes the main entity linked to TransportationEvent.

Mapping to relations:

• ShippedItem(ItemID, ..., CenterID FK)
• TransportationEvent(EventID, ...)
• Travels_via(ItemID FK, EventID FK, SequenceNo), with a composite key $(ItemID, EventID)$.

Tables: Book(Bookid, Title, Publisher, PublishedDate, Price), Book_Authors(Bookid, AuthorName), Borrower(CardNo, Name, Address, Contact), Bookissue(BookId, CardNo, IssuedDate, DueDate).

(a) Books taken by Ramesh Sharma

SELECT B.Title
FROM Book B
JOIN Bookissue I ON B.Bookid = I.BookId
JOIN Borrower R ON I.CardNo = R.CardNo
WHERE R.Name = 'Ramesh Sharma';

(b) Issued book name and borrower's name, issued before 15 May 2023 and due after 15 June 2023

SELECT B.Title, R.Name
FROM Bookissue I
JOIN Book B ON B.Bookid = I.BookId
JOIN Borrower R ON R.CardNo = I.CardNo
WHERE I.IssuedDate < '2023-05-15'
  AND I.DueDate > '2023-06-15';

(c) Borrowers who have taken a book written by Laxmi Prashad Devkota

SELECT DISTINCT R.Name
FROM Borrower R
JOIN Bookissue I ON R.CardNo = I.CardNo
JOIN Book_Authors A ON A.Bookid = I.BookId
WHERE A.AuthorName = 'Laxmi Prashad Devkota';

(d) Number of books issued on 25 April 2023

SELECT COUNT(*) AS BooksIssued
FROM Bookissue
WHERE IssuedDate = '2023-04-25';

Database system. A database system is a collection of interrelated, persistent data (the database) together with the database management system (DBMS) software that is used to define, store, retrieve, secure and manage that data, and the application programs that use it. The DBMS acts as the interface between users and the stored data. Examples of DBMSs are MySQL, Oracle, PostgreSQL and SQL Server.

Merits of DBMS

• Reduced data redundancy and inconsistency, since data is stored centrally.
• Data sharing among many users and applications.
• Data independence, so that structure changes do not affect programs.
• Data integrity through constraints.
• Security through authorization and access control.
• Concurrency control, so many users can work together safely.
• Backup and recovery after failures.
• Standard query language (SQL) for easy retrieval, and enforcement of standards.

Demerits of DBMS

• High cost of software, hardware and trained personnel.
• Complexity of design and administration.
• Large size, requiring more memory and storage.
• Performance overhead for simple applications compared with file processing.
• A central failure can affect all users, so there is a higher impact of failure.
• Conversion from existing file systems is costly and time consuming.

Three schema architecture (ANSI/SPARC). It separates the user view of data from the physical storage in three levels, which supports data independence.

  External level   [View 1] [View 2] ... [View n]
                        |  external/conceptual mapping
  Conceptual level      [ Conceptual schema ]
                        |  conceptual/internal mapping
  Internal level        [ Internal (physical) schema ]
                        |
                    Stored database

1. External (view) level: the highest level. It describes the part of the database relevant to each user group through many external schemas (views), and hides the rest of the data. A teacher may see only marks and a student only their own record.
2. Conceptual (logical) level: one conceptual schema that describes the whole database for the community of users: entities, attributes, relationships, data types and constraints. It hides physical storage details and is designed by the DBA.
3. Internal (physical) level: describes how the data is physically stored, including file organization, indexes, access paths, record placement and compression.

Mappings convert between levels, so a request on a view is translated to the conceptual schema and then to the stored data.

Data independence:

• Logical data independence is the ability to change the conceptual schema without changing the external schemas.
• Physical data independence is the ability to change the internal schema without changing the conceptual schema.

Entity. An entity is a real-world object that can be distinctly identified, such as a student, employee, course or book. A collection of similar entities forms an entity set.

Attributes. Attributes are the properties that describe an entity. For example, the entity Student has attributes RollNo, Name, Address and DOB. Attributes can be:

• simple or composite (Name = First + Last),
• single-valued or multi-valued (PhoneNo),
• stored or derived (Age from DOB),
• key attributes, which uniquely identify the entity.

Strong versus weak entity set

Example: Employee (strong, key EmpID) and Dependent (weak). Dependent has only the partial key DependentName, and is identified by combining it with the owner's EmpID. The primary key is therefore $(EmpID, DependentName)$. If the employee is deleted, the dependents are deleted too.

Why integrity constraints are used. Integrity constraints are rules enforced by the DBMS to keep the data accurate, valid and consistent. They prevent invalid data entering the database, whether through user error or application bugs, and preserve the correct relationships between tables.

Types of integrity constraints

1. Domain constraint: the value of an attribute must come from its domain (data type, range, format). Example: Age INT CHECK (Age >= 0 AND Age <= 120).
2. Entity integrity: the primary key cannot be NULL and must be unique. Example: RollNo in Student.
3. Referential integrity: a foreign key value must match an existing primary key value in the referenced table, or be NULL. Example: Student.DeptID must exist in Department.DeptID.
4. Key (uniqueness) constraint: no two tuples have the same value for the key, as with UNIQUE (Email).
5. NOT NULL constraint: a column must always have a value.
6. Semantic/business rules: enforced with CHECK constraints or triggers.

CREATE TABLE Department (
  DeptID INT PRIMARY KEY,
  DName  VARCHAR(30) NOT NULL UNIQUE
);
CREATE TABLE Student (
  RollNo INT PRIMARY KEY,
  Name   VARCHAR(40) NOT NULL,
  Age    INT CHECK (Age >= 15),
  DeptID INT,
  FOREIGN KEY (DeptID) REFERENCES Department(DeptID)
);

Inserting a student with a non-existent DeptID, or with a duplicate RollNo, is rejected by the DBMS.

Functional dependency (FD). An FD $X \rightarrow Y$ between sets of attributes of a relation means that whenever two tuples agree on $X$, they must agree on $Y$. That is, $X$ uniquely determines $Y$. For example, $RollNo \rightarrow Name$.

Types of functional dependency

1. Trivial FD: $X \rightarrow Y$ where $Y \subseteq X$, for example $\{RollNo, Name\} \rightarrow Name$. Non-trivial FD: $Y \not\subseteq X$, for example $RollNo \rightarrow Name$.
2. Fully functional dependency: $Y$ depends on all of $X$ and not on any proper subset of $X$. For example, $\{StudentID, CourseID\} \rightarrow Grade$.
3. Partial dependency: $Y$ depends on a proper subset of the key. For example, with key $\{StudentID, CourseID\}$, $StudentID \rightarrow StudentName$.
4. Transitive dependency: if $X \rightarrow Y$ and $Y \rightarrow Z$ (and $Y \not\rightarrow X$), then $X \rightarrow Z$ holds transitively. For example, $EmpID \rightarrow DeptID \rightarrow DeptName$.
5. Multivalued dependency ($X \twoheadrightarrow Y$): $X$ determines a set of values of $Y$ independently of the other attributes. For example, $Course \twoheadrightarrow Teacher$ and $Course \twoheadrightarrow Book$ in a Course-Teacher-Book relation.

FDs are used to find keys and to normalize relations (2NF, 3NF, BCNF).

Discretionary access control (DAC). Access is granted at the discretion of the owner of an object. The owner (or a user with grant option) decides who gets which privileges, and can pass the privileges on to others. It is flexible and implemented with GRANT and REVOKE.

Example: GRANT SELECT, UPDATE ON Student TO ram WITH GRANT OPTION; Ram can now also grant these rights to another user.

Mandatory access control (MAC). Access is decided by the system according to security classifications. Objects are given classes (Top Secret, Secret, Confidential, Unclassified) and users are given clearances. The Bell-LaPadula rules apply: a subject may read an object only if its clearance is greater than or equal to the object's class (no read up), and may write only if the object's class is greater than or equal to its clearance (no write down). Owners cannot change these rules.

Example: in a defence database, a user with Confidential clearance cannot read Secret records, even if the owner wants to share them.

ACID properties. A transaction is a logical unit of work, and the DBMS guarantees the following properties.

• Atomicity: all operations of a transaction happen or none do. If a failure occurs midway, the changes are rolled back. Example: in a transfer of Rs 500 from A to B, either both the debit and the credit happen or neither does.
• Consistency: a transaction takes the database from one consistent state to another, preserving integrity constraints. The total of A + B stays the same after the transfer.
• Isolation: concurrent transactions do not interfere, and each appears to run alone. The intermediate state of one transaction is not visible to others.
• Durability: once a transaction commits, its changes persist even after a system crash, through logs and recovery.

Serializability. A schedule (an interleaving of operations of concurrent transactions) is serializable if its effect is equal to that of some serial schedule, in which transactions run one after another. It guarantees correctness of concurrent execution.

• Conflict serializability: a schedule is conflict serializable if it can be converted into a serial schedule by swapping non-conflicting operations. Two operations conflict if they belong to different transactions, access the same data item, and at least one is a write. It is tested with a precedence graph, with an edge $T_i \rightarrow T_j$ for each conflict where $T_i$ operates first. The schedule is conflict serializable if and only if the graph has no cycle.
• View serializability: a schedule is view equivalent to a serial schedule if the initial reads, the read-from relationships and the final writes are the same. Every conflict serializable schedule is view serializable, but not the reverse.

Why normalization is required. Normalization organizes relations to remove redundancy and avoid the anomalies that come from it. Without it we get:

• Update anomaly: the same fact must be changed in many rows, and missing one causes inconsistency.
• Insertion anomaly: a fact cannot be recorded without unrelated data.
• Deletion anomaly: deleting a row accidentally removes other facts.

It also saves storage and gives a cleaner design. It works by decomposing relations using functional dependencies.

First Normal Form (1NF). All attribute values are atomic, with no repeating groups or multivalued attributes.

Example: $Student(RollNo, Name, Phones)$ with Phones = "9841, 9851" is not in 1NF. We make it 1NF by giving one phone per row: $Student(\underline{RollNo, Phone}, Name)$.

Second Normal Form (2NF). The relation is in 1NF and there is no partial dependency of a non-prime attribute on part of a composite key.

Example: $Enrol(\underline{RollNo, CourseID}, StudentName, Grade)$ with $RollNo \rightarrow StudentName$. Decompose into $Student(\underline{RollNo}, StudentName)$ and $Enrol(\underline{RollNo, CourseID}, Grade)$.

Third Normal Form (3NF). The relation is in 2NF and there is no transitive dependency of a non-prime attribute on a key.

Example: $Employee(\underline{EmpID}, Name, DeptID, DeptName)$ with $DeptID \rightarrow DeptName$. Decompose into $Employee(\underline{EmpID}, Name, DeptID)$ and $Department(\underline{DeptID}, DeptName)$.

Each step is lossless, and the result stores every fact in exactly one place.

Participation constraints. A participation constraint specifies whether every entity of an entity set must take part in a relationship set.

• Total participation: every entity must participate in at least one relationship instance. It is drawn with a double line from the entity to the relationship. Example: every Employee must belong to a Department.
• Partial participation: some entities may not participate. It is drawn with a single line. Example: not every Employee manages a Department.

Together with cardinality (1:1, 1:N, M:N), participation constraints show the minimum and maximum number of relationship instances an entity can have. A weak entity always participates totally in its identifying relationship.

E-R diagram for the car insurance company

Entities:

• Customer (CustID, Name, Address, Phone)
• Car (RegNo, Model, Year)
• Accident (ReportNo, Date, Location, DamageAmount)
• Policy (PolicyNo, StartDate, EndDate)
• Payment (PaymentNo, PeriodFrom, PeriodTo, DueDate, ReceivedDate). This is a weak entity, identified through Policy.

Relationships:

[Customer] 1 ---<owns>=== N [Car]         (a car has an owner: total on Car)
[Car] 1 ---<involved_in>--- N [Accident]  (zero or more accidents: partial on Car)
[Policy] 1 ---<covers>=== N [Car]         (a policy covers one or more cars: total on Policy)
[Policy] 1 ===<has>=== N ((Payment))      (identifying; one or more payments: total on Policy)

• A customer owns one or more cars, so Customer participates totally in owns.
• A car has zero to many accidents, so participation in involved_in is partial on the Car side. An accident belongs to exactly one car.
• A policy covers one or more cars (total on Policy), and each car is covered by one policy.
• A policy has one or more premium payments (total), and Payment is a weak entity with the partial key PaymentNo (or DueDate), so its key is $(PolicyNo, PaymentNo)$.

Relational mapping: Car(RegNo, ..., CustID FK, PolicyNo FK), Accident(ReportNo, ..., RegNo FK), Payment(PolicyNo FK, PaymentNo, PeriodFrom, PeriodTo, DueDate, ReceivedDate).

Tables: Supplier(supplier_id, supplier_name, city), Suppliers(supplier_id, parts_id, quantity), Parts(part_id, part_name, color, weight).

(a) Create the tables

CREATE TABLE Supplier (
  supplier_id   VARCHAR(10) PRIMARY KEY,
  supplier_name VARCHAR(50) NOT NULL,
  city          VARCHAR(30)
);

CREATE TABLE Parts (
  part_id   VARCHAR(10) PRIMARY KEY,
  part_name VARCHAR(50) NOT NULL,
  color     VARCHAR(20),
  weight    DECIMAL(8,2)
);

CREATE TABLE Suppliers (
  supplier_id VARCHAR(10),
  parts_id    VARCHAR(10),
  quantity    INT,
  PRIMARY KEY (supplier_id, parts_id),
  FOREIGN KEY (supplier_id) REFERENCES Supplier(supplier_id),
  FOREIGN KEY (parts_id)    REFERENCES Parts(part_id)
);

(b) Names of suppliers who supplied parts with quantity more than 100, and the names of all parts supplied by "RD Traders"

SELECT DISTINCT S.supplier_name
FROM Supplier S
JOIN Suppliers X ON S.supplier_id = X.supplier_id
WHERE X.quantity > 100;

SELECT P.part_name
FROM Parts P
JOIN Suppliers X ON P.part_id = X.parts_id
JOIN Supplier S  ON S.supplier_id = X.supplier_id
WHERE S.supplier_name = 'RD Traders';

(c) Number of parts supplied by "S02"

SELECT COUNT(parts_id) AS NumParts
FROM Suppliers
WHERE supplier_id = 'S02';

(d) Suppliers located in "KTM"

SELECT supplier_name
FROM Supplier
WHERE city = 'KTM';

Flat file system. A flat file system stores data in simple separate files (text, CSV or fixed-format records), usually one file per application, with no built-in relationships between files. Each application program defines and manages its own file structure, and the data are accessed by sequential or simple indexed methods.

Problems of flat files are redundancy, inconsistency, isolated data, program-data dependence, weak security and no concurrency control.

Advantages of DBMS over a flat file system

1. Less redundancy and inconsistency: data are stored centrally and shared, rather than duplicated across files.
2. Data independence: programs are not affected when file structure or storage changes.
3. Easy and powerful retrieval: SQL answers ad hoc queries without writing new programs.
4. Data integrity: constraints (keys, domain, referential) are enforced by the DBMS.
5. Security: authorization and access control by user or view.
6. Concurrent access: locking and transactions let many users work safely.
7. Backup and recovery: logs and recovery restore data after a crash.
8. Atomic updates: transactions give all-or-nothing behaviour.
9. Relationships and sharing: data from many entities are linked and shared by many applications.

Logical versus physical data independence

Three level database architecture

External level   : View 1 | View 2 | ... | View n
                      (external/conceptual mapping)
Conceptual level : Whole logical structure of the database
                      (conceptual/internal mapping)
Internal level   : Physical storage structure

• External level: the view level. Each user group sees only the part of the database it needs, which also gives security.
• Conceptual level: describes the entire database logically: entities, attributes, relationships, data types and constraints, independent of storage.
• Internal level: describes physical storage, such as file structures, indexes, record formats and access paths.

The mappings between levels provide the two forms of data independence above.

Primary key versus super key

• A super key is any set of one or more attributes that uniquely identifies a tuple. It may contain extra, unnecessary attributes. In $Student(RollNo, Name, Email)$, the sets $\{RollNo\}$, $\{RollNo, Name\}$ and $\{Email, Name\}$ may be super keys.
• A candidate key is a minimal super key, with no redundant attribute.
• A primary key is the one candidate key chosen by the designer to identify tuples. It cannot be NULL or duplicated.

So every primary key is a super key, but not every super key is a primary key. There are many super keys of a relation, but only one primary key.

Composite key. A key made of two or more attributes that together identify a tuple uniquely, although none of them alone does. Example: $Enrol(\underline{StudentID, CourseID}, Grade)$ has the composite key $(StudentID, CourseID)$.

Partial key (discriminator). An attribute, or set of attributes, of a weak entity set that identifies the weak entities only among those related to the same owner entity. It is underlined with a dashed line. Example: for the weak entity Dependent of Employee, DependentName is the partial key, and the full key is $(EmpID, DependentName)$.

Selection ($\sigma$). It selects the tuples (rows) of a relation that satisfy a condition: $\sigma_{condition}(R)$. Example: $\sigma_{Level='Bachelor'}(Student)$ returns the bachelor students. The result has the same attributes as $R$.

Projection ($\pi$). It selects the given attributes (columns) of a relation and removes duplicate tuples: $\pi_{A_1, A_2}(R)$. Example: $\pi_{Fname, Lname}(Student)$.

Relational algebra query. The names of students at Bachelor level, living in Birgunj, whose department head is Ramesh Sharma:

$\pi_{Fname,\,Lname}\Big(\sigma_{Level='Bachelor' \,\wedge\, Address='Birgunj' \,\wedge\, HOD='Ramesh Sharma'}\big(Student \bowtie_{Student.Did = Department.Did} Department\big)\Big)$

Equivalently, selecting first and then joining:

$\pi_{Fname,\,Lname}\Big(\sigma_{Level='Bachelor' \,\wedge\, Address='Birgunj'}(Student) \bowtie \sigma_{HOD='Ramesh Sharma'}(Department)\Big)$

Stored procedure. A stored procedure is a named, precompiled block of SQL statements stored in the database and executed with CALL or EXEC. Parameters let the same procedure work with different values.

Ways of passing parameters (MySQL syntax):

• IN: the caller passes a value into the procedure (the default). The procedure cannot change the caller's variable.
• OUT: the procedure sends a value back to the caller through the variable.
• INOUT: the caller passes a value in, and the procedure may modify it and return it.

Parameters are passed by position, for example CALL p(10, @x). Some systems (SQL Server) also allow passing by name.

Example

DELIMITER //
CREATE PROCEDURE GetStudentCount(IN dept INT, OUT total INT)
BEGIN
  SELECT COUNT(*) INTO total
  FROM Student
  WHERE DeptID = dept;
END //
DELIMITER ;

CALL GetStudentCount(2, @cnt);
SELECT @cnt;

Here dept is an IN parameter that carries the input value 2, and total is an OUT parameter whose value is read back through the session variable @cnt. An INOUT example is CREATE PROCEDURE Double(INOUT n INT) SET n = n * 2;.

Timestamp-based concurrency control. Each transaction $T$ gets a unique timestamp $TS(T)$ when it starts (system clock or counter), so older transactions have smaller timestamps. The protocol makes the execution equivalent to the serial order of the timestamps, without using locks, so there are no deadlocks.

Each data item $Q$ keeps two values:

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

Rules

Read(Q) by $T_i$:

• If $TS(T_i) < W\text{-}TS(Q)$, $T_i$ would read a value already overwritten by a younger transaction, so the read is rejected and $T_i$ is rolled back and restarted with a new timestamp.
• Otherwise the read is executed, and $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 younger transaction has already read the old value, so the write is rejected and $T_i$ is rolled back.
• If $TS(T_i) < W\text{-}TS(Q)$, the write is obsolete, so $T_i$ is rolled back. (Thomas' write rule instead ignores such a write.)
• Otherwise the write is executed and $W\text{-}TS(Q) = TS(T_i)$.

Example. Let $TS(T_1)=5$ and $TS(T_2)=10$, with $W\text{-}TS(Q)=0$. If $T_2$ writes $Q$, then $W\text{-}TS(Q)=10$. If $T_1$ now tries to read $Q$, $5 < 10$, so $T_1$ is aborted and restarted.

All conflicting operations are thus ordered by timestamp, which guarantees conflict serializability. The disadvantages are possible starvation by repeated restarts and cascading rollbacks (unless strict timestamping is used).

Indexing. An index is a data structure that speeds up searching for records, like the index of a book. It stores search-key values with pointers to the records.

Types of indexing

1. Primary index: built on the ordered primary key of a sorted data file. It is usually sparse, with one entry per block.
2. Clustering index: built on a non-key ordering field, where records with the same value are stored together.
3. Secondary index: built on a non-ordering field (candidate or non-key). It is dense and has an entry for every record or value.
4. Dense index: an index entry for every search-key value. Sparse index: entries for only some values (one per block).
5. Multilevel index: an index on the index, to reduce search steps.
6. B-tree / B+-tree index: balanced tree structures that give efficient search, insertion, deletion and range queries. They are the most widely used.
7. Hash index: uses a hash function on the key, which is good for equality searches.
8. Bitmap index: bit vectors for columns with few distinct values.

Creating an index in SQL

CREATE INDEX idx_student_name ON Student(Name);

CREATE UNIQUE INDEX idx_student_email ON Student(Email);

CREATE INDEX idx_dept_level ON Student(DeptID, Level);   -- composite index

DROP INDEX idx_student_name ON Student;

Queries such as SELECT * FROM Student WHERE Name = 'Ram'; can then use idx_student_name instead of scanning the whole table. The trade-off is extra storage and slower inserts and updates.

Advantages of normalization

Normalization is the process of organising relations to reduce redundancy and avoid anomalies. Its advantages are:

• Less redundancy: each fact is stored once, so storage is saved.
• No update, insertion or deletion anomalies: a change is made in one place only.
• Better data integrity and consistency: dependencies are enforced through keys.
• Smaller, well-structured tables: easier to maintain, index and query specific data.
• Flexible design: new data or attributes can be added with little effect on existing tables.

Third Normal Form (3NF)

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

Example: STUDENT(SID, Name, DeptID, DeptName) with $SID \to DeptID$ and $DeptID \to DeptName$. Here $SID \to DeptName$ is transitive, so the relation is not in 3NF. Decompose into:

• STUDENT(SID, Name, DeptID)
• DEPARTMENT(DeptID, DeptName)

Both are now in 3NF.

Boyce-Codd Normal Form (BCNF)

A relation is in BCNF if for every non-trivial FD $X \to Y$, $X$ is a superkey. It is stricter than 3NF: 3NF allows $X \to A$ when $A$ is prime, BCNF does not.

Example: COURSE_TEACH(Student, Course, Teacher) with FDs $(Student, Course) \to Teacher$ and $Teacher \to Course$ (each teacher teaches one course). Candidate keys are $(Student, Course)$ and $(Student, Teacher)$. The relation is in 3NF because $Course$ is prime, but $Teacher \to Course$ violates BCNF as $Teacher$ is not a superkey. Decompose into:

• TEACHES(Teacher, Course)
• ENROLS(Student, Teacher)

Now every determinant is a key, so both relations are in BCNF.

Mapping an ER model to the relational model

An ER schema is converted to relations using the following steps.

1. Strong entity sets: each becomes a relation with its simple attributes; composite attributes are flattened into their components; the key attribute becomes the primary key.
2. Weak entity sets: become a relation containing its own attributes plus the primary key of the owner entity as a foreign key. The primary key is (owner key + partial key).
3. Multivalued attributes: become a separate relation holding the entity's key and the attribute value; the key of the new relation is the combination of both.
4. 1:1 relationship: put the primary key of one side as a foreign key in the other (preferably the side with total participation).
5. 1:N relationship: put the primary key of the "1" side as a foreign key in the "N" side relation.
6. M:N relationship: create a new relation with the primary keys of both entities as foreign keys; their combination is the primary key. Relationship attributes are added to it.
7. Higher-degree relationships: a new relation containing the keys of all participating entities.
8. Specialization/generalization: either one relation per entity (subclass has superclass key), or a single relation with a type attribute.

Example

ER schema: STUDENT(SID, Name, {Phone}), DEPARTMENT(DID, DName), COURSE(CID, Title), relationships BELONGS_TO (DEPARTMENT 1 : N STUDENT) and ENROLLS (STUDENT M : N COURSE, attribute Grade).

Relational schema:

• DEPARTMENT(DID, DName)
• STUDENT(SID, Name, DID) where DID is a foreign key to DEPARTMENT (1:N mapping)
• STUDENT_PHONE(SID, Phone) where SID is a foreign key (multivalued attribute)
• COURSE(CID, Title)
• ENROLLS(SID, CID, Grade) with primary key $(SID, CID)$ and both as foreign keys (M:N mapping)

(a) An inner join combines rows from two tables only where the join condition is satisfied; rows with no match in the other table are excluded.

To find customers booked on a flight to 'South Wales', join Customer, Booking and Flight:

SELECT DISTINCT c.Name
FROM Customer c
INNER JOIN Booking b ON c.Cid = b.Cid
INNER JOIN Flight f ON b.FlightID = f.FlightID
WHERE f.Destination = 'South Wales';

(b)

Unary (recursive) relationship: a relationship in which an entity set participates more than once, in different roles, so the degree is 1. Example: EMPLOYEE supervises EMPLOYEE; one employee acts as a supervisor and others as subordinates. Another example is a person being married to a person.

Ternary relationship: a relationship among three entity sets, so the degree is 3. Example: SUPPLY relating SUPPLIER, PROJECT and PART: a supplier supplies a part to a project. It cannot in general be replaced by three binary relationships without losing information. Another example: DOCTOR prescribes MEDICINE to PATIENT.

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

ACID properties

1. Atomicity: all operations of a transaction are performed or none are ("all or nothing"). If the system fails after debiting A but before crediting B, the debit is rolled back.
2. Consistency: a transaction takes the database from one valid state to another, preserving integrity constraints. In the transfer, the sum $A + B$ is the same before and after.
3. Isolation: concurrent transactions behave as if executed serially; intermediate results of one are invisible to others. Another transaction reading A and B mid-transfer must not see the inconsistent total.
4. Durability: once a transaction commits, its changes persist even after a crash, ensured by logs and recovery.

Example: T: read(A); A = A - 500; write(A); read(B); B = B + 500; write(B); commit. If A = 2000, B = 1000, after commit A = 1500 and B = 1500, the total stays 3000 (consistency), and the change survives a failure (durability).

Physical data independence is the ability to change the physical (internal) schema without changing the conceptual (logical) schema or application programs. Changes such as moving files to another disk, changing file organisation, adding or removing an index, or changing storage structures affect only the internal-to-conceptual mapping. Example: adding an index on Student(Name) speeds up queries but no application needs rewriting. It is relatively easy to achieve.

Logical data independence is the ability to change the conceptual schema without changing external schemas (user views) or application programs. Changes such as adding a new attribute or entity, or splitting or merging tables, are absorbed by modifying the external-to-conceptual mapping. Example: adding an Email column to Student does not disturb programs that do not use it. It is harder to achieve because applications depend closely on the logical structure.

Both are provided by the three-schema architecture (external, conceptual, internal).

A stored procedure is a named, precompiled block of SQL and procedural statements stored in the database and executed on demand with a call. It can take parameters, reduces network traffic, improves reuse, performance and security.

CREATE PROCEDURE raise_salary(p_id NUMBER, p_pct NUMBER) AS
BEGIN
  UPDATE employee SET salary = salary * (1 + p_pct/100) WHERE eid = p_id;
END;

A trigger is a stored program that executes automatically when an INSERT, UPDATE or DELETE event occurs on a table.

Statement-level trigger: fires once per triggering SQL statement, regardless of how many rows are affected (even zero). It is the default when FOR EACH ROW is omitted. Used for auditing or restrictions on the operation as a whole.

CREATE TRIGGER trg_stmt
BEFORE DELETE ON student
BEGIN
  INSERT INTO audit_log VALUES ('DELETE on student', SYSDATE);
END;

Row-level (multi-row enabled) trigger: fires once for each row affected by the statement, so a statement that updates 100 rows fires it 100 times. It uses FOR EACH ROW and can access old and new values through :OLD and :NEW.

CREATE TRIGGER trg_row
AFTER UPDATE OF salary ON employee
FOR EACH ROW
BEGIN
  INSERT INTO sal_audit VALUES (:OLD.eid, :OLD.salary, :NEW.salary);
END;

A schedule is a chronological ordering of the operations (read, write, commit, abort) of a set of concurrent transactions, 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.

A schedule is serializable if its effect is equivalent to that of some serial schedule of the same transactions. Serializability guarantees correctness of concurrent execution.

Example: with $T_1$: R(A), W(A) and $T_2$: R(B), W(B), the interleaving R1(A), R2(B), W1(A), W2(B) is serializable because the transactions touch different items and it equals $T_1$ then $T_2$. If both accessed A with conflicting writes in a cyclic order, it would not be.

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$ on the same item. Conflicts: R-W, W-R, W-W by different transactions.
3. If the graph has no cycle, the schedule is conflict serializable, and a topological order of the graph gives an equivalent serial schedule. If there is a cycle, it is not conflict serializable.

Example: W1(A), R2(A), W2(B), R1(B) gives edges $T_1 \to T_2$ (on A) and $T_2 \to T_1$ (on B), a cycle, so not serializable.