Database Management System

The desirable properties of a transaction are the ACID properties:

• Atomicity: a transaction is all-or-nothing; if any part fails, the whole transaction is rolled back. It is the responsibility of the recovery subsystem.
• Consistency: a transaction takes the database from one consistent state to another, preserving all integrity constraints. For example, in a transfer the total of both accounts is unchanged.
• Isolation: concurrent transactions do not interfere; each behaves as if it ran alone. It is enforced by concurrency control.
• Durability: once committed, changes are permanent and survive system failures, which is ensured by logging and recovery.

Big data refers to extremely large and complex data sets, arriving at high speed and in many forms, that cannot be stored or processed efficiently by traditional database tools. It is characterised by volume, velocity and variety (the 3 Vs).

A serializable schedule is a concurrent schedule of transactions whose effect is equivalent to some serial schedule (one transaction at a time) of the same transactions, so it leaves the database consistent.

Concurrency control

Concurrency control is the set of mechanisms that manage the simultaneous execution of transactions so that they do not interfere with each other. It preserves isolation and the consistency of the database, and prevents problems such as lost update, dirty read and unrepeatable read.

Two-phase locking (2PL) protocol

A transaction must acquire locks on a data item before using it. Two kinds of lock are used: a shared lock (read) and an exclusive lock (write). In 2PL every transaction issues its lock and unlock requests in two phases.

1. Growing phase: the transaction may obtain locks but cannot release any.
2. Shrinking phase: the transaction may release locks but cannot obtain new ones.

The point at which the transaction obtains its last lock is the lock point. Example for transaction $T$:

lock-X(A); read(A); A = A - 50; write(A);
lock-X(B);          -- still growing
read(B); B = B + 50; write(B);
unlock(A); unlock(B);  -- shrinking

Properties

• 2PL guarantees conflict-serializable schedules.
• It does not prevent deadlock, and it can lead to cascading rollback.
• Strict 2PL holds all exclusive locks until commit or abort, which avoids cascading rollback. Rigorous 2PL holds all locks until commit.

Concurrency control is the set of mechanisms a DBMS uses to manage simultaneous execution of transactions so that they do not interfere with each other. It preserves isolation and consistency and prevents problems such as lost update, dirty read and unrepeatable read.

Two-phase locking (2PL) protocol

A transaction must obtain a lock on a data item before accessing it. Locks are of two kinds: a shared (read) lock and an exclusive (write) lock. 2PL requires every transaction to acquire and release locks in two distinct phases:

1. Growing phase: the transaction may obtain locks but may not release any.
2. Shrinking phase: once the transaction releases its first lock, it may release locks but may not obtain any new ones.

The point where the transaction holds all its locks (the lock point) fixes its serialization order. Because of this rule, any schedule produced by 2PL is conflict serializable.

Example: T1 does Lock-X(A), Lock-X(B), read/write A and B, then Unlock(A), Unlock(B). All locks come before all unlocks, so it follows 2PL.

Limitations and variants

• It does not prevent deadlock, since two transactions may wait for each other's locks.
• It can cause cascading rollback. Strict 2PL (hold exclusive locks until commit or abort) avoids this, and rigorous 2PL holds all locks until commit.

A data model is a collection of concepts and tools for describing the structure of a database: its data, relationships, semantics and constraints. Examples are the relational, entity-relationship and object-oriented models.

DROP TABLE student;

DROP TABLE removes the table's structure and data permanently. (DELETE FROM student; only removes the rows.)

A simple attribute cannot be divided into smaller parts (e.g. age, roll_no). A composite attribute can be divided into sub-parts with independent meaning (e.g. name into first_name, middle_name, last_name; address into street, city, district).

The mapping constraints (cardinality ratios) in the ER model are:

• One-to-one (1:1)
• One-to-many (1:N)
• Many-to-one (N:1)
• Many-to-many (M:N)

CREATE TABLE table_name (
    column_name data_type,
    CONSTRAINT constraint_name CHECK (condition)
);

Example: age INT CHECK (age >= 18).

A transaction is a logical unit of work consisting of one or more database operations (reads and writes) that must be executed as a whole, taking the database from one consistent state to another. It either completes fully (commit) or has no effect (rollback).

NoSQL ("not only SQL") refers to non-relational databases that store data in flexible formats such as key-value, document, column-family or graph, without a fixed schema. They scale horizontally and are suited to large, unstructured or rapidly changing data (e.g. MongoDB, Cassandra, Redis).

A relation is in First Normal Form (1NF) if every attribute contains only atomic (indivisible) values, with no multivalued attributes or repeating groups, and each row is uniquely identifiable.

Levels of abstraction (physical, logical, view) hide the complexity of how data is stored from users. They provide data independence, so the storage structure can change without affecting the application programs, simplify the user's interaction, and allow different users to see different views of the same data with better security.

Two-phase locking (2PL) is a concurrency control protocol that guarantees serializability. Every transaction executes in two phases:

• Growing phase: the transaction may acquire locks (shared or exclusive) but cannot release any.
• Shrinking phase: once it releases its first lock, it may only release locks and cannot acquire new ones.

Because no transaction acquires a lock after releasing one, the schedules produced are conflict-serializable. Basic 2PL can suffer deadlock; strict 2PL holds all exclusive locks until commit, which also avoids cascading rollbacks.

Types of database users:

• Naive (end) users: use the database through ready-made application interfaces, such as a bank clerk or ticket booking user.
• Application programmers: write application programs in a host language that access the database through SQL/APIs.
• Sophisticated users: analysts and engineers who write queries directly in a query language without programs.
• Specialized users: write specialized applications (CAD systems, expert systems, multimedia) that do not fit traditional processing.
• Database administrator (DBA): controls the whole database system, including schema, security, backup and recovery.

Importance: recovery restores the database to the last consistent state after a failure (system crash, disk failure, transaction failure, power loss). It preserves atomicity and durability and prevents data loss.

Methods:

• Log-based recovery: a log records every update. Deferred update applies changes to the database only after commit (redo only); immediate update writes changes before commit (needs undo and redo).
• Shadow paging: keeps a current and a shadow page table; on failure the shadow table is used, so no log is needed.
• Checkpoints: periodic saving points so recovery only examines the log after the last checkpoint.
• Backup and restore: restoring from a full backup, then replaying the log, for media failure.

A view is a virtual table defined by a stored query on one or more base tables; it holds no data of its own.

Importance: it hides sensitive columns and rows (security), simplifies complex queries, gives each user a customised view of the data, and provides logical data independence.

Syntax:

CREATE VIEW view_name AS
SELECT column1, column2
FROM table_name
WHERE condition;

Example: CREATE VIEW cs_students AS SELECT id, name FROM student WHERE dept = 'CS';

Database security is the protection of the database against unauthorised access, misuse, modification or destruction, ensuring confidentiality, integrity and availability.

It is secured by:

• Authentication: user names, passwords and biometrics.
• Authorization and access control: GRANT/REVOKE privileges and roles.
• Views: exposing only permitted data.
• Encryption: of stored and transmitted data.
• Backup and recovery, and audit trails or logging of activity.
• Firewalls and physical security, plus protection against SQL injection.

Normalization is the process of organising relations to remove redundancy and undesirable dependencies.

Importance: it reduces data redundancy, avoids insertion, update and deletion anomalies, saves storage and keeps data consistent.

Example: table Student(roll, name, course, course_fee) repeats the fee for every student taking a course. Changing a fee means updating many rows (update anomaly), and a new course cannot be stored without a student (insertion anomaly). Normalizing splits it into Student(roll, name, course) and Course(course, course_fee), so each fact is stored once.

Database languages are used to define, manipulate and control a database.

• DDL (Data Definition Language): defines the schema. Commands: CREATE, ALTER, DROP, TRUNCATE, RENAME. Example: CREATE TABLE student(id INT PRIMARY KEY, name VARCHAR(30));
• DML (Data Manipulation Language): retrieves and modifies data. Commands: SELECT, INSERT, UPDATE, DELETE. Example: INSERT INTO student VALUES(1,'Ram');
• DCL (Data Control Language): controls access and privileges. Commands: GRANT, REVOKE. Example: GRANT SELECT ON student TO user1;
• TCL (Transaction Control Language): manages transactions. Commands: COMMIT, ROLLBACK, SAVEPOINT. Example: ROLLBACK;
• DQL (Data Query Language): sometimes separated out to mean SELECT queries. Example: SELECT name FROM student WHERE id = 1;

Aggregate functions operate on a set of rows and return a single value:

• COUNT(): number of rows. SELECT COUNT(*) FROM student;
• SUM(): total of a numeric column. SELECT SUM(salary) FROM employee;
• AVG(): average value. SELECT AVG(marks) FROM student;
• MAX(): largest value. SELECT MAX(salary) FROM employee;
• MIN(): smallest value. SELECT MIN(salary) FROM employee;

General syntax: SELECT function(column) FROM table [WHERE condition] [GROUP BY column];. Except COUNT(*), they ignore NULL values.

Specialization is a top-down process: an entity set is divided into sub-groups (lower-level entity sets) that have additional distinct attributes or relationships. Generalization is a bottom-up process: several entity sets that share common attributes are combined into a higher-level entity set. Both are shown with an ISA triangle, and lower-level entities inherit the attributes of the higher-level one.

When used: when entities of one type have subgroups with their own special attributes or relationships, or when several entity sets share common features that should be stored once.

Example: Person(id, name, address) is specialized into Student(roll, program) and Teacher(salary, department). Conversely, if Student and Teacher are defined separately with common attributes id, name, address, these are generalized into Person.

Entities and attributes

• Employee (<u>emp_id</u>, name, address, phone)
• Project (<u>proj_id</u>, title, start_date, budget)
• Project_Manager (<u>pm_id</u>, name, phone)
• Client (<u>client_id</u>, name, address, phone)
• Feedback (<u>fb_id</u>, date, comments, rating)

Relationships and cardinalities

• Works_on between Employee and Project: many-to-many (an employee can work on many projects and a project has many employees).
• Managed_by between Project and Project_Manager: many-to-many (a project may be under one or more managers, and a manager can handle many projects).
• Pays between Client and Project (attribute: amount, date): one client pays for many projects, each project is paid by one client (1:N).
• Gives between Client and Feedback, and Feedback_for between Feedback and Project (a client gives feedback for a project; feedback may be modelled as a ternary relationship Client-Project-Feedback).

ER diagram (text form)

[Employee] --M--<Works_on>--N-- [Project] --N--<Managed_by>--M-- [Project_Manager]
                                   |  \
                                   N   \--- N --<Feedback_for>-- 1 [Feedback] --N--<Gives>--1-- [Client]
                                   |                                                              |
                                   +------------ N --<Pays (amount)>-- 1 --------------------------+

Rectangles are entities, diamonds are relationships and ovals are attributes (underlined for primary keys). The same structure is drawn with each entity connected to its attribute ovals and to the relationship diamonds above with the cardinalities M, N and 1.

i) Insert a tuple (the branch is not supplied, so the columns are named):

INSERT INTO Account(ac_no, type, balance) VALUES (1001, 'checking', 30000);

ii) Delete accounts that have no customer:

DELETE FROM Account
WHERE ac_no NOT IN (SELECT ac_no FROM Depositer);

iii) Change Ram's phone number:

UPDATE Customer
SET phone_no = '11111111'
WHERE name = 'Ram';

iv) Names of customers who own an account with balance greater than 2000:

SELECT DISTINCT c.name
FROM Customer c, Depositer d, Account a
WHERE c.cid = d.cid AND d.ac_no = a.ac_no AND a.balance > 2000;

v) Customers whose name starts with R and ends with A:

SELECT * FROM Customer
WHERE name LIKE 'R%A';

A database language is a language used to define the structure of a database, manipulate its data and control access to it. Examples are DDL, DML, DCL and TCL, all part of SQL.

UPDATE table_name
SET column1 = value1, column2 = value2
WHERE condition;

Example: UPDATE student SET name = 'Hari' WHERE id = 1;

A unary (recursive) relationship is a relationship in which an entity set is related to itself, so the same entity set participates twice in different roles. Example: an Employee supervises other Employees (manager and subordinate).

Four types of attributes in the ER model:

• Simple (atomic) attribute
• Composite attribute
• Single-valued attribute
• Multivalued attribute

(Others: derived, key and null attributes.)

Big data refers to extremely large, fast-growing and varied data sets (structured, semi-structured and unstructured) that are too complex for traditional data-processing tools. It is described by volume, velocity and variety.

In deferred data update (deferred modification), a transaction's updates are written only to the log until the transaction commits; the database itself is changed after the commit. Hence no undo is needed on failure, only redo.

Views are important because they provide security by hiding sensitive columns or rows, simplify complex queries, give users customised presentations of data, and provide logical data independence.

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

A role is a named collection of privileges that can be granted to users or to other roles. It simplifies authorization because the privileges are managed in one place. Example: CREATE ROLE manager; GRANT SELECT, UPDATE ON employee TO manager;

Shadow paging is a recovery technique that does not use a log. The database is divided into fixed-size pages, and a page table maps each page to a disk block.

• At the start of a transaction the current page table is copied to a shadow page table, which is saved on disk and never modified.
• Updates are written to new blocks and only the current page table is changed to point to them.
• On commit, the current page table becomes the new shadow table (the pointer is switched atomically).
• On failure, the current table is discarded and the shadow table restores the old state, so rollback is immediate.

It avoids undo/redo, but it causes data fragmentation and needs garbage collection of old pages.

The Database Administrator (DBA) is the person (or team) with central control over the database system and its users.

Roles of the DBA:

• Defining the schema and the storage structure and access methods
• Granting authorization and ensuring security
• Backup and recovery planning
• Monitoring performance and tuning
• Maintaining integrity constraints and data consistency
• Schema and physical organisation modification
• Liaising with users and application programmers

Timestamp ordering is a concurrency control method that orders transactions by timestamps instead of locks. Each transaction $T$ gets a unique timestamp $TS(T)$ when it starts, and each data item $Q$ keeps a read timestamp $R\text{-}TS(Q)$ and a write timestamp $W\text{-}TS(Q)$.

• Read(Q) by $T$: if $TS(T) < W\text{-}TS(Q)$, $T$ would read an overwritten value, so it is rolled back and restarted; otherwise the read is allowed and $R\text{-}TS(Q)=\max(R\text{-}TS(Q),TS(T))$.
• Write(Q) by $T$: if $TS(T) < R\text{-}TS(Q)$ or $TS(T) < W\text{-}TS(Q)$, $T$ is rolled back; otherwise the write is performed and $W\text{-}TS(Q)=TS(T)$.

The schedules are conflict-serializable (equivalent to timestamp order) and deadlock-free, but starvation of restarted transactions is possible.

In relational mapping, a composite attribute is reduced by keeping only its simple component attributes as separate columns; the composite attribute itself does not become a column.

Example: Student(roll, name, address) where address is composite of street, city, district. The relation schema is:

$\text{Student}(\underline{roll},\ name,\ street,\ city,\ district)$

The components street, city and district become ordinary attributes, and the parent address is not stored.

Constraints on generalization and specialization decide which entities may belong to which lower-level entity sets.

1. Membership (condition-defined vs user-defined)

• Condition-defined: an entity joins a lower-level set if it satisfies a condition on an attribute (e.g. every account with type = "Saving" goes to Saving_Account).
• User-defined: the database user assigns entities to the lower-level set manually.

2. Disjointness

• Disjoint: an entity can belong to at most one lower-level set (a person is either Student or Teacher).
• Overlapping: an entity can belong to more than one lower-level set (a person can be both Student and Employee).

3. Completeness

• Total: every higher-level entity must belong to at least one lower-level set.
• Partial: some higher-level entities may belong to none of the lower-level sets.

Database security protects data from unauthorised access, misuse, modification and loss. Its importance is:

• Confidentiality: sensitive data such as bank records, personal details and passwords is seen only by authorised users.
• Integrity: it prevents unauthorised or accidental changes, so data stays accurate and consistent.
• Availability: authorised users can access data when needed, even against attacks such as denial of service.
• Legal and business protection: it helps meet data-protection laws, maintains customer trust and avoids financial loss and reputational damage.
• Accountability: authentication, authorisation and audit trails identify who did what.

Database users are classified by the way they interact with the system.

1. Naive (end) users: unsophisticated users who use ready-made application programs and forms, e.g. a bank teller or a ticket-booking clerk. They need no knowledge of the DBMS.
2. Application programmers: computer professionals who write application programs in languages such as Java, PHP or C# with embedded SQL to give the end users their interfaces.
3. Sophisticated users: analysts and engineers who write their own queries in a query language such as SQL to explore data, without writing application programs.
4. Database administrator (DBA): the person with central control of the DBMS. The DBA defines the schema, grants access rights, manages storage, takes backups, and handles recovery and performance tuning.

(Specialised users, who build special applications such as CAD or expert systems, are a further type.)

How normalization helps good design

Normalization organises tables by decomposing them using functional dependencies. It helps by:

• reducing data redundancy and saving storage;
• removing insertion, deletion and update anomalies;
• keeping data consistent, because each fact is stored once;
• making the schema clearer and easier to maintain.

Second Normal Form (2NF)

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

Example: Enrollment(StudentID, CourseID, StudentName, Grade) with key (StudentID, CourseID).

• Here StudentID → StudentName is a partial dependency, because StudentName depends on only part of the key. So the relation is not in 2NF.
• It causes redundancy: the name is repeated for every course, and updating it risks inconsistency.

Decomposition into 2NF:

• Student(StudentID, StudentName)
• Enrollment(StudentID, CourseID, Grade)

Now every non-key attribute depends on the whole of its table's key.

Constraints are rules that keep the data in a database valid.

1. NOT NULL: a column cannot hold NULL. Name VARCHAR(50) NOT NULL
2. UNIQUE: all values in a column (or set of columns) are different, but NULL is allowed. Email VARCHAR(50) UNIQUE
3. PRIMARY KEY: uniquely identifies each row. It combines NOT NULL and UNIQUE, and a table has only one. StudentID INT PRIMARY KEY
4. FOREIGN KEY: a column that refers to the primary key of another table, which keeps referential integrity. FOREIGN KEY (DeptID) REFERENCES Department(DeptID)
5. CHECK: restricts values by a condition. Age INT CHECK (Age >= 18)
6. DEFAULT: gives a default value when none is supplied. Country VARCHAR(20) DEFAULT 'Nepal'

Example putting them together:

CREATE TABLE Student (
  StudentID INT PRIMARY KEY,
  Name VARCHAR(50) NOT NULL,
  Email VARCHAR(50) UNIQUE,
  Age INT CHECK (Age >= 18),
  DeptID INT,
  FOREIGN KEY (DeptID) REFERENCES Department(DeptID)
);

Entity sets (with attributes)

• Person (person_id, name, address, phone, dob), a superclass.
• Doctor (doctor_id, specialization, salary), a subclass of Person.
• Patient (patient_id, disease, admit_date), a subclass of Person.
• Department (dept_id, dept_name, location)
• Room (room_no, type, charge)
• Appointment (appt_id, date, time) as an entity or relationship.
• Treatment/Bill (bill_id, amount, date), a weak-style entity dependent on Patient.

Relationships and mapping cardinality

• Doctor works_in Department: many-to-one (many doctors, one department).
• Department has Room: one-to-many.
• Patient admitted_in Room: many-to-one (many patients per room, with a capacity limit).
• Patient consults Doctor (attribute: date, fee): many-to-many.
• Patient receives Bill: one-to-many; Bill is a weak entity, identified by patient_id plus bill_no, with total participation.
• Doctor heads Department: one-to-one.

Extended ER features

• Specialization/generalization: Person is specialized into Doctor and Patient (disjoint, partial). Attributes of Person are inherited by both.
• Aggregation: the relationship consults is aggregated and linked to Bill, so that a bill belongs to a particular consultation.
• Total participation (double line): each Bill must belong to a Patient; each Doctor must work in a Department.

Diagram (text form)

          Person (ISA, disjoint)
          /              \
     Doctor            Patient
       |  \              |   \
 works_in  heads      consults  admitted_in
       |     |           |          |
   Department------has---Room     (Room)
                    [Consults] --aggregation-- generates --> Bill (weak)

Rectangles are entity sets, diamonds are relationships, ellipses are attributes (key attributes underlined), the ISA triangle shows specialization, and a double rectangle shows the weak entity.

i)

INSERT INTO Person(pid, name, address) VALUES (1, 'Ram Bdr', 'kathmandu');

(The phone is left NULL.)

ii)

SELECT model FROM Car WHERE price = (SELECT MAX(price) FROM Car);

iii)

UPDATE Car SET price = price * 1.15;

iv)

SELECT p.name
FROM Person p
JOIN owns_by o ON p.pid = o.pid
JOIN Car c ON c.reg_no = o.reg_no
WHERE c.color = 'red';

v) Models with at most 4 characters:

SELECT * FROM Car WHERE LENGTH(model) <= 4;

(In SQL Server use LEN(model).)

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. It is of two types: physical (changing storage does not affect the logical schema) and logical (changing the logical schema does not affect application programs).

Specialization is a top-down process of designing in which a higher-level entity set is divided into lower-level entity sets that have distinct characteristics. For example, Person is specialized into Student and Teacher.

Keys are used to identify each tuple (row) in a table uniquely, to establish links between tables (foreign keys), to enforce integrity constraints, and to speed up searching and retrieval of data.

DDL (Data Definition Language) is the set of SQL commands used to define and change the structure of database objects. Its commands are CREATE, ALTER, DROP, TRUNCATE and RENAME.

A functional dependency $X \rightarrow Y$ is a constraint between two sets of attributes of a relation. It says that if two tuples have the same value for $X$, they must have the same value for $Y$, i.e. $X$ determines $Y$. For example, $StudentID \rightarrow StudentName$.

Deferred update is a recovery technique in which a transaction's updates are not written to the database until the transaction reaches its commit point. The changes are first recorded only in the log. Therefore no UNDO is needed after a failure, only REDO for committed transactions.

Shadow paging is a recovery technique that does not use a log. The database is divided into pages, and two page tables are kept: the current page table and the shadow page table. Updates are made on new copies of pages and recorded in the current table, while the shadow table keeps pointing to the old pages. On commit, the current table becomes the shadow table. On failure, the shadow table is used to restore the old consistent state.

Specialization is a top-down process of defining sub-classes (lower-level entity sets) from a higher-level entity set; generalization is the bottom-up process of combining entity sets with common features into a higher-level entity set.

Constraints

• Disjoint vs overlapping: in a disjoint design an entity belongs to at most one lower-level set (e.g. a person is either Student or Teacher); in an overlapping design it may belong to more than one.
• Total vs partial completeness: total means every higher-level entity must belong to some lower-level set; partial means some need not.

Characteristics

• Lower-level entity sets inherit the attributes and relationships of the higher-level set (attribute inheritance).
• They may add their own attributes and take part in their own relationships.
• Shown in an E-R diagram by an ISA triangle.

A relationship set is a set of associations among entities. By the number of entities that participate (degree) it is:

• Unary (recursive): relates entities of the same set, e.g. an Employee supervises another Employee.
• Binary: relates two entity sets, e.g. Student enrolls in Course. This is the most common type.
• Ternary (n-ary): relates three or more entity sets, e.g. Supplier supplies Part to Project.

By mapping cardinality, a binary relationship is one-to-one, one-to-many, many-to-one or many-to-many.

SQL data types define the kind of value a column can hold.

1. INT: stores whole numbers. Example: Age INT.
2. VARCHAR(n): stores variable-length character strings of up to n characters. Example: SName VARCHAR(50) holds "Ram".
3. DATE: stores calendar dates in the form YYYY-MM-DD. Example: DOB DATE holds '2004-05-12'.

Example: CREATE TABLE student(SID INT, SName VARCHAR(50), DOB DATE);

Decomposition replaces a relation $R$ by smaller relations $R_1, R_2,\dots,R_n$ to remove redundancy. A good decomposition must have the following properties.

1. Lossless-join (non-additive join) property: joining the decomposed relations must give back exactly the original relation, with no spurious tuples. For a decomposition into $R_1$ and $R_2$ it holds if $R_1\cap R_2 \to R_1$ or $R_1\cap R_2 \to R_2$.
2. Dependency preservation: every functional dependency of $R$ can be enforced by checking the dependencies within the individual decomposed relations, without joining them.
3. Attribute preservation: every attribute of $R$ appears in at least one decomposed relation.

Lossless join is essential. Dependency preservation is desirable and is not always attainable for BCNF.

Catastrophic failure is a loss of the disk or a physical disaster that destroys the database itself. Log-based recovery alone cannot repair it, so recovery depends on backups.

1. Periodic backup: the whole database and the log are regularly copied to tape, a remote disk or another stable storage.
2. Restore: after the failure the most recent backup copy is loaded onto a new disk.
3. Redo from the log: the log kept since the backup (stored on separate, safe media) is used to redo all committed transactions up to the time of failure. Transactions that did not commit are ignored or undone.

This brings the database back to the last consistent state. Keeping the log on a different disk from the data is therefore important.

In immediate update, a transaction's changes are written to the database on disk before it commits, while the transaction is still active. Because uncommitted values may reach the database, the log must record both the old value (before image) and the new value (after image), and the log record is written first (write-ahead logging).

Recovery after a crash

• Undo: a transaction that has a <T, start> record but no <T, commit> is undone. Its updated items are restored to their old values from the log.
• Redo: a transaction with both <T, start> and <T, commit> is redone, because some of its changes may not have reached the disk.

This is the UNDO/REDO algorithm. Its advantage is that it does not force the transaction to wait until commit to write.

The three-schema architecture separates the user's view of the data from its physical storage. It has three levels.

1. External level (view level): describes the part of the database a particular user group sees. There are many external schemas (views), and each hides the rest of the data. Example: a student sees only the marks of their own results.
2. Conceptual level (logical level): describes the whole database for the whole organization: entities, attributes, relationships, constraints and security. There is one conceptual schema, and it hides physical storage details.
3. Internal level (physical level): describes how the data is physically stored: file structures, indexes, access paths and record placement.

External view 1   External view 2   External view 3
        \               |               /
         ---- External/Conceptual mapping ----
                 Conceptual schema
         ---- Conceptual/Internal mapping ----
                  Internal schema
                        |
                   Stored database

Mappings convert requests and results between the levels.

Data independence

• Logical data independence: the conceptual schema can change without changing the external schemas.
• Physical data independence: the internal schema can change without changing the conceptual schema.

The architecture therefore gives multiple user views, simpler maintenance and data independence.

Entities and attributes (primary keys marked *)

• Customer: *Cust_ID, Name, Phone, Address
• Restaurant: *Rest_ID, Name, Location, Rating
• Menu_Item: *Item_ID, Name, Price, Category
• Order: *Order_ID, Order_Date, Total_Amount, Status
• Delivery_Person: *Del_ID, Name, Phone, Vehicle_No
• Payment (weak or separate entity): *Pay_ID, Mode, Amount, Pay_Date

Relationships

• Customer places Order: one-to-many (1 : N)
• Restaurant receives Order: one-to-many (1 : N)
• Restaurant offers Menu_Item: one-to-many (1 : N)
• Order contains Menu_Item: many-to-many (M : N), with the attribute Quantity
• Delivery_Person delivers Order: one-to-many (1 : N)
• Order has Payment: one-to-one (1 : 1)

E-R diagram (text form)

[Customer]--1--<places>--N--[Order]--N--<receives>--1--[Restaurant]
                              |  \                          |
                              1   N--<contains(qty)>--M--[Menu_Item]--N--<offers>--1--+
                              |
                         <has> 1--[Payment]
                         N--<delivers>--1--[Delivery_Person]

Entities are drawn as rectangles, attributes as ovals joined to them, relationships as diamonds, and the primary key attributes are underlined.

Data warehouse

A data warehouse is a large, centralized repository of integrated data collected from many operational sources. It is subject-oriented, integrated, time-variant (it keeps history) and non-volatile (data is not changed once loaded). It supports analysis and decision making rather than day-to-day transactions.

Data mining

Data mining is the process of discovering useful, previously unknown patterns, trends and relationships in large volumes of data, using techniques such as classification, clustering, association rule mining and prediction. It is a step in knowledge discovery in databases (KDD).

Main steps: data cleaning and integration, selection, transformation, pattern discovery, and evaluation and presentation of the result.

Examples

• Association rules (market basket analysis): a supermarket finds that customers who buy bread and butter often also buy milk, and then places these items close together.
• Classification: a bank uses past customer data to classify loan applicants as low or high risk.
• Clustering: a telecom company groups customers with similar calling behaviour to design offers.

Need for normalization

Normalization is the process of organizing relations to reduce redundancy and avoid anomalies. It is needed because a poorly designed relation suffers from:

• Redundancy: the same data is stored repeatedly, wasting space.
• Insertion anomaly: some data cannot be inserted without other unrelated data.
• Deletion anomaly: deleting one fact unintentionally removes other facts.
• Update anomaly: a change must be made in many rows, or the data becomes inconsistent.

Normalization also makes the design more flexible and keeps data consistent.

First Normal Form (1NF)

A relation is in 1NF if all attributes are atomic (single-valued) and there are no repeating groups or multivalued attributes.

Not in 1NF: Student(SID, Name, Phone) with SID 1, Ram, {9841, 9851}.

In 1NF: each phone number is placed in a separate row.

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(SID, CID, SName, Grade) with key (SID, CID). Here $SID \to SName$ is a partial dependency, so the relation is not in 2NF.

Decompose:

• Student(SID, SName)
• Enroll(SID, CID, Grade)

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

Third Normal Form (3NF)

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

Example: Employee(EID, EName, DeptID, DeptName) with $EID \to DeptID$ and $DeptID \to DeptName$. Then $EID \to DeptName$ is transitive, so the relation is not in 3NF.

Decompose:

• Employee(EID, EName, DeptID)
• Department(DeptID, DeptName)

Redundancy of DeptName is now removed, and each fact is stored once.

(a)

INSERT INTO student (SID, SName, SAddress, SEmail)
VALUES ('S101', 'Ram', 'Lalitpur', '[email protected]');

(b)

SELECT SName
FROM student
WHERE SAddress = 'Kathmandu';

(c)

SELECT s.SName
FROM student s
JOIN studies st ON s.SID = st.SID
JOIN course c ON st.CID = c.CID
WHERE c.CName = 'Database Management System';

(d)

SELECT COUNT(*)
FROM studies st
JOIN course c ON st.CID = c.CID
WHERE c.CName = 'Database Management System';

(e)

SELECT CName
FROM course
WHERE Credit_hours >= 3;

A schema is the overall design (structure) of the database and changes rarely, whereas an instance is the actual data stored in the database at a particular moment and changes frequently.

Attribute inheritance is the property by which a lower-level entity set (sub-class) automatically acquires all the attributes, and relationships, of the higher-level entity set (super-class) it is derived from through specialization or generalization.

Two SQL data types are INT (whole numbers) and VARCHAR(n) (variable-length character strings).

A role is a named group of privileges. Creating roles lets the DBA grant or revoke a set of privileges to many users at once by assigning the role. This simplifies authorization management and improves security.

A transitive dependency exists when a non-key attribute depends on another non-key attribute, that is, if $A \to B$ and $B \to C$ hold (with $B \not\to A$), then $C$ depends on $A$ transitively through $B$.

ALTER TABLE Employee DROP COLUMN email;

Concurrent transactions are two or more transactions that execute at the same time on the same database, with their operations interleaved. They need concurrency control so that they do not interfere with each other.

A distributed database is a collection of logically related data that is stored at several computers (sites) connected by a network, and appears to the user as a single database.

Privileges are the rights granted to a user or role to perform particular operations on database objects, such as SELECT, INSERT, UPDATE, DELETE, or creating tables. They are given with GRANT and withdrawn with REVOKE.

A catastrophic failure is a serious failure, such as a disk crash, fire or theft, that destroys the stored database itself. It can be recovered from only by using a backup copy together with the log.

Constraints are rules that restrict the data that may be stored, and so keep it valid and consistent.

1. Primary key constraint: uniquely identifies each row; its value must be unique and not NULL. Example: SID INT PRIMARY KEY.
2. Foreign key (referential integrity) constraint: a value in one table must match an existing primary key value in the referenced table. Example: FOREIGN KEY (CID) REFERENCES course(CID).
3. NOT NULL / UNIQUE / CHECK constraints: NOT NULL forbids empty values, UNIQUE forbids duplicates, and CHECK limits values to a condition. Example: Credit_hours INT CHECK (Credit_hours > 0).

The three-schema architecture divides a database into three levels so that users are kept separate from the physical storage.

External level:    View 1 | View 2 | View 3
                         |
Conceptual level:   Conceptual schema
                         |
Internal level:     Internal schema -> Stored database

• External level: the views of individual users or applications, each showing only the relevant data.
• Conceptual level: the logical structure of the entire database (entities, relationships, constraints).
• Internal level: the physical storage structure, files and indexes.

Mappings between the levels give logical and physical data independence.

Three methods of making a database secure:

1. Authentication and access control: users must prove their identity with a username and password (or other credentials), and they are given only the privileges they need (using GRANT and REVOKE, and roles).
2. Encryption: sensitive data is stored and transmitted in encrypted form, so it is unreadable if intercepted or stolen.
3. Backup and auditing: regular backups allow recovery from loss or damage, and audit trails record who accessed or changed data, so misuse can be detected. Views can also be used to hide sensitive columns.

A relationship set is a set of relationships of the same type among entity sets. Relationships are classified by degree and by cardinality.

By degree (number of participating entity sets)

• Unary (recursive): one entity set relates to itself, e.g. Employee supervises Employee.
• Binary: two entity sets, e.g. Student enrolls in Course. This is the most common type.
• Ternary: three entity sets, e.g. Instructor, Subject and Semester in Taught.

By mapping cardinality (binary)

• One-to-one (1:1): an entity in A relates to at most one in B and vice versa, e.g. Person and Passport.
• One-to-many (1:N): an entity in A relates to many in B, but each B relates to at most one A, e.g. Department and Employee.
• Many-to-one (N:1): the reverse of one-to-many.
• Many-to-many (M:N): entities on both sides may relate to many on the other, e.g. Student and Course.

Specialization is a top-down design process in the Extended ER model. A higher-level entity set is divided into lower-level sub-groups (subclasses) that are distinguished by some characteristic. Each subclass inherits all attributes and relationships of the superclass and may add attributes or relationships of its own. The link between them is an ISA ("is a") relationship.

Constraints

• Disjoint vs overlapping: an entity may belong to only one subclass, or to more than one.
• Total vs partial: every superclass entity must belong to some subclass, or not.

Example (a college): the entity set Person (PersonID, Name, Address, Phone) is specialized into:

• Student (adds Program, Semester, GPA)
• Teacher (adds Department, Salary, Qualification)
• Staff (adds Post, JoiningDate)

Every Student, Teacher and Staff member is a Person and inherits PersonID, Name, Address and Phone. The specialization is disjoint and partial here. Its benefit is that attributes specific to a subclass are stored only for that subclass, which avoids null values and redundancy and models real-world differences more accurately. The reverse bottom-up process is called generalization.

Anomalies are problems that arise from data redundancy in poorly designed (unnormalized) relations. There are three types.

Consider Employee_Project(E-ID, E-name, P-ID, P-name) in which employee and project details are repeated in each row.

1. Insertion anomaly: a new fact cannot be recorded without other, unrelated data. A new project cannot be added until an employee is assigned to it, unless null values are stored for the key.
2. Deletion anomaly: deleting one fact unintentionally removes another. If the only employee working on project P03 is deleted, the details of project P03 are lost as well.
3. Update (modification) anomaly: the same data is stored in many rows, so changing it requires updating every copy. If a project's name changes, every row containing it must be updated. Missing one leaves inconsistent data.

Remedy: normalization, i.e. decomposing the relation into smaller well-structured relations (1NF, 2NF, 3NF, BCNF) so that each fact is stored once.

Two-tier architecture (client-server)

 [ Client tier: UI + application logic ]  <----->  [ Server tier: DBMS / database ]

The client application (user interface and business logic) runs on the user's machine and communicates directly with the database server, typically through ODBC/JDBC, sending SQL queries and receiving results.

• Advantages: simple, fast to develop, low latency.
• Disadvantages: business logic sits on every client, so maintenance is hard. It scales poorly, and exposing the database directly to clients is a security risk.

Three-tier architecture

 [ Presentation tier ] <--> [ Application / Business tier ] <--> [ Database tier ]
   (browser, mobile)          (web/app server)                     (DBMS)

• Presentation tier: the user interface (web browser or mobile app); it contains no direct database access.
• Application (middle) tier: holds the business logic and processing. It validates requests, enforces rules and queries the database.
• Database tier: stores and manages the data.
• Advantages: better security because clients never touch the database, better scalability (tiers can be scaled separately), easier maintenance and reuse of business logic.
• Disadvantages: more complex and costly to build and deploy.

Three-tier is the standard for web applications such as online banking and e-commerce.

(i) Insert a record into Subject:

INSERT INTO Subject (SubCode, SubjectName, CreditHours)
VALUES ('IT232', 'DBMS', 3);

(ii) Change the job status of instructor 521:

UPDATE Instructor
SET JobStatus = 'Permanent'
WHERE InstructorID = 521;

(iii) Add a column salary to Instructor:

ALTER TABLE Instructor ADD salary DECIMAL(10,2);

(iv) Name of the instructor with the highest salary:

SELECT InstructorName
FROM Instructor
WHERE salary = (SELECT MAX(salary) FROM Instructor);

(v) Delete the column CreditHours from Subject:

ALTER TABLE Subject DROP COLUMN CreditHours;

Given relation: R(E-ID, E-name, Contact No, P-Id, P-name). Contact No holds multiple values in some rows, and an employee works on many projects, so the key is (E-ID, P-Id).

First Normal Form (1NF)

Every attribute must be atomic, so multi-valued contact numbers are split into separate rows (the typo ",," is read as a single number 5535):

A cleaner 1NF split puts the contact numbers into their own relation. The key then becomes (E-ID, Contact No, P-Id), and this creates partial dependencies, which is the problem 2NF resolves.

Second Normal Form (2NF)

Remove partial dependencies on the composite key (E-ID, P-Id):

• E-ID → E-name
• P-Id → P-name
• Contact numbers depend on E-ID alone.

Decompose into:

• Employee (E-ID, E-name)
• EmployeeContact (E-ID, Contact No)
• Project (P-Id, P-name)
• Works (E-ID, P-Id)

Third Normal Form (3NF)

3NF requires no transitive dependency of a non-key attribute on the key. In each relation above, every non-key attribute depends only on the key (E-name on E-ID, P-name on P-Id), and Works and EmployeeContact are all-key. So no further decomposition is needed.

Final 3NF relations

Redundancy and the insertion, deletion and update anomalies are removed.