Database Management System

A DBMS reduces data redundancy and inconsistency, allows data sharing, enforces integrity constraints and security, supports backup and recovery, provides data independence, and gives concurrent access and easy querying (SQL), unlike a file-based system where data is duplicated and tied to application programs.

Data abstraction is hiding the complex storage details from users and showing only the relevant view of the data. It has three levels: physical, logical and view.

A weak entity is an entity that has no primary key of its own and depends on a strong (owner) entity for identification, using a partial key plus the owner's key. Example: Dependent (name) of an Employee; a dependent cannot be identified without the employee.

The GROUP BY clause groups rows having the same values in specified columns so that aggregate functions (COUNT, SUM, AVG, MAX, MIN) are applied to each group, e.g. SELECT dept, AVG(salary) FROM emp GROUP BY dept;

A functional dependency $X \rightarrow Y$ means that the value of attribute set $X$ uniquely determines the value of $Y$: two tuples with the same $X$ value must have the same $Y$ value. Example: $Roll\_No \rightarrow Name$. It is the basis of normalization.

NoSQL databases are popular because they handle huge volumes of unstructured and semi-structured data (big data), scale horizontally across many servers, offer flexible schemas, high speed and availability, and suit web, real-time and cloud applications better than rigid relational databases.

Division ($R \div S$) is used to find the tuples of $R$ that are associated with all tuples of $S$, i.e. to answer "for all" queries, such as finding students who have enrolled in all courses.

A schedule is serializable if its effect (final database state) is equivalent to that of some serial schedule of the same transactions, where transactions run one after another. Serializable schedules keep the database consistent while allowing concurrent execution.

Concurrent transactions are two or more transactions whose operations are interleaved and executed at the same time on the same database. They improve throughput but need concurrency control to avoid problems such as lost update and dirty read.

The three-schema (ANSI-SPARC) architecture separates the user view from physical storage, giving data independence.

• External level (view level): the individual user views, showing only the part of the database relevant to each user group.
• Conceptual level (logical level): the whole database for the community of users: entities, attributes, relationships and constraints, independent of storage.
• Internal level (physical level): how data is physically stored: file structures, indexes and access paths.

Mappings between the levels (external/conceptual and conceptual/internal) convert requests and data from one level to another. Because of them, a change at one level need not affect the higher level.

Specialization is a top-down process of defining subclasses of an entity set based on distinguishing characteristics. Example: the entity Employee is specialized into Teacher and Clerk, each with additional attributes.

Generalization is a bottom-up process of combining several entity sets that share common attributes into a higher-level superclass. Example: Car and Truck are generalized into Vehicle.

In both, the subclass inherits the attributes and relationships of the superclass (the "is-a" relationship, drawn with a triangle in EER diagrams). Constraints can be disjoint/overlapping and total/partial.

Unary operations work on a single relation.

SELECT ($\sigma$): selects the rows (tuples) satisfying a condition, producing a horizontal subset of the relation.

$\sigma_{salary > 20000}(Employee)$

returns all employees whose salary is above 20000.

PROJECT ($\pi$): selects the specified columns (attributes) and removes duplicates, producing a vertical subset.

$\pi_{name, salary}(Employee)$

returns only the name and salary columns of Employee.

They can be combined, e.g. $\pi_{name}(\sigma_{salary>20000}(Employee))$.

Data Definition Language (DDL) defines and modifies the structure (schema) of the database. Its commands are auto-committed.

• CREATE creates objects: CREATE TABLE student(id INT PRIMARY KEY, name VARCHAR(30));
• ALTER modifies a table: ALTER TABLE student ADD age INT;
• DROP deletes an object: DROP TABLE student;
• TRUNCATE removes all rows; RENAME renames objects.

Data Manipulation Language (DML) is used to retrieve and change the data stored in tables.

• SELECT retrieves data: SELECT name FROM student WHERE age > 18;
• INSERT adds rows: INSERT INTO student VALUES(1,'Ram',20);
• UPDATE modifies rows: UPDATE student SET age=21 WHERE id=1;
• DELETE removes rows: DELETE FROM student WHERE id=1;

DML changes can be rolled back before commit.

A transaction is a logical unit of work consisting of one or more database operations (read/write) that must be executed completely or not at all, taking the database from one consistent state to another. Example: transferring money, which debits one account and credits another.

ACID properties:

• Atomicity: all operations of the transaction are done, or none are (all-or-nothing); a failed transaction is rolled back.
• Consistency: a transaction takes the database from one valid state to another, preserving integrity constraints.
• Isolation: concurrent transactions do not interfere; each appears to run alone.
• Durability: once committed, changes are permanent even after system failure.

Types of relationship in an ER diagram

By degree: unary (recursive; one entity set with itself), binary (two entity sets) and ternary (three entity sets).

By cardinality (binary):

• One-to-one (1:1): one A is related to at most one B (e.g. Person - Passport).
• One-to-many (1:N): one A is related to many B (e.g. Department - Employee).
• Many-to-one (N:1): many A relate to one B.
• Many-to-many (M:N): many A relate to many B (e.g. Student - Course).

Participation may be total or partial.

Converting an ER diagram to tables

1. Strong entity: make a table; attributes become columns; the key attribute becomes the primary key. Composite attributes are split into their simple components.
2. Weak entity: make a table including the partial key plus the primary key of the owner entity (as foreign key); the primary key is their combination.
3. Multivalued attribute: make a separate table with the entity's primary key and the attribute; the key is the combination.
4. 1:1 relationship: put the primary key of one side as a foreign key in the other (preferably on the total-participation side).
5. 1:N relationship: put the primary key of the "one" side as a foreign key in the "many" side table.
6. M:N relationship: create a new table with the primary keys of both entities as foreign keys (together forming the primary key) plus the relationship's own attributes.
7. Specialization/generalization: make a table for the superclass and a table for each subclass containing the superclass key as primary and foreign key.

Example: Student (S_id, name) and Course (C_id, title) in M:N "Enrolls" give tables Student, Course and Enrolls(S_id, C_id, date).

Join operation

A join ($\bowtie$) combines related tuples from two relations into a single tuple based on a join condition on common attributes. Types include inner (natural/theta/equi) join and outer joins (left, right, full), where an outer join also keeps tuples that have no match, filling missing values with NULL.

Join attribute: Emp_name.

Left outer join (Employee ⟕ Branch)

All Employee rows are kept; unmatched rows get NULL.

Right outer join (Employee ⟖ Branch)

All Branch rows are kept; unmatched rows get NULL.

SQL: SELECT * FROM Employee e LEFT OUTER JOIN Branch b ON e.Emp_name = b.Emp_name; (and RIGHT OUTER JOIN for the right join).

Need for database recovery

A database can fail because of transaction errors, system crashes, power failure, disk failure or software bugs. Recovery is essential to restore the database to the latest consistent state, to preserve atomicity (partial updates of failed transactions are undone) and durability (committed updates are not lost), and to avoid data loss and inconsistency.

Shadow paging

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

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 modified during the transaction.
2. When a page is to be written, a new copy of the page is written to a free disk block, and the current page table is updated to point to this new page. The old page remains pointed to by the shadow table.
3. Commit: the current page table is made the new shadow page table (by atomically changing the pointer to the page table in a fixed location). Old pages are freed.
4. Failure/rollback: the current page table is discarded and the shadow page table is used; the database returns to its state before the transaction. No undo or redo is needed.

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

Concurrency control manages the simultaneous execution of transactions so that the database stays consistent. Running transactions one at a time is safe but slow; concurrent execution improves throughput, resource utilization and response time, but uncontrolled interleaving causes problems:

• Lost update: two transactions read the same value and both write, so one update is overwritten.
• Dirty read (temporary update): a transaction reads data written by another transaction that later aborts.
• Unrepeatable read: a transaction reads the same item twice and gets different values because another transaction changed it.
• Phantom read: a repeated query returns extra rows inserted by another transaction.
• Incorrect summary: an aggregate is computed while others update items.

Concurrency control ensures isolation and serializability so that the result equals some serial execution. Techniques include lock-based protocols (shared/exclusive locks, two-phase locking), timestamp ordering, optimistic (validation) methods and multiversion concurrency control.

ER diagram

Entities and attributes (key underlined in a drawing):

• Restaurant (R_ID, R_Name, R_address)
• Cook (C_id, C_name, C_specilization, salary)
• Branch (B_ID, Total_No_Sales, revenue) - a weak entity of Restaurant, identified by B_ID with owner R_ID (R_ID is its foreign key).

Relationships:

• Works_At between Cook and Restaurant, many-to-many, with attributes Workinghrs and Wshift.
• Has between Restaurant and Branch, one-to-many (a restaurant has many branches; each branch belongs to one restaurant).

 Cook (C_id) ---M--- <Works_At: Workinghrs, Wshift> ---N--- Restaurant (R_ID)
                                                                 |
                                                               <Has>
                                                                 | 1
                                                                 N
                                                           Branch (B_ID)

SQL queries

a. Name and address of restaurants where the working shift is "day":

SELECT DISTINCT r.R_Name, r.R_address
FROM Restaurant r JOIN Works_At w ON r.R_ID = w.R_ID
WHERE w.Wshift = 'day';

b. Names of all cooks specialized in Italian:

SELECT C_name FROM Cook WHERE C_specilization = 'Italian';

c. Number of cooks whose working hours are "night" (the working shift is taken as night):

SELECT COUNT(DISTINCT C_id) FROM Works_At WHERE Wshift = 'night';

d. Average salary of the cooks:

SELECT AVG(salary) FROM Cook;

e. Names of restaurants and their branches generating revenue more than 15000:

SELECT r.R_Name, b.B_ID
FROM Restaurant r JOIN Branch b ON r.R_ID = b.R_ID
WHERE b.revenue > 15000;

Importance of normalization

Normalization is the process of organizing tables, using functional dependencies, to reduce redundancy and avoid anomalies. Its importance:

• reduces data redundancy and saves storage,
• avoids insertion, deletion and update anomalies,
• maintains data consistency and integrity,
• gives a logical, well-structured design that is easy to maintain and extend.

(Over-normalization can slow queries because of many joins.)

First Normal Form (1NF)

A relation is in 1NF if all attributes hold only atomic (indivisible) values, with no multivalued or repeating groups.

Not in 1NF:

In 1NF (one value per cell):

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on part of a composite candidate key.

Example: Enroll(Roll, Course, Student_name, Grade) with key (Roll, Course). Here $Roll \rightarrow Student\_name$ is a partial dependency. Decompose into:

• Student(Roll, Student_name)
• Enroll(Roll, Course, Grade)

Third Normal Form (3NF)

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

Example: Student(Roll, Name, Dept, Dept_head) with $Roll \rightarrow Dept$ and $Dept \rightarrow Dept\_head$, so $Roll \rightarrow Dept\_head$ is transitive. Decompose into:

• Student(Roll, Name, Dept)
• Department(Dept, Dept_head)

Each decomposition is lossless and removes the anomalies (for example, changing a department head now needs one update).