Database Management System

Database recovery: restoring the database to a correct, consistent state after a failure, so committed transactions persist and uncommitted ones leave no effect.

Shadow paging: recovery without a log, using a page table.

 Current page table      Disk pages            Shadow page table
 1 --------------------> page 1 (old)  <-----------------  1
 2 --------------------> page 2' (new) ;  page 2 (old) <--  2
 3 --------------------> page 3 (old)  <-----------------  3

1. At transaction start, the current page table is copied into the shadow page table, saved on disk and never altered.
2. On an update to page 2, a new copy 2' is written in a free block; only the current table points to it.
3. Commit: the current table becomes the new shadow table via an atomic pointer switch; old pages are freed.
4. Failure: discard the current table and new pages; the shadow table gives the original consistent database. No undo/redo needed.

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 them.

Working

1. At the start of a transaction the current page table is copied to a shadow page table, which is saved on disk and never changed during the transaction. Both initially point to the same pages.
2. When a page is first written, a new copy of the page is created on a free block, the current table points to the new copy and the update is done there. The shadow table still points to the old page.
3. Commit: the current page table is written to disk and becomes the new shadow table (by switching a pointer to it atomically). Old pages are freed.

Recovery: after a crash or failure before commit, the current table is discarded and the shadow table is used, so the database returns to its state before the transaction. No undo/redo is needed.

Advantages: no log overhead, fast recovery. Disadvantages: data fragmentation, garbage collection, copying of page table, hard in concurrent transactions.

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

• Logical data independence - the conceptual schema can change (add/remove an attribute or entity) without changing external schemas or application programs.
• Physical data independence - the internal schema can change (new file organisation, indexes, storage device) without changing the conceptual schema or external views.

How the three-schema architecture ensures it

The architecture has external, conceptual and internal levels, joined by two mappings.

• Conceptual/internal mapping: when storage structure changes, only this mapping is modified, so the conceptual schema (and everything above it) is unaffected: physical independence.
• External/conceptual mapping: when the conceptual schema changes, the mapping is adjusted so that views stay the same: logical independence.

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

Database recovery is the process of restoring the database to the most recent consistent state that existed before a failure (transaction, system or media failure), ensuring atomicity and durability of transactions.

Shadow paging

The database is made of fixed-size pages, located through a page table.

1. When a transaction starts, the current page table is copied as the shadow page table and stored on disk; it is never modified during the transaction.
2. On a write, the page is not overwritten: a new copy is made in a free block and the current page table points to it. The shadow table keeps pointing to the original page.
3. On commit, the current table is written to disk and becomes the new shadow table (an atomic pointer switch).
4. On failure/abort, the current table and the new pages are discarded and the shadow table is used, restoring the pre-transaction state.

It requires no log and no undo/redo, and gives fast recovery, but suffers from page fragmentation, garbage collection and difficulty with concurrent transactions.

Three-schema architecture

   External level :  View A   View B   View C
                        \       |       /
                   external/conceptual mapping
   Conceptual level:     Conceptual schema
                   conceptual/internal mapping
   Internal level :      Internal schema
                              |
                       Physical database

• External - user views of parts of the database.
• Conceptual - the logical structure of the entire database for the community.
• Internal - physical storage structure.

Logical vs physical data independence

An E-R (Entity-Relationship) diagram is a graphical model of the data of an organisation. It shows the entities, their attributes and the relationships among them. It is used to design a database at the conceptual level, before it is mapped to relational tables.

Symbols used

Example: STUDENT (rectangle) is linked through the diamond ENROLLS to COURSE (rectangle) with cardinality M:N, and Roll_no (underlined ellipse) is the key of STUDENT.

Transaction: a logical unit of database work made of one or more read and write operations that takes the database from one consistent state to another. Either all its operations are done or none is. Example: transferring Rs 1,000 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". If it fails midway, all its changes are undone (rolled back). Handled by the recovery manager.
2. Consistency: a transaction takes the database from one valid state to another, preserving all integrity constraints. In the transfer example, the total A + B stays the same.
3. Isolation: concurrent transactions do not interfere. Each behaves as if it were running alone, and intermediate results are hidden from others. Handled by concurrency control.
4. Durability: once a transaction commits, its changes are permanent and survive system failures. Handled by logs and recovery.

Assume the usual company schema:

EMPLOYEE(Fname, Lname, Ssn, Salary, Dno), DEPARTMENT(Dnumber, Dname), PROJECT(Pnumber, Pname, Dnum), WORKS_ON(Essn, Pno, Hours), DEPENDENT(Essn, Dependent_name, ...), DEPT_LOCATIONS(Dnumber, Dlocation).

(a) All attributes of employees in the 'Computer' department (number 5):

SELECT *
FROM EMPLOYEE
WHERE Dno = 5;

(b) For each department, the number, number of employees and average salary:

SELECT Dno, COUNT(*) AS Num_Employees, AVG(Salary) AS Avg_Salary
FROM EMPLOYEE
GROUP BY Dno;

(c) Projects with more than two employees, giving the number, name and employee count:

SELECT P.Pnumber, P.Pname, COUNT(*) AS Num_Employees
FROM PROJECT P, WORKS_ON W
WHERE P.Pnumber = W.Pno
GROUP BY P.Pnumber, P.Pname
HAVING COUNT(*) > 2;

(d) Relational algebra, employees in department 10 or with salary above Rs 50,000:

$\sigma_{Dno=10 \ \lor\ Salary>50000}(EMPLOYEE)$

(e) Relational algebra, names of employees with no dependents:

$\pi_{Fname,Lname}\Big(EMPLOYEE \bowtie_{Ssn=Essn'} \big(\rho_{R(Essn')}(\pi_{Ssn}(EMPLOYEE)) - \rho_{R(Essn')}(\pi_{Essn}(DEPENDENT))\big)\Big)$

In simpler steps:

$NO\_DEP \leftarrow \pi_{Ssn}(EMPLOYEE) - \pi_{Essn}(DEPENDENT)$

$RESULT \leftarrow \pi_{Fname,Lname}(NO\_DEP \bowtie_{Ssn=Ssn} EMPLOYEE)$

Here the set difference gives the Ssn values that appear in EMPLOYEE but never in DEPENDENT, and the join then recovers their names.

Database users are classified by how they interact with the database.

1. Database Administrator (DBA): controls the whole database system. The DBA defines the schema, grants access and authorisation, monitors performance, and manages backup and recovery.
2. Database designers: identify the data to be stored and choose structures to represent it. They design the conceptual and logical schema, working with the end users.
3. Application programmers (software developers): write programs in a host language (Java, C, PHP) with embedded SQL to give users access to the data.
4. Naive (parametric) end users: use the database through ready-made applications and forms without knowing its details, for example bank tellers and ticket booking clerks.
5. Sophisticated users: engineers, analysts and scientists who write their own queries in SQL or use tools to explore the data.
6. Casual (specialised) users: occasional users such as middle or senior managers who query the database now and then.
7. System analysts: work out the requirements of naive users and specify transactions that meet them.

Primary key: an attribute, or minimal set of attributes, chosen from the candidate keys that uniquely identifies each tuple (row) of a relation. It cannot be NULL or duplicated. Example: Roll_no in STUDENT.

Foreign key: an attribute, or set of attributes, in one relation that refers to the primary key of the same or another relation. Its values must either match an existing primary key value in the referenced relation or be NULL. Example: Dno in EMPLOYEE refers to Dnumber in DEPARTMENT.

CREATE TABLE EMPLOYEE (
  Ssn CHAR(9) PRIMARY KEY,
  Name VARCHAR(40),
  Dno INT,
  FOREIGN KEY (Dno) REFERENCES DEPARTMENT(Dnumber)
);

Why they are required

• The primary key identifies every record uniquely, so records can be searched, updated and deleted exactly. It enforces entity integrity.
• The foreign key links relations, so related data can be combined through joins.
• The foreign key enforces referential integrity. It prevents a record from referring to a non-existent record, such as an employee in a department that does not exist.
• Together they reduce redundancy and keep the data consistent.

Integrity constraints are rules that the data in a database must satisfy at all times, so that the data stay accurate, valid and consistent. The DBMS checks them whenever data are inserted, updated or deleted, and rejects operations that violate them.

Three main categories

1. Inherent (model-based) constraints: rules that are part of the data model itself. For example, a relation cannot have duplicate tuples, and tuples have no ordering.
2. Schema-based (explicit) constraints: rules declared in the schema using DDL. They include:
   • Domain constraints: values must be of the stated type and range.
   • Key constraints: the key attribute values must be unique.
   • Entity integrity: a primary key cannot be NULL.
   • Referential integrity: a foreign key must match an existing primary key or be NULL.
   • NOT NULL, UNIQUE and CHECK constraints.
3. Application-based (semantic) constraints: business rules that cannot be expressed in the schema and are enforced by the application programs or by triggers and assertions. For example, "an employee's salary cannot exceed that of his or her supervisor".

Functional dependency (FD): for a relation $R$, an attribute set $Y$ is functionally dependent on $X$, written $X \to Y$, if each value of $X$ is associated with exactly one value of $Y$. That is, if two tuples agree on $X$ they must agree on $Y$. Example: $Roll\_no \to Name$.

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.

Transitive dependency: $A \to B$ and $B \to C$ (with $B$ not a key) give $A \to C$.

Example

STUDENT(Roll_no, Name, Dept_id, Dept_name) with $Roll\_no \to Dept\_id$ and $Dept\_id \to Dept\_name$.

Here $Dept\_name$ depends transitively on $Roll\_no$ through $Dept\_id$, so the relation is not in 3NF. It causes redundancy, since the department name is repeated for every student, and update anomalies.

Decompose it into:

• STUDENT(Roll_no, Name, Dept_id)
• DEPARTMENT(Dept_id, Dept_name)

Now every non-key attribute depends only on the key, so both relations are in 3NF.

Schedule: a schedule (or history) is the chronological order in which the operations of a set of concurrent transactions are executed. The order of operations inside each transaction is preserved. A schedule is serial if the transactions run one after another without interleaving, and non-serial if their operations are interleaved.

Serializability

A non-serial schedule is serializable if it produces the same result as some serial schedule of the same transactions. Serializability is the accepted criterion of correctness for concurrent execution. A serializable schedule gives the benefits of concurrency without losing consistency. The two main types are conflict serializability and view serializability.

Conflict schedule (conflict serializability)

Two operations conflict if they belong to different transactions, access the same data item, and at least one is a write. So read-write, write-read and write-write pairs conflict.

Two schedules are conflict equivalent if every pair of conflicting operations appears in the same order in both. A schedule is conflict serializable if it is conflict equivalent to a serial schedule.

Testing uses a precedence graph, with one node per transaction and an edge $T_i \to T_j$ if an operation of $T_i$ conflicts with and comes before an operation of $T_j$. The schedule is conflict serializable if and only if the graph has no cycle.

Example: $r_1(X), w_1(X), r_2(X), w_2(X)$ has only the edge $T_1 \to T_2$, so it is conflict serializable and equals the serial order $T_1, T_2$.

Starvation (or livelock) in a DBMS is a situation in which a transaction waits for an indefinitely long time, or is repeatedly rolled back or denied resources, while other transactions continue to proceed. Unlike a deadlock, the system as a whole keeps working, but one transaction never gets to finish.

Causes

• An unfair lock waiting scheme, or priority-based scheduling in which low-priority transactions are always bypassed.
• A transaction that keeps getting selected as the victim in deadlock resolution.
• Shared locks: a stream of readers holding shared locks can stop a writer from ever getting an exclusive lock.

Example

$T_1$ holds a shared lock on item $X$. $T_2$ requests an exclusive lock on $X$ and must wait. Before $T_1$ releases, $T_3$ requests and gets a shared lock on $X$, then $T_4$, and so on. Since new shared locks keep being granted, $T_2$ waits forever.

Solutions

• Use a first-come first-served queue for lock requests.
• Increase the priority of a transaction the longer it waits (ageing).
• Do not repeatedly pick the same transaction as the deadlock victim.

Mapping a 1:N relationship

Use the foreign key approach. Take the primary key of the "one" side and add it as a foreign key in the relation of the "many" side. Any attribute of the relationship also goes to the N side.

Example: DEPARTMENT (1) —WORKS_FOR— (N) EMPLOYEE.

• DEPARTMENT(<u>Dnumber</u>, Dname)
• EMPLOYEE(<u>Ssn</u>, Name, Salary, Dno), where Dno is a foreign key referencing DEPARTMENT(Dnumber)

Mapping an N:M relationship

Create a new relation (a relationship or junction relation). Its attributes are the primary keys of both participating entities, which become foreign keys, plus any attributes of the relationship. The primary key is the combination of the two foreign keys.

Example: EMPLOYEE (N) —WORKS_ON— (M) PROJECT, with the attribute Hours.

• EMPLOYEE(<u>Ssn</u>, Name)
• PROJECT(<u>Pnumber</u>, Pname)
• WORKS_ON(<u>Essn</u>, <u>Pno</u>, Hours), where Essn references EMPLOYEE(Ssn) and Pno references PROJECT(Pnumber)

A separate relation is needed for N:M because a single foreign key column cannot hold multiple values on either side.

NoSQL ("Not Only SQL") refers to non-relational database systems that store and retrieve data in forms other than the fixed tables of relational databases. They use flexible or no schema, scale horizontally across many servers, and handle very large volumes of structured, semi-structured and unstructured data with high availability. They are used in big data and real-time web applications, and commonly follow the BASE model.

Types of NoSQL databases

1. Key-value stores: data are kept as unique key and value pairs, like a hash table. Very fast for simple lookups. Examples: Redis, DynamoDB.
2. Document stores: data are kept as documents, typically JSON or BSON, which can have different structures. Example: MongoDB, CouchDB.
3. Column-family (wide-column) stores: data are stored in columns grouped into families instead of rows, which suits large analytical workloads. Examples: Cassandra, HBase.
4. Graph databases: data are stored as nodes and edges with properties, suited to highly connected data such as social networks and recommendations. Examples: Neo4j, ArangoDB.

Data model: a collection of concepts used to describe the structure of a database, including data types, relationships and constraints. It gives the means to achieve data abstraction. Categories are:

• High-level (conceptual) models, such as the E-R model, which are close to how users see data.
• Representational (logical) models, such as the relational, hierarchical and network models, which are used by many commercial DBMSs.
• Low-level (physical) models, which describe how data are stored in files, with record formats and access paths.

Schema: the overall description of the database, specified at design time. It rarely changes. Also called the intension. Under the three-schema architecture there are the internal schema (physical storage), conceptual schema (the whole database for all users) and external schemas (user views). Example: STUDENT(Roll_no, Name, Dept).

Instance (database state): the actual data stored in the database at a particular moment. It changes with every insert, update or delete. Also called the extension. Example: the set of rows currently in STUDENT.

The schema is like the type declaration of a variable, and the instance is like its current value.

Transaction: a logical unit of work made of one or more database operations (read, write) that must be executed completely or not at all. It is delimited by the statements BEGIN_TRANSACTION and END_TRANSACTION, and must preserve the ACID properties.

State diagram

                   +----------------------- READ/WRITE ----+
                   v                                       |
BEGIN --> [ ACTIVE ] --END_TRANSACTION--> [ PARTIALLY COMMITTED ] --COMMIT--> [ COMMITTED ] --> [ TERMINATED ]
              |                                   |
            ABORT                               ABORT
              v                                   v
           [ FAILED ] ------- rollback --------> (back out)
              |
              v
         [ TERMINATED ]

States

1. Active: the initial state. The transaction stays here while it executes its read and write operations.
2. Partially committed: entered after the last operation has been executed. The changes may still only be in main memory, so a failure could still prevent a safe commit. The system checks whether the changes can be made permanent and writes the log to disk.
3. Committed: entered after successful completion. All changes have been recorded permanently in the database, and the transaction cannot be undone.
4. Failed: entered when normal execution cannot go on, either because of an abort in the active state or because a check in the partially committed state failed.
5. Terminated (aborted): the transaction has left the system. Changes made by a failed transaction are rolled back, and the transaction may then be restarted or killed.

A transaction ends either in the committed state or, after rollback, in the aborted state.

Functional dependency (FD): a constraint between two attribute sets $X$ and $Y$ of a relation $R$, written $X \to Y$. It means that the value of $X$ uniquely determines the value of $Y$, so any two tuples with the same $X$ value must have the same $Y$ value. Example: $Ssn \to Ename$. FDs are used to find keys and to normalise relations.

Four informal quality measures (guidelines) for relational schema design

1. Semantics of the attributes: each relation should represent one entity type or relationship type, so that its meaning is clear. Attributes of several entities should not be mixed in one relation. For example, EMPLOYEE and DEPARTMENT data should be in separate relations, with a foreign key linking them.

2. Reducing redundant information in tuples (and update anomalies): storing the same data many times wastes space and causes anomalies.

   • Insertion anomaly: a new department cannot be recorded without an employee.
   • Deletion anomaly: deleting the last employee of a department removes the department's information.
   • Modification anomaly: a change to a department name must be made in many tuples.

   Base relations should be designed so that no such anomalies occur.

3. Reducing NULL values in tuples: attributes that are often NULL should not be placed in the base relation. NULLs waste space, make joins and aggregate functions ambiguous, and their meaning is unclear (unknown, not applicable, or not recorded). Put such attributes in a separate relation.

4. Disallowing spurious tuples: relations should be designed so that joining them gives back exactly the original information and no false tuples. Decompositions must have the lossless join (non-additive join) property. Relations should be joined only on attributes that are primary key or foreign key pairs.

The Entity-Relationship (E-R) model describes data using entities, attributes and relationships. Its diagram uses the following symbols.

Example: EMPLOYEE (rectangle, with key Ssn) —WORKS_FOR (diamond)— DEPARTMENT (rectangle), with cardinality N:1 and total participation of EMPLOYEE.

NoSQL ("Not Only SQL") systems are non-relational databases designed for large-scale, distributed data storage with flexible schemas, high availability and horizontal scalability. They give up some strict consistency (they follow BASE: Basically Available, Soft state, Eventually consistent) in return for performance and scale.

Characteristics related to data models

• Schema-less or flexible schema: records in the same collection may have different fields, so the structure can change without migration.
• Data are not necessarily stored in tables. Models include key-value, document, column-family and graph.
• Data are often denormalised and aggregated (a whole object stored together), so joins are rarely needed.
• Built for horizontal scaling through sharding and replication across commodity servers.

Characteristics related to query languages

• There is no single standard like SQL. Each system has its own API or query language, for example MongoDB's JSON-style queries and Cassandra's CQL.
• Queries are usually simple, based on a key or a document, with limited or no join and complex multi-table query support.
• Operations are often exposed through simple programming APIs such as get, put and delete, or through REST.
• Some systems provide SQL-like languages (CQL), or map-reduce for batch processing.

System log (transaction log / journal): a sequential, append-only file kept on stable storage in which the DBMS records all operations that change the database. Entries are written before the changes reach the database itself (write-ahead logging).

Purpose

• To recover from failures. After a crash, the log is used to undo the effects of uncommitted transactions and to redo committed transactions whose changes did not reach disk.
• To support transaction rollback, so that atomicity is maintained when a transaction aborts.
• To help ensure durability of committed transactions.

Typical entry types (T is a transaction id)

1. [start_transaction, T]: transaction T has started.
2. [write_item, T, X, old_value, new_value]: T changed item X from the old value to the new value. The old value is used for undo and the new value for redo.
3. [read_item, T, X]: T has read item X (needed only in some protocols).
4. [commit, T]: T finished successfully and its changes can be made permanent.
5. [abort, T]: T was aborted and its changes must be undone.
6. [checkpoint]: marks a point at which the buffers were flushed to disk. Recovery then needs to examine only the log after it.

Normalization is the process of organising the attributes and relations of a database by applying a series of normal forms (1NF, 2NF, 3NF, BCNF), in order to reduce data redundancy and avoid insertion, deletion and update anomalies. It works by decomposing a relation into smaller relations using functional dependencies, without losing information.

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. That is, every non-key attribute depends on the whole of the key, not just a part of it. A relation with a single-attribute key is automatically in 2NF if it is in 1NF.

Example

ENROLL(Student_id, Course_id, Student_name, Grade), with key (Student_id, Course_id).

FDs: $(Student\_id, Course\_id) \to Grade$ and $Student\_id \to Student\_name$.

Student_name depends on only part of the key, so there is a partial dependency and the relation is not in 2NF. The student's name is repeated for each course taken.

Decompose into:

• STUDENT(<u>Student_id</u>, Student_name)
• ENROLL(<u>Student_id</u>, <u>Course_id</u>, Grade)

Now every non-key attribute depends on the full key, so both relations are in 2NF.

Concurrent execution in a multiuser system

In a multiuser DBMS many users submit transactions at the same time. Instead of running them one after another (serially), the system interleaves their operations, for example while one transaction waits for disk I/O the CPU runs another. The interleaved order of operations is a schedule. This improves CPU and disk utilisation, throughput (transactions per second) and response time, especially for short transactions.

Why concurrency control is needed

If interleaving is uncontrolled, the database can be left in an inconsistent state. Problems include:

1. Lost update: two transactions read the same item and both update it, so one update overwrites the other. For example $T_1$ and $T_2$ both read balance 1000. $T_1$ adds 100 and $T_2$ subtracts 50, and the later write wins, so one change is lost.
2. Dirty read (temporary update): a transaction reads a value written by another transaction that later aborts, so it has used data that never existed.
3. Incorrect summary: an aggregate function reads some items before and some after another transaction updates them, giving a wrong total.
4. Unrepeatable read: a transaction reads the same item twice and gets different values because another transaction changed it in between.

Concurrency control protocols, such as locking, timestamp ordering and multiversion methods, make the schedules serializable, so that isolation and consistency are kept while concurrency is still allowed.

Assume the schema:

EMPLOYEE(Fname, Lname, Ssn, Dno), DEPARTMENT(Dnumber, Dname), PROJECT(Pnumber, Pname, Dnum), WORKS_ON(Essn, Pno, Hours).

The name and department number come from EMPLOYEE, and the department name comes from DEPARTMENT through Dno = Dnumber. Only these two relations are needed to answer the query. PROJECT and WORKS_ON are needed only if project details are requested.

Step 1, select John Smith:

$JS \leftarrow \sigma_{Fname='John' \ \land\ Lname='Smith'}(EMPLOYEE)$

Step 2, join with DEPARTMENT:

$JSD \leftarrow JS \bowtie_{Dno=Dnumber} DEPARTMENT$

Step 3, project the required attributes:

$RESULT \leftarrow \pi_{Fname,\,Lname,\,Dno,\,Dname}(JSD)$

As one expression:

$\pi_{Fname,Lname,Dno,Dname}\Big(\sigma_{Fname='John' \land Lname='Smith'}(EMPLOYEE)\bowtie_{Dno=Dnumber}DEPARTMENT\Big)$

Note that selection is applied before the join, so that the join works on a much smaller relation.

A failure is any event that stops a transaction or the DBMS from completing normally, leaving the database possibly inconsistent. Recovery restores a consistent state.

Types of failures

1. Transaction failure - a single transaction aborts because of a logical error (division by zero, bad input, integrity violation) or a system error (deadlock victim).
2. System crash - a hardware, software or power failure (OS bug, power cut) loses the contents of volatile memory (buffers) but disk data remains intact.
3. Disk failure - a head crash, bad sector or controller fault destroys part of the disk data.
4. Physical problems and catastrophes - fire, flood, theft, earthquake, sabotage, or operator mistakes.
5. Concurrency-control enforcement - a transaction is aborted/rolled back to preserve serializability.

Catastrophic failure

A catastrophic failure is one in which the stable storage itself (disk) is damaged or destroyed, e.g. a disk crash, fire or flood, so the database cannot be recovered by the log alone. Recovery needs a backup (archive) copy of the database: the last full backup is restored and the log/redo of committed transactions since the backup is applied. Hence regular backups, off-site copies and mirrored (RAID) disks are used to protect against it.

Relational data model

The relational model (E. F. Codd, 1970) represents the database as a collection of relations. Each relation is a table of rows (tuples) and columns (attributes). Every attribute has a domain (set of allowed atomic values), a relation has a schema $R(A_1, A_2, \dots, A_n)$ and a set of tuples. Integrity is maintained through keys, entity integrity and referential integrity, and data is manipulated by relational algebra/SQL.

Relation versus flat file

Database: an organised collection of logically related data, stored so that it can be easily accessed, managed and updated, e.g. a college's student records. A DBMS is the software that defines, creates, controls and shares it.

Characteristics of the database approach

1. Self-describing nature - the database holds a catalog (metadata) describing structure, types and constraints along with the data.
2. Insulation between programs and data (data abstraction) - program-data and program-operation independence; the structure can change without rewriting programs.
3. Support for multiple views - different users see different customised subsets of the data.
4. Sharing of data and multiuser transaction processing - concurrent access with concurrency control and ACID transactions.
5. Controlled redundancy - data is stored once, avoiding duplication and inconsistency.
6. Integrity and security - constraints, authorisation and access control protect data.
7. Backup and recovery - the DBMS restores data after failures.

The three-schema (ANSI/SPARC) architecture separates the user's view of data from its physical storage using 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 (physical) - the internal schema describes physical storage: file organisation, record layout, indexes, access paths and data compression.
2. Conceptual level (logical) - the conceptual schema describes the structure of the whole database for all users: entities, attributes, relationships, data types and constraints, hiding storage detail. Usually expressed in a representational data model.
3. External level (view) - each external schema (user view) describes the part of the database a particular group of users needs and hides the rest.

DBMS mappings translate requests between levels. The architecture gives logical and physical data independence.

Schedule: the chronological order of operations of a set of concurrent transactions, preserving the order inside each transaction.

Serial schedule - transactions run one after another with no interleaving. For $T_1, T_2$: all of $T_1$ then all of $T_2$ (or the reverse).

Non-serial schedule - operations of different transactions are interleaved.

Serializable schedule - a non-serial schedule whose outcome equals that of some serial schedule, so it is correct.

Example, with $T_1$: R(A), W(A), R(B), W(B) and $T_2$: R(A), W(A):

The non-serial schedule is serializable because it is equivalent to the serial order $T_1 \to T_2$ ($T_2$ never touches B).

Testing conflict serializability (precedence graph)

1. Create a node for each transaction.
2. Add edge $T_i \to T_j$ if an operation of $T_i$ conflicts with a later operation of $T_j$ on the same item (R-W, W-R or W-W with different transactions).
3. The schedule is conflict serializable iff the graph has no cycle. A topological order of the graph gives the equivalent serial schedule.

Example: $S$: R1(A) W1(A) R2(A) W2(A) R1(B) W1(B). Conflicts on A: W1(A) before R2(A) and W2(A), so edge $T_1 \to T_2$. B is only used by $T_1$. The graph $T_1 \to T_2$ has no cycle, so $S$ is serializable, equivalent to $T_1, T_2$.

Counter-example: R1(A) W2(A) W1(A) gives $T_1 \to T_2$ (R1 before W2) and $T_2 \to T_1$ (W2 before W1): a cycle, so it is not serializable.

A transaction is a logical unit of database work, a sequence of read/write operations that takes the database from one consistent state to another (e.g. transferring Rs 500 between accounts). It must satisfy ACID properties.

States of a transaction

          +--> Partially committed --> Committed --+
Active ---+                                         +--> Terminated
          +--> Failed ---------------> Aborted ----+

1. Active - the initial state; the transaction is executing its reads and writes.
2. Partially committed - after the final operation has executed, but changes may still only be in memory buffers.
3. Committed - changes are safely written to the database (log forced to disk); the transaction ended successfully and its effects are permanent.
4. Failed - normal execution cannot continue (error, system failure, or check in the partially committed state fails).
5. Aborted - the transaction is rolled back and the database restored to its state before the transaction. It may then be restarted or killed.

Committed and aborted are the terminal (terminated) states.

(a)

SELECT E.Ename, E.Address
FROM EMPLOYEE E JOIN DEPARTMENT D ON E.Dno = D.Dnumber
WHERE D.Dname = 'Computer';

(b)

SELECT Dno, COUNT(*) AS No_of_employees, AVG(Salary) AS Avg_salary
FROM EMPLOYEE
GROUP BY Dno;

(c) An employee is linked to a project through the department that controls it (Dnum).

SELECT E.Ename, D.Dname, P.Pname
FROM EMPLOYEE E, DEPARTMENT D, PROJECT P
WHERE E.Dno = D.Dnumber AND P.Dnum = D.Dnumber
ORDER BY D.Dname;

(d) $\pi_{Ename,\,Salary}\big(\sigma_{Dno=5}(EMPLOYEE)\big)$

(e) $\pi_{Dname,\,Ename}\big(DEPARTMENT \bowtie_{Mgr\_ssn = Ssn} EMPLOYEE\big)$ which gives the manager's name for each department (project $Ename$ only if just the name is wanted).

Advantages of using a DBMS

1. Controlling redundancy - data is stored once, saving space and avoiding inconsistency.
2. Data consistency and integrity - constraints (key, domain, referential) keep data valid.
3. Data sharing - many users and applications access the same data concurrently.
4. Security - authorisation and access rights restrict who can see or change data.
5. Backup and recovery - the DBMS restores the database after failures.
6. Data independence - programs are insulated from changes in storage structure.
7. Multiple user views and efficient query processing - indexes and query optimisation give fast access, and each user group gets its own view.
8. Standards enforcement and reduced application development time - common naming and formats, and ready-made services like SQL.

An attribute is a property that describes an entity, e.g. the entity STUDENT has attributes Roll_no, Name, Address, Phone.

Types of attributes

1. Simple (atomic) - cannot be divided further, e.g. Roll_no, Gender.
2. Composite - can be divided into smaller parts, e.g. Name = (First, Middle, Last); Address = (Street, City, District).
3. Single-valued - holds one value per entity, e.g. Date_of_birth.
4. Multivalued - can hold several values, e.g. Phone_numbers, Skills (shown with a double ellipse).
5. Derived - computed from another attribute, e.g. Age from Date_of_birth (dashed ellipse).
6. Stored - the base attribute from which a derived one is computed, e.g. Date_of_birth.
7. Key attribute - uniquely identifies each entity, e.g. Roll_no (underlined).
8. Null-valued - value is unknown or not applicable, e.g. Middle_name.

Relation - a table of rows and columns representing a set of tuples over a set of attributes; formally a subset of $D_1 \times D_2 \times \dots \times D_n$.

Schema (relation schema) - the structure of the relation: its name, attributes and domains. It is the design and changes rarely. Example: $STUDENT(Roll\_no, Name, Address, Phone)$.

Instance - the set of tuples in the relation at a particular moment. It changes with every insertion, deletion or update.

Example

Schema: $STUDENT(Roll\_no, Name, Address)$

Instance:

Adding a third row creates a new instance of the same schema.

Normalization is the process of organising relations by decomposing them, using functional dependencies, to remove redundancy and the insertion, deletion and update anomalies.

Second Normal Form (2NF): a relation is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on the whole primary key, i.e. there is no partial dependency on part of a composite key.

Example: $ENROLL(Student\_id, Course\_id, Student\_name, Grade)$ with key $(Student\_id, Course\_id)$.

• $(Student\_id, Course\_id) \to Grade$ (full dependency)
• $Student\_id \to Student\_name$ (partial dependency), so not in 2NF. The student's name repeats for every course.

Decomposition into 2NF

• $STUDENT(\underline{Student\_id}, Student\_name)$
• $ENROLL(\underline{Student\_id}, \underline{Course\_id}, Grade)$

Now each non-key attribute depends on the full key of its relation.

Binary lock - has only two states, locked (1) and unlocked (0), per data item. A transaction must lock item $X$ before accessing it and unlock afterwards; only one transaction can hold the lock at a time.

Shared/exclusive (read/write) lock - three operations: read_lock(X), write_lock(X), unlock(X).

• Shared (S, read) lock - several transactions may hold it on the same item, only to read.
• Exclusive (X, write) lock - only one transaction holds it, to read and write; no other lock is allowed with it.

Difference

A deadlock is a situation in which two or more transactions each wait for a lock held by another in the set, so none can proceed.

Example

$T_1$ waits for $T_2$ and $T_2$ waits for $T_1$: a cycle in the wait-for graph, $T_1 \rightleftarrows T_2$.

Handling: prevention (wait-die, wound-wait, conservative locking of all items first), detection (wait-for graph cycle, then abort a victim transaction) and timeouts.

NoSQL ("Not only SQL") databases are non-relational databases designed to store, retrieve and scale very large volumes of structured, semi-structured and unstructured data across distributed servers. Types: key-value (Redis), document (MongoDB), column-family (Cassandra), graph (Neo4j).

Characteristics

1. Schema-less / flexible schema - records in a collection need not share the same structure.
2. Horizontal scalability - scale out by adding commodity servers (sharding).
3. Distributed and replicated - data copied over nodes for high availability and fault tolerance.
4. High performance - simple data models and no joins give fast reads and writes.
5. BASE rather than ACID - Basically Available, Soft state, Eventual consistency; follows the CAP theorem.
6. Non-relational models - key-value, document, column and graph.
7. Simple APIs - often query by key or through a custom query language instead of full SQL.

Transaction: a logical unit of work consisting of one or more database operations (reads and writes) that must be executed completely or not at all, taking the database from one consistent state to another.

When transactions run concurrently without control, interleaving can cause the following problems.

1. Lost update problem

Two transactions read the same item and both update it; one update overwrites the other.

The correct final value is $100 - 20 + 50 = 130$, but $T_2$ overwrote $T_1$'s update, so 150 is stored: the update of $T_1$ is lost.

2. Dirty read (temporary update) problem

A transaction reads data written by another transaction that has not yet committed and later aborts.

$T_2$ used the value 80, which never legally existed, and may use it to compute and store wrong results.

Both are avoided by concurrency control such as locking (two-phase locking) which ensures serializable, recoverable schedules.

Need for an ER diagram

An Entity-Relationship diagram is a conceptual design of a database before implementation. It: communicates requirements between designer and user, shows entities, attributes and relationships clearly, is independent of any DBMS, helps find mistakes early, and maps easily into relational tables.

Example: University system

Assumptions: a student enrols in many courses and a course has many students; a teacher teaches many courses; a department has many teachers; a student has many dependents (guardians) who are identified only through the student; every course must belong to a department; age is calculated from date of birth; a student may have several phone numbers.

Entities

1. STUDENT(<u>Sid</u>, Name, DOB, /Age/, {Phone})
2. COURSE(<u>Cid</u>, Title, Credit_hours)
3. TEACHER(<u>Tid</u>, Name, Salary)
4. DEPARTMENT(<u>Did</u>, Dname)
5. GUARDIAN (weak entity)(<u>Gname</u> - partial key, Relation)

Relationships

• STUDENT M:N COURSE through ENROLLS (attribute Grade).
• TEACHER M:N COURSE through TEACHES.
• DEPARTMENT 1:N TEACHER through WORKS_IN.
• DEPARTMENT 1:N COURSE through OFFERS; COURSE has total participation (double line).
• STUDENT 1:N GUARDIAN through the identifying relationship HAS (double diamond); GUARDIAN totally participates.

 [Sid]  [Name] [DOB] (Age) ((Phone))
   \      |     |    :     /
    +-----[ STUDENT ]-----+
               |
        <ENROLLS>(Grade)
               |
 [Did]--[DEPARTMENT]==<OFFERS>==[[COURSE]]--<TEACHES>--[TEACHER]
 (rectangle=entity, diamond=relationship, dashed oval=derived /Age/,
  double oval=multivalued {Phone}, double line = total participation,
  double rectangle = weak entity GUARDIAN with partial key Gname)

Here Age is derived (from DOB) and Phone is multivalued. The weak entity GUARDIAN depends on its owner STUDENT.

Need for normalization

Poorly designed relations store the same fact many times. This leads to anomalies:

• Insertion anomaly - cannot add a fact without unrelated data.
• Deletion anomaly - deleting a row loses other facts.
• Update anomaly - a changed value must be updated in many rows or becomes inconsistent.

Normalization decomposes relations, using functional dependencies (FDs), to reduce redundancy, avoid anomalies, save space and keep data consistent, while preserving lossless join and dependencies.

First Normal Form (1NF): all attributes hold only atomic (indivisible) values; no repeating groups or multivalued attributes.

Example: $STUDENT(Sid, Name, Phone)$ with Phone = {9841, 9851} for one student is not in 1NF. Fix: one phone per row: $(1, Ram, 9841)$ and $(1, Ram, 9851)$, or a separate $STUDENT\_PHONE(Sid, Phone)$.

Second Normal Form (2NF): in 1NF and no partial dependency: every non-prime attribute depends on the whole candidate key.

Example: $ENROLL(Sid, Cid, Sname, Grade)$, key $(Sid, Cid)$; $Sid \to Sname$ is partial. Decompose into $STUDENT(Sid, Sname)$ and $ENROLL(Sid, Cid, Grade)$.

Third Normal Form (3NF): in 2NF and no transitive dependency of a non-prime attribute on the key. For every FD $X \to A$, either $X$ is a superkey or $A$ is a prime attribute.

Example: $EMP(Eid, Ename, Dno, Dname)$ with $Eid \to Dno$ and $Dno \to Dname$, so $Eid \to Dname$ is transitive. Decompose into $EMP(Eid, Ename, Dno)$ and $DEPT(Dno, Dname)$.

Assumption: a Department table and an Employee table where each employee belongs to a department.

Create

CREATE TABLE Department (
    Dno    INT PRIMARY KEY,
    Dname  VARCHAR(40) NOT NULL
);

CREATE TABLE Employee (
    Eid     INT PRIMARY KEY,
    Ename   VARCHAR(50) NOT NULL,
    Salary  DECIMAL(10,2) DEFAULT 0,
    Dno     INT,
    FOREIGN KEY (Dno) REFERENCES Department(Dno)
        ON DELETE CASCADE
);

Update

UPDATE Employee SET Salary = Salary * 1.10 WHERE Dno = 2;
ALTER TABLE Employee ADD Phone VARCHAR(15);

Use of CASCADE on delete

ON DELETE CASCADE on a foreign key means that when a row in the parent (referenced) table is deleted, all child rows referencing it are automatically deleted. Thus DELETE FROM Department WHERE Dno = 2; also removes all employees of department 2. This keeps referential integrity without orphan rows. The alternatives are SET NULL, SET DEFAULT and RESTRICT/NO ACTION. Cascade should be used carefully since it can remove much data.

GROUP BY groups rows having the same values in the given column(s) so that aggregate functions (COUNT, SUM, AVG, MAX, MIN) are computed per group.

HAVING filters groups after grouping (conditions on aggregates). WHERE filters individual rows before grouping, and cannot use aggregates.

Syntax

SELECT column, aggregate_function(column)
FROM table
[WHERE row_condition]
GROUP BY column
[HAVING group_condition]
[ORDER BY column];

Example: departments having more than 3 employees, with average salary:

SELECT Dno, COUNT(*) AS Total, AVG(Salary) AS Avg_sal
FROM Employee
WHERE Salary > 10000
GROUP BY Dno
HAVING COUNT(*) > 3;

Order of execution: FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY.

The three-schema architecture (ANSI/SPARC) has three levels:

• External level - many user views; each describes only the data a user group needs.
• Conceptual level - one conceptual schema describing the whole database logically (entities, relationships, constraints), hiding storage details.
• Internal level - the internal schema describing physical storage, file structures, indexes and access paths.

 External views  ->  Conceptual schema  ->  Internal schema
      (mapping)            (mapping)

Data independence

• Logical data independence: the conceptual schema can be altered (add an attribute or table) without changing external views or application programs; only the external/conceptual mapping is adjusted.
• Physical data independence: the internal schema can be altered (change file structure, add an index, move to another disk) without changing the conceptual schema; only the conceptual/internal mapping changes.

Hence, changes at a lower level do not affect the upper levels.

NoSQL databases store data in models other than tables, designed for scale and flexibility; each type has its own storage and retrieval method.

Examples

Key-value (Redis):

SET user:1 "Ram"
GET user:1

Document (MongoDB):

db.students.insertOne({ sid: 10, name: "Aarav", phones: ["9841", "9851"] })
db.students.find({ name: "Aarav" })

Data is distributed over many nodes by sharding (partitioning on a key) and replicated for availability. Indexes on keys or fields speed retrieval, and consistency is usually eventual.

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

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

The lock point is the moment the last lock is acquired. Transactions executed under 2PL are serializable in the order of their lock points.

Variants: basic 2PL, conservative (locks all items before starting; deadlock-free), strict (holds exclusive locks until commit/abort; avoids cascading rollbacks) and rigorous 2PL.

How it leads to deadlock

Since locks are acquired incrementally while holding others, circular waiting can occur:

Neither can reach its shrinking phase, so both wait forever. 2PL (except conservative) therefore does not prevent deadlock; it must be detected (wait-for graph) and resolved by aborting a victim, or prevented by wait-die/wound-wait.

The Extended ER (EER) model adds specialization/generalization and categories. Its constraints are:

1. Disjointness constraint on specialization - disjoint (d): an entity belongs to at most one subclass (e.g. EMPLOYEE is either SECRETARY or ENGINEER); overlapping (o): an entity can belong to several subclasses (e.g. PART can be both manufactured and purchased).
2. Completeness (participation) constraint - total: every entity of the superclass must belong to at least one subclass (double line); partial: some may belong to none (single line).

These combine into four types: disjoint-total, disjoint-partial, overlapping-total, overlapping-partial.

3. Attribute-defined (predicate-defined) vs user-defined membership - in an attribute-defined subclass membership is decided by a condition on an attribute (e.g. Job_type = 'Secretary'); in user-defined it is chosen by the user.
4. Inheritance constraint - subclasses inherit all attributes and relationships of the superclass; with multiple superclasses (a category/union type) an entity belongs to only one of the superclasses.
5. Specialization lattice/hierarchy constraints - single inheritance in a hierarchy; multiple inheritance in a lattice.

A view is a virtual table defined by a stored SQL query on one or more base tables. It stores no data of its own; the query runs whenever the view is used. Views simplify complex queries, hide columns (security), and give logical data independence.

Syntax

CREATE VIEW view_name AS
SELECT columns FROM tables [WHERE condition];

Example

CREATE VIEW CS_Students AS
SELECT Sid, Name, City
FROM Student
WHERE Program = 'BIT';

SELECT * FROM CS_Students WHERE City = 'Pokhara';
DROP VIEW CS_Students;

Users can query the view like a table. Simple views (one table, no aggregates) are updatable; views with joins, aggregates or DISTINCT generally are not.

(a) Names of persons who are doctors (join on $pid$): $\pi_{pname}\big(Person \bowtie_{Person.Pid = Doctor.pid} Doctor\big)$

(b) Doctors whose speciality is pediatric: $\sigma_{dspeciality = 'pediatric'}(Doctor)$

(a) Create tables

CREATE TABLE Student (
    SID      INT PRIMARY KEY,
    Name     VARCHAR(50) NOT NULL,
    City     VARCHAR(30),
    Program  VARCHAR(20)
);

CREATE TABLE Course (
    CID     INT PRIMARY KEY,
    CName   VARCHAR(50) NOT NULL,
    Credit  INT
);

CREATE TABLE Enrollment (
    SID  INT,
    CID  INT,
    PRIMARY KEY (SID, CID),
    FOREIGN KEY (SID) REFERENCES Student(SID),
    FOREIGN KEY (CID) REFERENCES Course(CID)
);

(b) Insert

INSERT INTO Student (SID, Name, City, Program)
VALUES (10, 'Aarav', 'Pokhara', 'BIT');

(c) Students from Kathmandu

SELECT * FROM Student WHERE City = 'Kathmandu';

(d) Students enrolled in the 'Database' course

SELECT S.SID, S.Name
FROM Student S
JOIN Enrollment E ON S.SID = E.SID
JOIN Course C ON E.CID = C.CID
WHERE C.CName = 'Database';

(e) Update city

UPDATE Student SET City = 'Kathmandu' WHERE SID = 10;

Definitions

• Entity - a real-world object that is distinguishable, e.g. a student, teacher.
• Attribute - a property describing an entity, e.g. Name, DOB.
• Relationship - an association among entities, e.g. a teacher teaches a subject.

ER design: School

Entities and attributes:

• TEACHER(<u>Teacher_ID</u>, Name, Subject)
• STUDENT(<u>Student_ID</u>, Name, DOB, /Age/, {Phone})
• SUBJECT/CLASS as required (here the relationship links TEACHER and STUDENT directly)

Relationship TEACHES between TEACHER and STUDENT: M:N, with the relationship attribute Academic_Year.

 (Teacher_ID) (Name)            (Student_ID) (Name) (DOB) :Age: ((Phone))
        \     /                       \       |      |    :     /
        [ TEACHER ] ---M--<TEACHES>--N--- [ STUDENT ]
                              |
                       (Academic_Year)

• Underlined Teacher_ID and Student_ID are key attributes (unique).
• Age (dashed oval) is derived from DOB.
• Phone (double oval) is multivalued: a student can have many numbers.
• TEACHES is many-to-many (a teacher teaches many students and a student is taught by many teachers); Academic_Year is stored on the relationship.

Mapping to tables: $TEACHER(Teacher\_ID, \dots)$, $STUDENT(Student\_ID, Name, DOB)$, $STUDENT\_PHONE(Student\_ID, Phone)$, $TEACHES(Teacher\_ID, Student\_ID, Academic\_Year)$.

Transaction: a logical unit of work made of one or more database operations that moves the database from one consistent state to another.

ACID properties

• Atomicity - all operations are done or none (all-or-nothing); handled by the recovery manager.
• Consistency - a transaction preserves database integrity constraints.
• Isolation - concurrent transactions do not see each other's intermediate results; handled by concurrency control.
• Durability - once committed, changes persist even after failures.

Transaction states: active, partially committed, committed, failed, aborted (terminated).

Serial schedules

A serial schedule executes transactions one after another, with no interleaving of operations. It is always considered correct because each transaction, run alone on a consistent database, leaves it consistent (by the consistency property); so running them one at a time in any order also leaves it consistent. There is no interference, so no lost update, dirty read or inconsistent result occurs (though different serial orders may give different results, each is correct). The drawback is poor throughput, which is why serializable schedules are used.

DBMS: a software system that lets users define, create, maintain and control access to a database, e.g. MySQL, Oracle.

Advantages over file-based systems

1. Reduced data redundancy and inconsistency.
2. Data sharing by many users concurrently.
3. Data independence between programs and storage.
4. Integrity constraints and security (access control).
5. Backup and recovery, and efficient querying with SQL.

Real-life example: a bank's system storing customers, accounts and transactions in one database accessed by ATMs, branches and online banking.

Weak entity type: an entity type that does not have a key attribute of its own; it is identified only through its relationship with an owner (identifying) entity, and has total participation in that identifying relationship.

Example: EMPLOYEE and DEPENDENT. A dependent is identified by the owner employee's SSN together with the dependent's name (the partial key).

 [SSN]--[Name]
     \  /
   [ EMPLOYEE ] ===<< HAS >>=== [[ DEPENDENT ]]--(Dep_name)  (Relation)
    (owner)    (identifying)       (weak entity)    (partial key,
                relationship                         dashed underline)

• Weak entity: double rectangle DEPENDENT.
• Owner (strong) entity: EMPLOYEE.
• Identifying relationship: double diamond HAS, with a double line (total participation) from DEPENDENT.
• Partial key: Dep_name, drawn with a dashed underline; the full key is $(SSN, Dep\_name)$.

Domain constraint: the value of every attribute must be an atomic value from the attribute's domain (data type, range, format). Example: $Age$ must be an integer between 0 and 120; a NOT NULL or CHECK clause can enforce it.

Referential integrity constraint: a foreign key value in a tuple of the referencing relation must either match an existing primary key value in the referenced relation or be NULL. Example: $Employee.Dno$ must exist in $Department.Dnumber$.

When a DELETE violates referential integrity (deleting a parent tuple still referenced by child tuples), the DBMS can:

1. Restrict / reject the delete (default).
2. Cascade - delete the referencing tuples too (ON DELETE CASCADE).
3. Set NULL - set the foreign key in referencing tuples to NULL (ON DELETE SET NULL).
4. Set default - set it to a default value.

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

• Growing phase: locks are acquired; none released.
• Shrinking phase: locks are released; none acquired.

Once a transaction releases its first lock it cannot lock again. This guarantees conflict-serializable schedules. (Strict 2PL holds exclusive locks until commit.)

Deadlock detection

1. Wait-for graph: nodes are transactions; add edge $T_i \to T_j$ when $T_i$ waits for a lock held by $T_j$. The graph is checked periodically; a cycle means deadlock.
2. A victim transaction in the cycle is chosen (e.g. the youngest or least work done) and aborted/rolled back to break the cycle.
3. A simpler method is a timeout: a transaction waiting longer than a limit is assumed deadlocked and aborted.

Functional dependency (FD): a constraint between two sets of attributes $X$ and $Y$ of a relation, written $X \to Y$, meaning that if two tuples have the same value of $X$ they must have the same value of $Y$ ($X$ determines $Y$). Example: $Roll\_no \to Name$.

First Normal Form (1NF): a relation is in 1NF if all attribute values are atomic (single, indivisible), with no multivalued attributes or repeating groups.

Example

Not in 1NF:

In 1NF:

Concurrency control is the set of techniques a DBMS uses to manage the simultaneous execution of transactions so that they do not interfere and the database stays consistent (isolation, serializability).

Why needed: uncontrolled interleaving causes the lost update, dirty read, unrepeatable read and incorrect summary problems, leading to inconsistent data.

Shared vs exclusive locks

(a) NoSQL databases

NoSQL ("not only SQL") databases are non-relational systems for large-scale, distributed data that is structured, semi-structured or unstructured.

• Schema-less and flexible; horizontally scalable by sharding; data replicated for availability.
• High read/write performance; follows BASE (eventual consistency) and the CAP theorem.
• Types: key-value (Redis), document (MongoDB), column-family (Cassandra), graph (Neo4j).
• Used in big data, social networks, real-time web applications.

(b) Database users

1. Database administrators (DBA) - manage the DBMS, schema, security, backup and performance.
2. Database designers - decide data to store and design structures and constraints.
3. End users - casual users (occasional queries), naive/parametric users (use ready forms, e.g. bank tellers), sophisticated users (analysts using query languages) and standalone users.
4. System analysts and application programmers - determine end-user requirements and write programs/applications.
5. DBMS designers and implementers, tool developers and operators/maintenance staff.