Database Management System

Data independence is the ability to change the schema at one level of a database system without having to change the schema at the next higher level. Physical data independence means changing the internal (storage) schema without affecting the conceptual schema; logical data independence means changing the conceptual schema without affecting external schemas or application programs.

Specialization is a top-down process of defining a set of subclasses of an entity type (superclass) based on some distinguishing characteristic. For example, EMPLOYEE can be specialized into SECRETARY, ENGINEER and TECHNICIAN; each subclass inherits the attributes of the superclass and may have its own.

Keys are used to:

• uniquely identify each tuple (row) in a table (primary key, candidate key, super key);
• establish relationships between tables (foreign key);
• enforce entity and referential integrity and prevent duplicate records;
• speed up searching and retrieval of data.

DDL (Data Definition Language) is the set of SQL commands used to define and modify the structure of database objects such as tables, views and indexes. Examples are CREATE, ALTER, DROP and TRUNCATE.

A functional dependency $X \rightarrow Y$ between two sets of attributes of a relation means that the value of $X$ uniquely determines the value of $Y$: if two tuples have the same $X$ value, they must have the same $Y$ value. For example, $\text{SID} \rightarrow \text{SName}$.

A schedule of concurrent transactions is serializable if its effect is equivalent to that of some serial schedule (one in which the transactions execute one after another with no interleaving). It therefore keeps the database consistent even though operations are interleaved.

The desirable properties of a transaction are the ACID properties:

• Atomicity: all operations of the transaction are done or none are.
• Consistency: the transaction takes the database from one consistent state to another.
• Isolation: concurrent transactions do not see each other's intermediate results.
• Durability: once committed, the changes persist even after a failure.

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; until then they are only recorded in the log. If the transaction fails before commit, nothing needs to be undone (NO-UNDO/REDO); after a crash, committed transactions are redone from the log.

Shadow paging is a recovery technique that maintains two page tables during a transaction: the current page table and the shadow page table. Updates are written to new pages and referenced only by the current table, while the shadow table keeps pointing to the old pages. On failure the shadow table is simply restored; on commit it is replaced by the current table. No log is required.

Big Data refers to extremely large and complex datasets that cannot be stored, managed or processed efficiently by traditional database tools. It is commonly characterized by the 3 Vs: Volume, Velocity and Variety.

Constraints on specialization/generalization

• Predicate-defined (condition-defined): membership in a subclass is decided by a condition on an attribute of the superclass, e.g. JobType = 'Secretary'. If the same attribute defines all subclasses, it is attribute-defined. Otherwise it is user-defined, where the user assigns entities to subclasses.
• Disjointness constraint: subclasses are disjoint (an entity belongs to at most one subclass) or overlapping (an entity may belong to more than one).
• Completeness (participation) constraint: total means every entity of the superclass must belong to some subclass; partial means some entities may belong to none.

Characteristics

• Subclasses inherit all attributes and relationships of the superclass (attribute and relationship inheritance).
• A subclass may have its own local attributes and relationships.
• Specialization is top-down refinement, whereas generalization is bottom-up, combining entity types with common features into a superclass.

The combinations are disjoint total, disjoint partial, overlapping total and overlapping partial.

Relationship sets 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.
• Ternary: three entity sets, e.g. SUPPLIER supplies PART to PROJECT.

By cardinality (binary relationships)

• One-to-one (1:1): each entity in A relates to at most one in B and vice versa, e.g. a manager manages one department.
• One-to-many (1:N): one entity in A relates to many in B, e.g. a department has many employees.
• Many-to-one (N:1): the reverse of 1:N.
• Many-to-many (M:N): many entities in A relate to many in B, e.g. students and courses.

Three common SQL data types:

1. INT: stores whole numbers. Example: Age INT holds 21.
2. VARCHAR(n): variable-length character string of up to n characters. Example: SName VARCHAR(50) holds 'Ram'.
3. DATE: stores a date in the form YYYY-MM-DD. Example: DOB DATE holds '2002-05-14'.

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

Other types include CHAR, FLOAT/DECIMAL, and TIME.

Decomposing a relation $R$ into smaller relations $R_1, R_2, \dots, R_n$ should have these properties:

1. Attribute preservation: every attribute of $R$ appears in at least one $R_i$, so $R_1 \cup R_2 \cup \dots \cup R_n = R$.
2. Lossless (non-additive) join: joining the decomposed relations gives back exactly the original tuples, with no spurious tuples. For a binary decomposition, it is lossless if $R_1 \cap R_2 \rightarrow R_1$ or $R_1 \cap R_2 \rightarrow R_2$.
3. Dependency preservation: every functional dependency of $R$ can be enforced in the individual $R_i$ (or derived from the dependencies that hold in them) without joining the relations.
4. Each $R_i$ is in a desirable normal form (e.g. 3NF or BCNF), reducing redundancy and anomalies.

A catastrophic failure is one in which the disk itself is damaged (for example, a head crash), so the database and possibly the log are lost. Recovery uses backups:

1. Periodic backup: the whole database and the log are regularly copied (dumped) to tape or another disk, kept at a separate safe location.
2. Restore: after a failure, the most recent backup copy of the database is loaded to a new disk.
3. Redo using the log: the system log, which is backed up more frequently or stored on a separate disk, is used to redo all operations of transactions that committed after the backup was taken, bringing the database up to the time of failure.
4. Transactions that were active and uncommitted at the time of failure are ignored or rolled back.

Frequent backups of the log (and keeping it on a separate disk) reduce the amount of work lost.

In the immediate update technique, a transaction's updates may be written to the database before the transaction commits. Because uncommitted changes may reach the disk, the log must hold both the old value (before image) and new value (after image), and the write-ahead logging rule applies: log records are written to disk before the corresponding data item is changed.

Recovery after a crash

• Transactions that had committed (both [start_transaction, T] and [commit, T] are in the log) are redone, using the new values.
• Transactions that had started but not committed are undone, restoring the old values from the log, in reverse order.

So the algorithm is UNDO/REDO. A variant that forces all updates to disk before commit needs only UNDO.

The three-schema architecture separates the user's view of the database from its physical storage, supporting data independence and multiple views. It has three levels:

1. External (view) level: the highest level, consisting of many external schemas (user views). Each describes only the part of the database a particular user group is interested in and hides the rest.
2. Conceptual level: a single conceptual schema describing the structure of the whole database for the community of users: entities, data types, relationships, constraints. It hides physical storage details.
3. Internal level: the internal schema describes the physical storage structure: file organization, indexes, access paths and record placement.

External view 1   External view 2   ...   External view n
          \              |                 /
           ---- external/conceptual mapping ----
                  Conceptual schema
           ---- conceptual/internal mapping ----
                   Internal schema
                  Stored database

Mappings: the DBMS translates requests between levels through the external/conceptual and conceptual/internal mappings.

Advantages: it provides logical data independence (the conceptual schema can change without changing external views) and physical data independence (the internal schema can change without changing the conceptual schema), improves security by restricting what each user sees, and allows each user a customized view.

Entities and attributes (primary keys underlined by the (PK) tag)

• CUSTOMER (CustomerID (PK), Name, Phone, Email, Address)
• RESTAURANT (RestaurantID (PK), Name, Location, Phone)
• FOOD_ITEM (ItemID (PK), Name, Price, Category)
• ORDER (OrderID (PK), OrderDate, TotalAmount, Status)
• PAYMENT (PaymentID (PK), Method, Amount, PayDate)
• DELIVERY_PERSON (DeliveryID (PK), Name, Phone)

Relationships

• CUSTOMER places ORDER: 1 to N (a customer places many orders; each order is placed by one customer).
• ORDER contains FOOD_ITEM: M to N, with relationship attribute Quantity.
• RESTAURANT offers FOOD_ITEM: 1 to N.
• ORDER has PAYMENT: 1 to 1.
• DELIVERY_PERSON delivers ORDER: 1 to N.

Diagram (rectangles are entities, diamonds are relationships)

[CUSTOMER] --1--<places>--N-- [ORDER] --N--<contains>--M-- [FOOD_ITEM] --N--<offers>--1-- [RESTAURANT]
                                 |  \                 (Quantity)
                                 1   N
                            <has>     <delivers>
                                 |         |
                                 1         1
                            [PAYMENT] [DELIVERY_PERSON]

Attributes hang from each rectangle as ovals; the key attribute of each entity is underlined.

Concurrency control is the set of techniques a DBMS uses to manage simultaneous execution of transactions so that they do not interfere with each other and the database stays consistent (preventing problems such as lost update, dirty read and unrepeatable read) while maintaining isolation and serializability.

Locking is the most common technique: a transaction must lock a data item before accessing it. A shared (read) lock allows many readers; an exclusive (write) lock allows only one transaction.

Two-phase locking (2PL) protocol

A transaction follows 2PL if all its locking operations precede its first unlock operation. It 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 new ones.

Locks held
   |      /\
   |     /  \
   |    /    \
   +---/------\----> time
     growing  shrinking

Result: any schedule in which all transactions obey 2PL is guaranteed to be conflict serializable.

Variants: Strict 2PL holds all exclusive locks until commit/abort (avoids cascading rollback); rigorous 2PL holds all locks until commit; conservative 2PL acquires all locks before starting (avoids deadlock).

Drawback: 2PL can cause deadlock, which must be detected or prevented.

Data warehouse: a large, centralized repository of integrated data collected from multiple heterogeneous sources, designed for query and analysis rather than day-to-day transaction processing. According to Inmon it is subject-oriented, integrated, time-variant and non-volatile. It stores historical data to support decision making, usually organized with fact and dimension tables, and loaded through ETL (extract, transform, load).

Data mining: the process of discovering previously unknown, useful patterns, relationships and trends from large amounts of data using statistical, machine-learning and database techniques. It is a step in Knowledge Discovery in Databases (KDD).

Main tasks:

• Association rule mining: finding items that occur together.
• Classification: assigning records to predefined classes.
• Clustering: grouping similar records without predefined classes.
• Prediction/regression and outlier detection.

Example: a supermarket mines its sales data and finds the rule bread -> butter with 80% confidence. It then places the two items close together or offers a joint discount. Similarly, a bank can classify loan applicants as high or low risk from past records.

Need for normalization

Normalization is the process of organizing relations to reduce redundancy and avoid anomalies. Without it, a badly designed table 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, otherwise the data becomes inconsistent.

Normalization also improves data integrity and makes the schema easier to maintain.

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:

In 1NF (each cell has one value):

Second Normal Form (2NF)

A relation is in 2NF if it is in 1NF and every non-key attribute is fully functionally dependent on the whole primary key (no partial dependency). It matters only for composite keys.

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

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

Third Normal Form (3NF)

A relation is in 3NF if it is in 2NF and no non-key attribute is transitively dependent on the primary key (no non-key attribute determines another non-key attribute).

Example: STUDENT(SID, SName, DeptID, DeptName) with $SID \rightarrow DeptID$ and $DeptID \rightarrow DeptName$ gives the transitive dependency $SID \rightarrow DeptName$. Decompose into:

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

Each step removes a kind of redundancy: 1NF removes repeating groups, 2NF removes partial dependencies, and 3NF removes transitive dependencies.

(a)

INSERT INTO student (SID, SName, SAddress, SEmail)
VALUES ('S101', 'Ram', 'Lalitpur', 'ram@abc.com');

(b)

SELECT SName
FROM student
WHERE SAddress = 'Kathmandu';

(c)

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

(d)

SELECT COUNT(s.SID)
FROM student s, studies st, course c
WHERE s.SID = st.SID
  AND st.CID = c.CID
  AND c.CName = 'Database Management System';

(e)

SELECT CName
FROM course
WHERE Credit_hours >= 3;