Notes

Intension -> Schema of the database Extension -> Actual data stored in database at a point of time

Chapter 2

2 Tire - Users directly interact with the database 3 Tier Architecture - More scalability (can support multiple queries), data sanitizing etc.

Data abstraction - refers to the suppression of details of data organization and storage.

States - Empty, initial and valid state - A state that satisfies the structure and constraints specified in the state.

Internal state - Describes the physical storage structure of the database, including the details of data storage, access paths etc.

Conceptual state - Describes the structure of the whole database of whole database for a community of users eg. Data types, relationships, user operations etc. (Logical structure of the database) (ER Model)

External Level - includes a number of external schemas, where each schema describes the part of database that a particular user group is interested in and hides the rest.

Data independence is the change of schema at one should not affect the next higher level.

(External, Conceptual, Internal)

Logical Independence

The ability to change the conceptual schema without affecting external schemas. Users and applications remain unaffected even if the database structure is modified.

Physical Data Independence

The ability to change the internal schema without changing the conceptual schema, The logical structure of data remains the same even if the physical storage is optimized.

Answers

• Data Model: A logical structure that defines how data is organized, stored, and manipulated in a database (e.g., relational, hierarchical, network).

• Database Schema: The structure of a database, including its tables, attributes, data types, and relationships. It is defined at design time and does not change frequently.

• Database State: The actual data stored in the database at a given time. Unlike the schema, the state changes frequently as records are inserted, updated, or deleted.

• Internal Schema: Defines the physical storage of the database, including file structures, indexing, and storage paths.

• Conceptual Schema: Represents the logical structure of the database, including tables, relationships, and constraints, without focusing on physical storage.

• External Schema: Defines how different users or applications view the database, providing security and abstraction.

• Data Independence: The ability to modify the database schema without affecting application programs or higher schema levels.

• DDL (Data Definition Language): Used to define the database schema (e.g., CREATE TABLE, ALTER TABLE).

• DML (Data Manipulation Language): Used to insert, update, delete, and retrieve data (e.g., SELECT, INSERT, UPDATE, DELETE).

DCL - Required to deal withs the user permissions and controls the database system (GRANT AND REVOKE)

TCL - required to deal with transactions (COMMIT, ROLLBACK)

(DDL, DML, DCL, TCL)

Chapter 3

Constraints

Domain Constraints - ensures that value for a specific attribute belongs to its domain.

Entity Integrity Constraint - Primary cannot be NULL

Referential Integrity Constraint - Foreign key must point to a valid primary key.

Key Constraints - All keys must be unique

===(Domain, Integrity, Referential)===

1) Unary - Select, Rename, Projection 2) Binary - UNION, Intersection, Set Difference, Product

Tuple - Domain is the list of tuples Domain - Domain is the list of attributes

Universal Quantifier indicates that a predicate is true for all elements in a given domain

Existential Quatifier indicates that a predicate is true for atleast one element in a given domain

SELECT E.Fname, E.Lname FROM EMPLOYEE E WHERE EXISTS (SELECT * FROM DEPEDENT D WHERE E.ssn=D.ssn)

SELECT E.Fname, E.Lname FROM EMPLOYEE E WHERE NOT EXISTS (SELECT * FROM DEPEDENT D WHERE E.ssn=D.ssn)

SELECT FROM WHERE DISTINCT Essn WORKS_ON Pno IN (1, 2, 3);

SELECT FROM WHERE Fname, Lname, Address (EMPLOYEE JOIN DEPARTMENT ON Dno=Dnumber) Dname=‘Research’;

SELECT Fname, Lname, Address FROM (EMPLOYEE NATURAL JOIN ON DEPARTMENT AS DEPT (Dname,Dno,Mssn,Msdate));

COUNT(DISTINCT Salary);

ALTER TABLE COMPANY.EMPLOYEE DROP CONSTRAINT EMPSUPERFK CASCADE

1NF - Every column must have single value and atomic, Duplicate columns must be removed

2NF - Every non-prime attribute of the table should be fully dependent on the primary key (No partial dependency)

3NF - (No Transitive dependency) - No non prime attribute should depend on another non prime attribute, but rather the primary key.

3.5NF - For every functional dependency (A->B), A should be the super key of the table. A cant be a non prime key if the B is a prime attribute

4NF - No multi valued dependency

5NF - no further lossless decomposition is possible

===Transaction represents a logical unit of database processing that must be completely in its entirety ===

BEGIN TRANSACTION
END TRANSACTION

Read only transaction Read Write transaction

Granularity - size of data item Data item - can be an attribute, record or disk block

The Lost Update Problem

This occurs when multiple transactions on a data item are interleaved in such a way that incorrect value is written to the database

The Temporary Update (Dirty Read) Problem

Occurs when a transaction T1 fails and another transaction T2 reads the incorrect value before T1 can write back the original value, due to which it is not recorded permanently due to the failure of T1

The Incorrect Summary Problem

Occurs when a transaction is processing an aggregate query and another transaction is updating the values.

(Lost Update, Temporary Update, and Incorrect Summary)

The unrepeatable read problem

Same value is read twice, one original and one modified.

flowchart TB
    A[Types] --- B[Lost Update]
    A[Types] --- C[Temporary Update]
    A[Types] --- D[Incorrect Summary]
    A[Types] --- E[Unrepeatable Read]

State diagram for basic database system

Normalization

Process of reducing redundancy by organizing the data into multiple tables.

ACID

Transactions should possess several properties, often called ACID

Atomicity -  A transaction is an atomic unit of processing, it should either be performed in its entirety or not performed

Consistency - If a transaction is completely executed, it should take the database from one consistent state to another

Isolation - A transaction should appear as though it is being executed in isolation from other transactions.

Durability - The changes applied to the database by a transaction should persist in database, no chance for failure.

Levels of Isolation

1) Level 0 - A transaction is allowed to read data written by another uncommitted transaction. 2) It must not overwrite data written by higher isolation transactions that havent commited yet.

- T1 writes value A = 100

- T2 reads A = 100 before T1 commits

- T1 rolls back — now T2 has read a value that never really existed

1) Level 1 - Dirty reads are still allowed, but lost updates are not.

- T1 reads A = 10

- T2 reads A = 10

- T1 writes A = 15

- T2 writes A = 20 (T1’s update is lost) ❌

4) Level 2 - No dirty reads, No lost updates

Transactions only read committed data, and updates from concurrent transactions do not overwrite each other. 5) No dirty reads, No lost updates, No non repeatable reads If you read a row once in a transaction, the value should not chance if you read it again.

Schedules

Schedule (or history) of n transactions is the ordered of operations of transactions.

Two operations are said to be in conflict if 1) They belong to different transactions 2) Access the same data item 3) Atleast one is write command

Sa: r1(X); r2(X); w1(X); r1(Y); w2(X); w1(Y);

Ordering of the operations also matter

Read write conflict and write write conflict

A complete schedule if 1) The operations are exactly those operations in T1, T2...TN, with commit or abort operations as the last operations in each 2) For any pair of operations from the same transaction, their relative order in S should be the same as in Ti 3) For conflicting operations, one should occur before the other.

committed projection C(S) of a schedule S, which includes only the operations in S that belong to committed trans actions—that is, transactions Ti whose commit operation ci is in S.

Cascading Rollback - An uncommitted transaction is rolled back as it read a value X from a failed transaction

1) Recoverable Transaction 2) Cascadeless Transaction 3) Strict Transaction

Serializability of schedules

Two definitions in equivalence 1) Conflict Equivalence - Same operations, order is the same 2) View Equivalence - Inital Reads, Read from, Final Writes

Precedence graph for conflict serializability

EXEC SQL WHENEVER SQLERROR GOTO UNDO; EXEC SQL SET TRANSACTION READ WRITE DIAGNOSTIC SIZE 5 ISOLATION LEVEL SERIALIZABLE; EXEC SQL INSERT INTO EMPLOYEE (Fname, Lname, Ssn, Dno, Salary) VALUES ('Robert', 'Smith', '991004321', 2, 35000); EXEC SQL UPDATE EMPLOYEE SET Salary = Salary * 1.1 WHERE Dno = 2; EXEC SQL COMMIT; GOTO THE_END; UNDO: EXEC SQL ROLLBACK; THE_END: ... ;

Locks

A database lock is a mechanism to protect a shared piece of data from getting updated by two or more database operations at the same time. If a transaction acquires a lock, then no one else can acquire it.

Shared Locking - A locking mechanism involving multiple modes of locking (shared and exclusive).

Write lock - Exclusive Read Lock - Shared

May not be serializable

2 Phase Locking

1) Growing phase: locks are acquired but no locks are released
2) Shrinking phase: locks are released and no locks are acquired
Guarantees serializability - lock only acquired after the a transaction has unlocked it in its shrinking phase

point just before the first unlock in a transaction is called lock-point

Advantages - ensures serializibility Disadvantages - May not free from irrecoverability Not free from deadlocks Not free from starvations Not free from cascading rollback

Indexing

Indexes - fast retrieval of data instead of linear scan of all database items.

Indexing attributes

Dense Indexing - For every search value in data file, there exists an index record

Sparse Indexing - The index record appear only for some items in data file (we find the largest key less than or equal to the key that we want)

Primary Indexing - Type of indexing in which the data file is sorted based on the primary key, the index file contains primary keys as well as the points to corresponding data records

Primary has both dense and sparse indexing

Clustering is an indexing technique in which the data file is sorted and stored according to a clustering key (may not be unique).

Secondary Indexing is a used to create additional indexes on columns other than primary key (to enhance performance) (non key + unordered).

B-Tree

Specialized m way tree designed to optimize data access. (m children and m-1 keys). It stores the record pointers in intermediate nodes as well

B+ Tree

Instead of storing the record pointers in intermediate, it actually stores in leaf nodes, so space occupied by the intermediate nodes are less and can store significantly more keys, reducing tree height.

select e1.emp_no, e1.emp_name, e1.salary from employee e1
where n-1 = (
    select COUNT(DISTINCT Salary) from employee e2
    where e2.salary > e1.salary
);

Keys

• Primary Key
• Unique Key
• Alternate Key
• Foreign Key
• Composite Key - Combination of two or more columns
• Candidate Key
• Super Key