Database Management System (old course)

Embedded SQL means placing SQL statements inside a host programming language such as C, Java or COBOL. A precompiler translates the SQL statements (usually marked with EXEC SQL) into calls of the host language. It lets the program use database facilities while the host language provides control structures and user interface.

Embedded SQL means SQL statements are written inside a host programming language (such as C, C++ or Java), so that the program can access the database. SQL statements are marked with a prefix such as EXEC SQL and terminated with a delimiter; a precompiler replaces them with function calls to the DBMS library before the program is compiled. Host variables, prefixed with a colon, exchange data between the program and SQL, and cursors are used to process query results one row at a time.

EXEC SQL SELECT name INTO :n FROM student WHERE roll = :r;

An insertion anomaly occurs when certain data cannot be inserted into a table without also inserting other unrelated data, because of redundancy in the design.

Example: in Student(RollNo, Name, CourseID, CourseName), a new course cannot be added until at least one student enrols in it, since RollNo (part of the key) cannot be null.

A trigger is a stored procedure-like block of code that is executed automatically by the DBMS in response to an event (INSERT, UPDATE or DELETE) on a table. It is used to enforce business rules, auditing and maintain derived data.

Syntax:

CREATE TRIGGER trigger_name
{BEFORE | AFTER} {INSERT | UPDATE | DELETE}
ON table_name
FOR EACH ROW
BEGIN
    -- trigger body (SQL statements)
END;

Example:

CREATE TRIGGER log_delete
AFTER DELETE ON Student
FOR EACH ROW
INSERT INTO Audit(RollNo, Action) VALUES (OLD.RollNo, 'deleted');

An attribute is extraneous in a functional dependency if it can be removed from the dependency without changing the closure of the set of dependencies. For $F$ and $\alpha \rightarrow \beta$:

• $A$ is extraneous in $\alpha$ if $A \in \alpha$ and $F$ implies $(\alpha - A) \rightarrow \beta$.
• $A$ is extraneous in $\beta$ if $A \in \beta$ and $(F - \{\alpha \rightarrow \beta\}) \cup \{\alpha \rightarrow (\beta - A)\}$ implies $\alpha \rightarrow \beta$.

Example: with $F=\{A \rightarrow C, AB \rightarrow C\}$, $B$ is extraneous in $AB \rightarrow C$.

A trigger is a statement stored in the database that the DBMS executes automatically as a side effect of a modification (INSERT, UPDATE or DELETE) on a specified table. It is defined by an event, an optional condition and an action (the ECA model), and is used to enforce complex integrity rules, auditing and automatic updates.

A view is a virtual relation that does not store data itself; it is defined by a query over one or more base tables and is computed when used. Views hide data (security) and simplify complex queries.

Syntax:

CREATE VIEW view_name [(column_list)] AS
  <query expression>;

Example:

CREATE VIEW cs_students AS
  SELECT roll, name FROM student WHERE dept = 'CS';

The fundamental operations of relational algebra are:

1. Select ($\sigma$): chooses tuples that satisfy a condition.
2. Project ($\pi$): chooses specified attributes (columns).
3. Union ($\cup$): tuples in either relation.
4. Set difference ($-$): tuples in one relation but not in the other.
5. Cartesian product ($\times$): all combinations of tuples from two relations.
6. Rename ($\rho$): renames a relation or attributes.

Operations such as join, intersection and division can be derived from these.

Embedded SQL is required because SQL alone is not a complete programming language: it has no loops, conditions or user-interface facilities. By embedding SQL statements in a host language (C, Java, COBOL), programs can use the full power of the language for computation, control flow, input and output and report generation, while accessing the database through SQL. It also allows queries to be written for applications that need the result processed row by row.

Data abstraction is the process of hiding the details of how data is stored and maintained and showing users only the information relevant to them. It makes the system easy to use while the complexity is hidden. A DBMS provides three levels of abstraction.

1. Physical level (internal level)

The lowest level. It describes how the data is actually stored on the disk, including file organization, indexes, storage structures and access paths. Only database administrators and system programmers deal with it.

2. Logical level (conceptual level)

The next higher level. It describes what data is stored in the database and the relationships among the data: tables, attributes, data types, keys and constraints. It is the view of the database administrator, and physical details are hidden.

3. View level (external level)

The highest level. It describes only the part of the database relevant to a particular user or application. Many different views may exist for the same database, which also gives security by hiding the rest of the data.

Data independence: Because of these levels, a change at a lower level does not affect the level above it. Physical data independence is the ability to change the physical schema without changing the logical schema, and logical data independence is the ability to change the logical schema without changing the views or application programs.

Example: for a Student table, the view level shows a student his own marks, the logical level defines the attributes RollNo, Name, Marks, and the physical level stores the records in blocks of a file with a B+ tree index.

A relation $R$ is in third normal form (3NF) if it is in 2NF and, for every non-trivial functional dependency $X \rightarrow A$ in $R$, either $X$ is a superkey, or $A$ is a prime attribute (part of some candidate key). Equivalently, no non-prime attribute is transitively dependent on a key.

A relation $R$ is in third normal form (3NF) if it is in 2NF and, for every non-trivial functional dependency $X \rightarrow A$ in $R$, either $X$ is a superkey, or $A$ is a prime attribute (part of some candidate key). Equivalently, no non-prime attribute is transitively dependent on a key.

A functional dependency $X \to Y$ between sets of attributes of a relation $R$ means that whenever two tuples agree on the values of $X$, they must also agree on the values of $Y$; the value of $X$ determines the value of $Y$. For example, $roll \to name$ in a STUDENT relation. Functional dependencies are the basis for keys and normalization.

The fundamental (basic) operations of relational algebra are:

1. Select ($\sigma$): chooses tuples satisfying a condition.
2. Project ($\pi$): chooses specified attributes (columns).
3. Union ($\cup$): tuples in either relation.
4. Set difference ($-$): tuples in one relation but not the other.
5. Cartesian product ($\times$): all combinations of tuples of two relations.
6. Rename ($\rho$): renames a relation or its attributes.

All other operations, such as join, intersection and division, can be expressed using these.

Embedded SQL is required because SQL alone is declarative and cannot do everything a general-purpose language can, such as complex computation, loops, user interfaces and report generation. By embedding SQL statements in a host language (C, Java, COBOL), applications get the full power of the programming language together with database access. Some queries also cannot be expressed in SQL alone, and results often need to be processed one row at a time.

Data abstraction hides the complex details of data storage from users. A database system has three levels.

1. Physical level (internal level): the lowest level. It describes how the data is actually stored on disk, such as file organisation, indexes, and blocks.
2. Logical level (conceptual level): describes what data is stored and the relationships among the data (entities, attributes, constraints). Database administrators work at this level, without worrying about physical details.
3. View level (external level): the highest level. It describes only the part of the database relevant to a particular user or group, and hides the rest. A database can have many views, which also helps security.

The levels are linked by mappings, which give data independence between them.

A functional dependency $X \to 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, roll_no → name.

Organizations use a database to store large amounts of data in an organized way, reduce redundancy and inconsistency, share data among many users, enforce security and integrity, allow fast and flexible retrieval through queries, and support backup, recovery and decision making.

Organizations should use a database (managed by a DBMS) instead of file-based systems for the following reasons.

• Reduced data redundancy and inconsistency: data is stored once in a central place, so duplicate copies do not drift apart.
• Data sharing: many users and applications can access the same data concurrently.
• Data integrity: integrity constraints (keys, domain, referential) keep data correct and valid.
• Security: access rights and authorization control who can view or change data.
• Concurrency control: simultaneous transactions are handled without producing wrong results.
• Backup and recovery: the DBMS restores data after failures, giving reliability.
• Data independence: programs are insulated from changes in storage structure.
• Efficient query and retrieval: SQL and indexing give fast, flexible access to data, helping decision making.
• Standards enforcement and lower maintenance cost: centralized control makes standards easier to apply and reduces development effort.

Referential integrity is a constraint which ensures that a foreign key value in one relation must either be null or match an existing primary key value in the referenced relation. It prevents references to non-existent tuples.

Example: in Student(RollNo, Name, DeptID) and Department(DeptID, DeptName), DeptID in Student is a foreign key referencing Department. A student cannot be inserted with DeptID = 9 if no department with ID 9 exists.

An attribute in a functional dependency is extraneous if it can be removed from the left or right side without changing the closure of the set of dependencies.

For a set $F$ and a dependency $\alpha \to \beta$:

• Attribute $A$ is extraneous in $\alpha$ if $A \in \alpha$ and $F$ implies $(F - \{\alpha \to \beta\}) \cup \{(\alpha - A) \to \beta\}$.
• Attribute $A$ is extraneous in $\beta$ if $A \in \beta$ and the set $(F - \{\alpha \to \beta\}) \cup \{\alpha \to (\beta - A)\}$ implies $F$.

Example: with $F = \{A \to C,\ AB \to C\}$, $B$ is extraneous in $AB \to C$ because $A \to C$ already holds. Removing extraneous attributes is a step in finding the canonical cover.

Advantages of a view:

• Security: users see only selected rows and columns, hiding sensitive data.
• Simplicity: a complex query (joins, aggregates) can be saved as a view and used like a table.
• Logical data independence: the view stays the same even if the underlying tables change.
• Different users can see the same data in different forms.

Partial functional dependency: In a relation with a composite primary key, an attribute that depends on only a part of the key is partially dependent. For key $(A, B)$, if $A \to C$ holds where $C$ is a non-key attribute, then $C$ is partially dependent on the key. Example: in Enrol(StudentID, CourseID, StudentName), $StudentID \to StudentName$.

Transitive functional dependency: If $A \to B$ and $B \to C$ hold, and $B \not\to A$, then $A \to C$ is a transitive dependency; $C$ depends on $A$ through the non-key attribute $B$. Example: $EmpID \to DeptID$ and $DeptID \to DeptName$ gives $EmpID \to DeptName$.

The schema of a database is its overall logical design or structure. It describes the tables (relations), their attributes, data types, keys and constraints and the relationships among them, but not the actual data. It changes rarely, whereas the data stored in it (the instance) changes often.

Example: Student(RollNo, Name, Address).

The buffer manager is the DBMS component that manages the main-memory buffer. It fetches disk blocks into the buffer when they are needed, decides which block to replace (using a policy such as LRU) when the buffer is full, writes modified blocks back to disk, and keeps frequently used blocks in memory. This reduces disk I/O and speeds up query processing.

Normalization is the process of organizing the attributes and relations of a database to reduce data redundancy and avoid insertion, update and deletion anomalies. It does this by decomposing a relation into smaller relations using functional dependencies, without losing information (lossless decomposition).

First Normal Form (1NF)

A relation is in 1NF if every attribute contains only atomic (indivisible) values; there are no multivalued attributes or repeating groups.

Not in 1NF:

In 1NF (each cell has a single value):

Alternatively, phone numbers can be moved to a separate relation StudentPhone(StudentID, Phone).

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, i.e. there is no partial dependency. It matters only when the key is composite.

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

• $StudentID \to StudentName$ is a partial dependency, so the relation is not in 2NF.
• $(StudentID, CourseID) \to Grade$ is a full dependency.

Decompose into:

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

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

(a) Students who live in Lalitpur

SQL:

SELECT StudentName FROM Student WHERE Address = 'Lalitpur';

Relational algebra: $\pi_{StudentName}(\sigma_{Address='Lalitpur'}(Student))$

(b) Teachers who teach Database Management System

SQL:

SELECT TecherName FROM Teachers
WHERE TeachingSubject = 'Database Management System';

Relational algebra: $\pi_{TecherName}(\sigma_{TeachingSubject='Database\ Management\ System'}(Teachers))$

(c) Teacher who teaches Computer Organization to student John Smith

SQL:

SELECT T.TecherName
FROM Teachers T, College C, Student S
WHERE T.TeacherID = C.TeacherID
  AND C.RollNumber = S.RollNumber
  AND T.TeachingSubject = 'Computer Organization'
  AND S.StudentName = 'John Smith';

Relational algebra: $\pi_{TecherName}\big(\sigma_{TeachingSubject='Computer\ Organization' \wedge StudentName='John\ Smith'}(Teachers \bowtie College \bowtie Student)\big)$

(d) Insert a new tuple into Teachers

INSERT INTO Teachers (TeacherID, TecherName, TeachingSubject)
VALUES (101, 'Hari Sharma', 'Database Management System');

Relational algebra: $Teachers \leftarrow Teachers \cup \{(101, \text{Hari Sharma}, \text{Database Management System})\}$

(e) Delete records of students whose address is Pokhara

DELETE FROM Student WHERE Address = 'Pokhara';

Relational algebra: $Student \leftarrow Student - \sigma_{Address='Pokhara'}(Student)$

(If College references Student through a foreign key, the related College tuples must also be deleted, or ON DELETE CASCADE used, to keep referential integrity.)

A database is an organized collection of related data, stored so that it can be easily accessed, managed and updated. Example: the records of students, courses and results of a college.

The difference operator ($-$) is used to delete records. To delete the tuples satisfying a condition from relation $r$: $r \leftarrow r - \sigma_{condition}(r)$.

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

Example: UPDATE Student SET Age = 22 WHERE Roll = 5;. Without WHERE, all rows are updated.

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

Example: CREATE VIEW CS_Students AS SELECT Roll, Name FROM Student WHERE Dept = 'CS';

A foreign key is an attribute (or set of attributes) in one relation whose values must match the primary key (or a candidate key) values of another relation, or be null. It links two relations and enforces referential integrity. Example: Roll in Class referencing Roll in Student.

A cardinality constraint (mapping cardinality) in an E-R model specifies the number of entities of one entity set that can be associated with entities of another set through a relationship set. The types are one-to-one, one-to-many, many-to-one and many-to-many.

The storage manager is the DBMS component that provides the interface between the low-level data stored on disk and the application programs and queries. Its roles:

• Interacting with the file manager to store, retrieve and update data on disk.
• Authorization and integrity management (checking integrity constraints and user access rights).
• Transaction management (keeping the database consistent despite failures and concurrent access).
• Buffer management (moving data between disk and main memory) and maintaining indices and data files.

A strong entity set is an entity set that has a primary key of its own, formed from its own attributes, so its entities can be uniquely identified without depending on any other entity set. It is drawn with a single rectangle. Example: Student with key Roll.

DBMS. A Database Management System is software that lets users define, create, maintain and control access to a database. It provides an environment to store and retrieve data conveniently and efficiently, with security, integrity, concurrency control and recovery. Examples: MySQL, Oracle, SQL Server.

Data independence. The ability to change the schema at one level without having to change the schema at the next higher level.

• Physical data independence: the physical (internal) schema can be changed, for example file organization, indexes or storage devices, without changing the conceptual schema or application programs.
• Logical data independence: the conceptual schema can be changed, for example by adding an attribute or entity, without changing external schemas or application programs. It is harder to achieve.

Three-level architecture (ANSI/SPARC).

1. External (view) level: the user's view. Each user group sees only the part of the database relevant to it, through external schemas or views. It hides the rest of the data.
2. Conceptual (logical) level: describes the whole database for the community of users: entities, attributes, relationships, constraints, security and integrity. It hides storage details.
3. Internal (physical) level: describes how data is actually stored: file structures, indexes, record formats and access paths.

The mappings between levels (external/conceptual and conceptual/internal) are maintained by the DBMS and provide data independence. Changes at a lower level are absorbed by changing the mapping, so users and programs are unaffected.

SQL DDL is the part of SQL used to define and modify the structure of database objects (schema). Its commands include CREATE, ALTER, DROP and TRUNCATE. It also specifies constraints such as primary key, foreign key, CHECK and NOT NULL.

CREATE TABLE Student (
    Roll   INTEGER PRIMARY KEY,
    Age    INTEGER CHECK (Age > 20),
    Gender VARCHAR(10) CHECK (Gender IN ('Male', 'Female'))
);

CREATE TABLE Class (
    ClassNo         INTEGER PRIMARY KEY,
    Roll            INTEGER,
    NumberOfStudent INTEGER CHECK (NumberOfStudent > 0),
    FOREIGN KEY (Roll) REFERENCES Student(Roll)
);

Generalization is a bottom-up process: several lower-level entity sets that share common attributes are combined into a higher-level entity set. Example: Car and Truck are generalized into Vehicle, which holds the common attributes.

Specialization is a top-down process: a higher-level entity set is divided into lower-level entity sets that have distinctive attributes or relationships. Example: Employee is specialized into Manager and Clerk. The lower-level sets inherit the attributes of the higher-level set (ISA relationship).

Constraints on generalization

1. Condition-defined vs user-defined (membership constraint). In condition-defined, membership is decided by a condition on an attribute (for example job_type = "manager"). In user-defined, the database user assigns each entity to a lower-level set, with no explicit condition.
2. Disjoint vs overlapping. Disjoint means an entity can belong to at most one lower-level set (an account is either Savings or Current). Overlapping means an entity may belong to more than one (a person can be both Employee and Student).
3. Completeness constraint. Total means every higher-level entity must belong to at least one lower-level set (every Account is Savings or Current). Partial means some higher-level entities need not belong to any lower-level set (an Employee need not be a Manager or Clerk).

Extraneous attributes. An attribute of a functional dependency is extraneous if removing it does not change the closure $F^+$ of the set of dependencies.

• $A \in \alpha$ is extraneous in $\alpha \rightarrow \beta$ if $F$ implies $(\alpha - A) \rightarrow \beta$. Test: compute $(\alpha - A)^+$ under $F$; if it contains $\beta$, $A$ is extraneous.
• $A \in \beta$ is extraneous if $F' = (F - \{\alpha \rightarrow \beta\}) \cup \{\alpha \rightarrow (\beta - A)\}$ implies $F$. Test: compute $\alpha^+$ under $F'$; if it contains $A$, $A$ is extraneous.

Canonical cover $F_c$ is a minimal set equivalent to $F$ in which no dependency has an extraneous attribute and every left side is unique.

Algorithm

Fc = F
repeat
    // Combine using the union rule
    for each pair a1 -> b1 and a1 -> b2 in Fc:
        replace them with a1 -> b1 b2
    // Remove extraneous attributes
    find a dependency a -> b in Fc with an extraneous attribute
        either in a or in b
    if found, delete the extraneous attribute from a -> b
until Fc does not change

Each loop gives a set equivalent to $F$. Example: $F=\{A\rightarrow BC,\ B\rightarrow C,\ A\rightarrow B,\ AB\rightarrow C\}$. Union gives $A\rightarrow BC$. In $AB\rightarrow C$, $A$ is extraneous because $B \rightarrow C$, so it becomes $B\rightarrow C$. $C$ is extraneous in $A\rightarrow BC$ because $A\rightarrow B\rightarrow C$. So $F_c=\{A\rightarrow B,\ B\rightarrow C\}$.

Normalization is the process of decomposing relations to remove redundancy and undesirable dependencies, using functional dependencies and normal forms (1NF, 2NF, 3NF, BCNF). It is required because poorly designed relations suffer from anomalies:

Consider Emp_Dept(EmpID, EmpName, DeptID, DeptName) with $DeptID \rightarrow DeptName$.

• Redundancy: Sales is stored again for every employee of D1, wasting space.
• Update anomaly: changing the name of D1 needs many rows to be updated; missing one causes inconsistency.
• Insertion anomaly: a new department with no employee cannot be added without null EmpID (a primary key part).
• Deletion anomaly: deleting Hari (the only D2 employee) also deletes the fact that D2 is HR.

Decomposing into Employee(EmpID, EmpName, DeptID) and Department(DeptID, DeptName) removes these problems, with a lossless join and dependency preservation.

So normalization reduces redundancy, avoids anomalies, saves storage, improves integrity and keeps the design logically consistent.

Relational algebra is a procedural query language. It has a set of operators that take one or two relations as input and produce a new relation as output. Basic operators: select ($\sigma$), project ($\pi$), union ($\cup$), set difference ($-$), Cartesian product ($\times$) and rename ($\rho$). Others are derived, such as join and intersection.

i. Natural join ($\bowtie$). $r \bowtie s$ combines tuples of $r$ and $s$ that have equal values on all common attributes, and keeps one copy of each common attribute. It is defined as $r \bowtie s = \pi_{R \cup S}\big(\sigma_{r.A_1 = s.A_1 \wedge \dots \wedge r.A_n = s.A_n}(r \times s)\big)$ Example: Student(Roll, Name) $\bowtie$ Result(Roll, Marks) gives (Roll, Name, Marks) for matching rolls.

ii. Inserting a new record. Use union with a relation holding the new tuple: $r \leftarrow r \cup \{(101, \text{"Ram"}, 22)\}$

iii. Update of a record. Delete the old tuple using difference, then insert the changed one using union (or use the generalized projection): $r \leftarrow \pi_{Roll,\ Name,\ 23}\big(\sigma_{Roll=101}(r)\big) \cup \big(r - \sigma_{Roll=101}(r)\big)$ This changes the age of the student with Roll 101 to 23.

Fixed-length records. Every record in the file has the same size, for example Account(acc_no CHAR(10), branch CHAR(22), balance NUMERIC(8)) is 40 bytes each. Record $i$ starts at byte $n\times(i-1)$, so access is simple. Deletion leaves a gap which must be filled by moving records or by a free list linked from the file header. Space is wasted when values are shorter than the field size.

Variable-length records. Records of the same file differ in size, because of variable-length fields (VARCHAR), repeating fields or multiple record types. Each record stores an offset/length for variable fields and a null bitmap. They save space but are harder to locate, update and delete; the slotted-page structure is commonly used.

Sequential file organization. Records are stored in order, based on a search key (such as primary key), and are linked by pointers in search-key order.

• Good for processing the entire file and for range queries, as records are read in order.
• Reading a record by key can use binary search if the file is physically sorted.
• Insertion: find the position by key; if free space exists in the block, insert there, otherwise put the record in an overflow block and link it by pointer.
• Deletion: pointer chains are updated and the record's space is freed.
• The file needs periodic reorganization to restore physical order.
• Disadvantage: slow random access and costly insert/delete.

a.

SELECT name FROM Book
WHERE price > (SELECT AVG(price) FROM Book);

b.

SELECT A.Author_name FROM Author A
WHERE A.address = (SELECT address FROM Author WHERE Author_name = 'Hari');

c.

SELECT B.name FROM Book B, Writers W
WHERE B.book_id = W.book_id AND W.Author_ID = 7;

Relational algebra: $\pi_{name}\big(Book \bowtie \sigma_{Author\_ID=7}(Writers)\big)$

d.

SELECT name FROM Book
WHERE (price > 500 AND price < 1000) OR name LIKE 'M%';

e.

SELECT Author_name FROM Author
WHERE age < (SELECT MIN(age) FROM Author);

The result of (e) is always empty, because no age can be less than the minimum age of the same relation.

A canonical cover $F_c$ of a set of functional dependencies $F$ is a minimal set equivalent to $F$ (so $F_c^+ = F^+$) in which no dependency contains an extraneous attribute and each left side is unique. It is used to reduce the cost of checking dependencies during updates.

Three-tier architecture divides an application into three layers:

1. Presentation tier (client): the user interface, such as a browser or form.
2. Application (business logic) tier: processes requests, applies business rules and talks to the database.
3. Data tier: the database server that stores and manages the data.

The client never communicates directly with the database, which improves security, scalability and maintainability. Web applications commonly use it.

The closure of an attribute set $\alpha$ under a set of functional dependencies $F$, written $\alpha^+$, is the set of all attributes that are functionally determined by $\alpha$ using $F$. If $\alpha^+$ contains all attributes of the relation, $\alpha$ is a superkey.

NULL is a special marker meaning that the value of an attribute is unknown, missing or not applicable. It is not zero or an empty string. Comparisons with NULL give unknown, so IS NULL is used to test it. Primary key attributes cannot be NULL.

File organization is the way records of a file are arranged and stored on secondary storage (disk) so that they can be accessed efficiently. Common methods are heap (unordered), sequential, hash and indexed (clustering) file organization.

A partial dependency exists when a non-prime attribute depends on only part of a composite candidate key rather than on the whole key. Example: in Enrol(StudentID, CourseID, StudentName, Grade) with key (StudentID, CourseID), $StudentID \rightarrow StudentName$ is a partial dependency. It must be removed to reach 2NF.

A weak entity set can be made strong by adding to it attributes that form a primary key of its own (for example, a unique identifier). It then no longer depends on an owner entity set for identification and need not have an identifying relationship.

15 rows. The Cartesian product contains every pairing of a tuple of $r_1$ with a tuple of $r_2$, so $3 \times 5 = 15$.

Normalization is essential to remove data redundancy and avoid insertion, update and deletion anomalies. It saves storage, keeps data consistent and gives a logical, well-structured design by decomposing relations using functional dependencies.

A Database Management System (DBMS) is software that allows users to define, create, store, retrieve, update and control access to a database, while providing security, integrity, concurrency control and recovery. Examples: Oracle, MySQL, SQL Server.

Hiding low-level details. The DBMS uses data abstraction with three levels, so users are not exposed to how data is stored:

• Physical level: the lowest level, describing how data is actually stored (files, blocks, indexes, access paths). Hidden from almost everybody.
• Logical level: describes what data is stored and the relationships among the data (tables, attributes, constraints). Used by database administrators. Users do not see the physical structures.
• View level: the highest level, in which each user group sees only the part of the database it needs. Users cannot see the rest of the data, and complexity is hidden.

The DBMS keeps mappings between the levels. Because of these mappings, physical data independence and logical data independence are achieved, so users interact with the data through simple queries or forms without knowing about storage structures.

Constraints on generalization/specialization restrict which entities may belong to the lower-level entity sets.

1. Membership constraint
   • Condition-defined: membership is decided by a condition on an attribute. Example: in Employee, all entities with job_type = "manager" belong to Manager.
   • User-defined: the database user assigns entities to a lower-level set. Example: a project manager puts employees into work teams.
2. Disjointness constraint
   • Disjoint: an entity belongs to at most one lower-level set. Example: Account is either Savings or Current.
   • Overlapping: an entity may belong to several lower-level sets. Example: a person can be both Student and Employee.
3. Completeness constraint
   • Total: each higher-level entity must belong to some lower-level set. Example: every Account is Savings or Current.
   • Partial: a higher-level entity need not belong to any lower-level set. Example: an Employee may be neither Manager nor Clerk.

SQL (Structured Query Language) is the standard, declarative language for defining, manipulating and controlling data in a relational database. Its parts are DDL, DML, DCL and TCL.

SQL Data Definition Language (DDL) defines and changes the schema (structure) of the database. Main commands:

• CREATE creates tables, views and indexes:

CREATE TABLE Student (
    Roll INTEGER PRIMARY KEY,
    Name VARCHAR(30) NOT NULL,
    Age  INTEGER CHECK (Age > 15)
);

• ALTER changes an existing table:

ALTER TABLE Student ADD Address VARCHAR(40);
ALTER TABLE Student DROP COLUMN Age;

• DROP removes a table (with its data) or other object:

DROP TABLE Student;

• TRUNCATE removes all rows but keeps the table structure:

TRUNCATE TABLE Student;

DDL also covers constraints (PRIMARY KEY, FOREIGN KEY, UNIQUE, NOT NULL, CHECK, DEFAULT) and the creation of views (CREATE VIEW) and indexes (CREATE INDEX).

Extraneous attribute. An attribute in a functional dependency is extraneous if it can be removed without changing the closure of the set of dependencies. For $\alpha \rightarrow \beta$ in $F$, $A \in \alpha$ is extraneous if $(\alpha - A)^+$ under $F$ contains $\beta$. For example, in $AB \rightarrow C$ with $A \rightarrow C$ in $F$, $B$ is extraneous.

Algorithm to compute the closure of a set of functional dependencies $F^+$

F+ = F
repeat
    for each functional dependency f in F+
        apply reflexivity and augmentation rules on f
        add the resulting functional dependencies to F+
    for each pair of functional dependencies f1 and f2 in F+
        if f1 and f2 can be combined using transitivity
            add the resulting functional dependency to F+
until F+ does not change any further

The rules used are reflexivity (if $\beta \subseteq \alpha$ then $\alpha \rightarrow \beta$), augmentation (if $\alpha \rightarrow \beta$ then $\gamma\alpha \rightarrow \gamma\beta$) and transitivity (if $\alpha \rightarrow \beta$ and $\beta \rightarrow \gamma$ then $\alpha \rightarrow \gamma$).

Closure of an attribute set (which is the practical way to test a dependency):

result = alpha
repeat
    for each functional dependency b -> g in F
        if b is a subset of result
            result = result U g
until result does not change

$\alpha \rightarrow \beta$ holds in $F^+$ if and only if $\beta \subseteq \alpha^+$.

Integrity constraints guard against accidental damage to the database by ensuring that changes keep the data consistent.

1. Domain constraints: the value of each attribute must come from its domain (data type and allowed values). Example: Age INTEGER CHECK (Age > 20).
2. Entity integrity: no primary key attribute can be NULL, so every tuple is uniquely identifiable. Example: Roll in Student.
3. Referential integrity: a foreign key value must match an existing primary key value in the referenced relation, or be NULL. Example: Class.Roll must exist in Student.Roll. Deleting a referenced row needs ON DELETE CASCADE or similar actions.
4. Key constraints: every relation has a candidate key whose values are unique (UNIQUE, PRIMARY KEY).
5. NOT NULL constraint: the attribute cannot hold NULL.
6. Assertions and triggers: general conditions that the database must always satisfy, for example CREATE ASSERTION that the sum of loan amounts is below a limit.

CREATE TABLE Class (
    ClassNo INTEGER PRIMARY KEY,
    Roll    INTEGER NOT NULL,
    Strength INTEGER CHECK (Strength > 0),
    FOREIGN KEY (Roll) REFERENCES Student(Roll)
);

i.

INSERT INTO Personal_information
VALUES (1, 'Ram', 'Bahadur', 'Thapa', 'Male', 'Kathmandu', 'ram@mail.com', 9841000000);

ii.

UPDATE Personal_information SET phone = 4433881 WHERE person_id = 8;

iii.

DELETE FROM Dependent WHERE lName = 'xyz';

Relational algebra: $Dependent \leftarrow Dependent - \sigma_{lName='xyz'}(Dependent)$

iv.

SELECT DISTINCT P.fName, P.mName, P.lName
FROM Personal_information P, Dependent D
WHERE P.person_id = D.person_id AND D.relation = 'boy';

Here boy is taken as a dependent who is male, so the condition may also be written D.Gender = 'Male'.

v.

SELECT fName FROM Personal_information
WHERE Gender = 'Male' AND Address = 'aaa';

Relational algebra: $\pi_{fName}\big(\sigma_{Gender='Male' \wedge Address='aaa'}(Personal\_information)\big)$

Sequential file organization. Records are stored in sequence, ordered by a search key (often the primary key), and linked in key order by pointers.

• Efficient for processing the whole file and range queries.
• Insertion: locate the position by key; if free space exists in the block, insert there, otherwise put the record in an overflow block and link it with pointers.
• Deletion: pointer chains are updated and space freed.
• The file must be reorganized periodically to restore physical order.
• Weak for random access, insertion and deletion.

Fixed-length vs variable-length records

Example: fixed: Account(acc_no CHAR(10), branch CHAR(22), balance NUMERIC(8)), 40 bytes each. Variable: Account with a VARCHAR branch name, or a record with an array of owners that grows.

• Physical data independence: the ability to change the physical (internal) schema, such as file organization, indexes or storage devices, without changing the conceptual schema or application programs. It is easier to achieve.
• Logical data independence: the ability to change the conceptual schema, such as adding or removing attributes or entities, without changing external schemas or application programs. It is harder to achieve, because programs depend heavily on the logical structure.

The discriminator (partial key) of a weak entity set is the set of attributes that distinguishes the weak entities that depend on the same strong (owner) entity. The primary key of a weak entity set is the primary key of the owner entity set plus the discriminator. It is shown with a dashed underline in the E-R diagram.

A view is a virtual relation defined by a query over one or more base tables. It does not store data itself; its contents are computed when it is used. Views hide data, simplify queries and give security. It is created with CREATE VIEW v AS SELECT ....

In user-defined generalization/specialization, membership of an entity in a lower-level entity set is not decided by an explicit condition. The database user assigns each entity to a lower-level set manually, for example when adding the entity. Example: the manager assigns employees to work teams.

A super key is any set of attributes that uniquely identifies a tuple in a relation; it may contain redundant attributes (e.g. {roll, name}). A candidate key is a minimal super key, i.e. no proper subset of it is itself a super key (e.g. {roll}). Every candidate key is a super key, but not every super key is a candidate key.

The rename operator $\rho$ gives a new name to a relational-algebra expression result and, optionally, to its attributes. For example, $\rho_{x}(E)$ returns the result of expression $E$ under the name $x$, and $\rho_{x(A_1,A_2)}(E)$ also renames its attributes. It is needed to refer to the same relation twice in one expression (self-join) and to avoid name clashes.

A decomposition of relation $R$ into $R_1$ and $R_2$ is lossless when joining the parts gives back exactly $R$, with no spurious tuples. This holds if at least one of the following functional dependencies is in $F^+$:

$R_1 \cap R_2 \to R_1 \quad\text{or}\quad R_1 \cap R_2 \to R_2$

That is, the common attributes form a super key of $R_1$ or of $R_2$.

A distributed database system consists of a collection of logically related databases stored at multiple sites (computers) connected by a network. Each site is autonomous and can process local transactions, while the sites together can also process global transactions that access data at several sites, so users see it as a single database.

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

• Naive (parametric) users: unsophisticated users who interact through pre-written application programs and forms, e.g. a bank teller or a ticket-booking clerk.
• Application programmers: computer professionals who write application programs in languages such as Java or PHP, using embedded SQL or APIs to access the database.
• Sophisticated users: analysts and engineers who form requests directly in a query language such as SQL, or use data-analysis tools, without writing programs.
• Specialized users: write specialized database applications that do not fit traditional data processing, e.g. CAD systems, knowledge-based and expert systems, and multimedia applications.
• Database administrator (DBA): has central control of the system; defines schema and storage structure, grants authorization, performs backup and recovery, and tunes performance.

Entity sets and attributes

• CUSTOMER (<u>customer_id</u>, name, address, phone)
• CAR (<u>license_no</u>, model, year)
• ACCIDENT (<u>report_no</u>, date, location, damage_amount)

Relationship sets

• OWNS between CUSTOMER and CAR: one-to-many. A customer owns one or more cars (total participation of CUSTOMER), and each car is owned by one customer.
• INVOLVED_IN between CAR and ACCIDENT: one-to-many. A car has zero or more recorded accidents (partial participation of CAR), and each accident record belongs to one car.

E-R diagram

 [CUSTOMER]====1--<OWNS>--N----[CAR]----1--<INVOLVED_IN>--N----[ACCIDENT]
  |  |  |  |                    |  |  |                        |  |  |  |
 id name addr phone          license model year          report_no date location damage

CUSTOMER has total participation in OWNS (double line), CAR has partial participation in INVOLVED_IN (single line), and the underlined attributes (customer_id, license_no, report_no) are the primary keys. In the relational schema, OWNS is realised by putting customer_id as a foreign key in CAR, and INVOLVED_IN by putting license_no as a foreign key in ACCIDENT.

Domain constraint: the value of every attribute must come from the set of permitted values (its domain) and must be atomic. It is the most basic constraint, covering data type, range, format, NOT NULL and CHECK conditions. Example:

CREATE TABLE student (
  roll INT PRIMARY KEY,
  name VARCHAR(30) NOT NULL,
  age  INT CHECK (age BETWEEN 15 AND 60)
);

Referential integrity constraint: a value that appears in a foreign key of one relation must also appear as a primary (or candidate) key value in the referenced relation, or else be NULL. It keeps references between tables consistent: a student cannot be enrolled in a course that does not exist.

CREATE TABLE enrol (
  roll INT REFERENCES student(roll),
  cid  CHAR(5) REFERENCES course(cid)
);

Violations on insert or update are rejected; on delete of a referenced row the DBMS may reject it or cascade (ON DELETE CASCADE / SET NULL).

Anomalies are undesirable side effects that occur in a relation due to redundancy, which is caused by poor design (storing unrelated facts in one table). They are removed by normalization.

Consider EMP_DEPT(emp_id, emp_name, dept_id, dept_name, dept_location).

• Insertion anomaly: a fact cannot be inserted without another unrelated fact. A new department with no employees cannot be recorded because emp_id (the key) cannot be NULL.
• Deletion anomaly: deleting some data unintentionally loses other data. Deleting the last employee of a department also deletes the department's name and location.
• Update (modification) anomaly: the same fact is stored in many rows, so changing it in only some rows causes inconsistency. If a department's location changes, every employee row of that department must be updated; missing one leaves the data inconsistent.

Natural join $r \bowtie s$ combines tuples of $r$ and $s$ that have equal values on all attributes common to both relations, and the common attributes appear only once in the result. Formally, if $R \cap S=\{A_1,\dots,A_n\}$:

$r \bowtie s = \pi_{R\cup S}\left(\sigma_{r.A_1=s.A_1 \wedge \dots \wedge r.A_n=s.A_n}(r\times s)\right)$

Tuples with no match in the other relation are lost (dangling tuples). Outer joins keep them, padding with NULL.

• Left outer join $r \mathbin{⟕} s$: all tuples of the natural join, plus the tuples of $r$ that have no match in $s$, with the attributes of $s$ set to NULL.
• Right outer join $r \mathbin{⟖} s$: all tuples of the natural join, plus the tuples of $s$ that have no match in $r$, with the attributes of $r$ set to NULL.
• Full outer join $r \mathbin{⟗} s$: the natural join plus the unmatched tuples of both $r$ and $s$, each padded with NULLs; it is the union of the left and right outer joins.

Example: for $r(A,B)=\{(1,x),(2,y)\}$ and $s(B,C)=\{(x,p),(z,q)\}$, the natural join is $\{(1,x,p)\}$; left outer adds $(2,y,\text{NULL})$; right outer adds $(\text{NULL},z,q)$; full outer adds both.

A transaction must have the ACID properties so that the database stays correct despite concurrency and failures.

• Atomicity: all operations of a transaction are executed or none are. If it fails midway, its effects are rolled back. Handled by the recovery manager.
• Consistency: a transaction, run alone, takes the database from one consistent state to another, preserving all integrity constraints. Ensured by the programmer and the DBMS.
• Isolation: concurrent transactions do not see each other's intermediate results; the outcome is as if they ran serially. Handled by the concurrency control manager.
• Durability: once a transaction commits, its changes persist even after a system crash. Ensured by logging and recovery.

Example: transfer of Rs 500 from account A (balance Rs 2000) to B (balance Rs 1000).

read(A); A = A - 500; write(A);
read(B); B = B + 500; write(B);

• Atomicity: if the system crashes after write(A) but before write(B), the debit is undone, so no money vanishes.
• Consistency: A + B = Rs 3000 before and after.
• Isolation: another transaction reading A and B in between must not see A = 1500 and B = 1000 (total Rs 2500).
• Durability: after commit, A = 1500 and B = 1500 survive a crash.

Normalization is the process of decomposing relations to reduce redundancy and eliminate insertion, deletion and update anomalies, using functional dependencies and normal forms (1NF, 2NF, 3NF, BCNF). Decomposition should be lossless and preferably dependency preserving.

Given: STUDENT(name, grade, semester, program, roll, gender) with

$name \to semester,\quad roll \to program,\quad grade \to gender$

Candidate key: name, roll and grade never appear on the right side except as determinants, and the other attributes are all determined by them. Closure:

$\{name, roll, grade\}^+ = \{name, roll, grade, semester, program, gender\}$

so the key is $\{name, roll, grade\}$ (a composite key).

2NF: every non-key attribute must depend on the whole key. Here semester depends only on name, program only on roll and gender only on grade, so there are partial dependencies and the relation is not in 2NF. Remove them:

• R1(<u>name</u>, semester)
• R2(<u>roll</u>, program)
• R3(<u>grade</u>, gender)
• R4(<u>name, roll, grade</u>)

3NF: there must be no transitive dependency of a non-key attribute on the key. In R1, R2 and R3 the only non-key attribute depends directly on the key, and R4 has no non-key attribute. All determinants are keys of their relations, so no further decomposition is needed.

Final 3NF schema: R1(name, semester), R2(roll, program), R3(grade, gender), R4(name, roll, grade). The decomposition is lossless and dependency preserving.

i. Name of the member with maximum age

SELECT Name FROM Members
WHERE Age = (SELECT MAX(Age) FROM Members);

ii. Members who reserved both "DBMS" and "Database"

SELECT m.Name
FROM Members m
WHERE m.Member_id IN (SELECT r.Member_id FROM Reserve r, Books b
                      WHERE r.Bid = b.Bid AND b.Btitle = 'DBMS')
  AND m.Member_id IN (SELECT r.Member_id FROM Reserve r, Books b
                      WHERE r.Bid = b.Bid AND b.Btitle = 'Database');

iii. Increase the price of the "DBMS" book by 10%

UPDATE Books
SET Bprice = Bprice * 1.10
WHERE Btitle = 'DBMS';

iv. Authors and titles of books reserved on 27-May-2010

SELECT DISTINCT b.Bauthor, b.Btitle
FROM Books b, Reserve r
WHERE b.Bid = r.Bid AND r.Date = '2010-05-27';

v. Delete all books of publisher Bud Press

DELETE FROM Books
WHERE Bpublisher = 'Bud Press';

a. Number of doctors in each address

SELECT address, COUNT(*) AS no_of_doctors
FROM DOCTOR
GROUP BY address;

b. Delete the department where no one works

DELETE FROM DEPARTMENT
WHERE deptno NOT IN (SELECT deptno FROM WORKS);

c. Room of the doctor with maximum age

SELECT d.room
FROM DEPARTMENT d, WORKS w, DOCTOR dr
WHERE d.deptno = w.deptno AND w.name = dr.name
  AND dr.age = (SELECT MAX(age) FROM DOCTOR);

d. Deptno of doctors whose address neither starts with 'U' nor ends in 'U'

SELECT w.deptno
FROM WORKS w, DOCTOR dr
WHERE w.name = dr.name
  AND dr.address NOT LIKE 'U%'
  AND dr.address NOT LIKE '%U';

e. Increase by 1 the age of all doctors working on the top floor

UPDATE DOCTOR
SET age = age + 1
WHERE name IN (SELECT w.name
               FROM WORKS w, DEPARTMENT d
               WHERE w.deptno = d.deptno
                 AND d.floor = (SELECT MAX(floor) FROM DEPARTMENT));

The instance of a database is the collection of information stored in the database at a particular moment in time (a snapshot of the data). It changes as data are inserted, deleted or updated, whereas the schema (the overall design) stays the same.

The closure of a set of attributes $X$ under a set of functional dependencies $F$, written $X^+$, is the set of all attributes that are functionally determined by $X$, i.e. every $A$ such that $X \to A$ can be derived from $F$. For $F=\{A\to B, B\to C\}$, $A^+=\{A,B,C\}$.

The natural join $r \bowtie s$ of two relations is the join that combines tuples having equal values on all attributes with the same name in both relations, keeping each common attribute only once in the result. It is equal to a selection on equality of the common attributes over the Cartesian product $r \times s$, followed by a projection that removes the duplicate columns.

A NULL value is a special marker meaning that the value of an attribute is unknown, missing or not applicable. It is not the same as zero or an empty string. Any comparison with NULL (other than IS NULL / IS NOT NULL) evaluates to unknown, and aggregate functions such as SUM and AVG ignore NULLs.

A composite attribute is an attribute that can be divided into smaller sub-parts, each with an independent meaning. For example, the attribute name can be divided into first_name, middle_name and last_name, and address into street, city and district. Attributes that cannot be divided are called simple (atomic) attributes.

A parallel database system uses multiple processors and multiple disks working in parallel (connected by a high-speed interconnect) to execute database operations, so that data loading, scans, sorts, joins and queries run faster and more transactions per second can be handled. The architectures are shared-memory, shared-disk, shared-nothing and hierarchical. Its goals are higher throughput (speed-up) and scale-up with growing data and load.

A transaction is a logical unit of database work consisting of a sequence of read and write operations that must be executed as a whole, taking the database from one consistent state to another. It ends with either commit or abort (rollback), and must satisfy the ACID properties.

Two-phase locking (2PL) protocol ensures conflict-serializable schedules by requiring each transaction to issue lock and unlock requests in two phases:

1. Growing phase: the transaction may obtain locks (shared or exclusive) but may not release any lock.
2. Shrinking phase: the transaction may release locks but may not obtain any new lock.

The point at which the transaction obtains its last lock (the lock point) orders the transactions in the equivalent serial schedule.

Example:

T1: lock-X(A); read(A); write(A); lock-X(B); read(B); write(B); unlock(A); unlock(B)

Here all locks are acquired before the first unlock, so T1 is two-phase.

2PL guarantees serializability, but it does not prevent deadlock and may cause cascading rollback. Strict 2PL (hold all exclusive locks until commit) avoids cascading rollback, and rigorous 2PL holds all locks until commit.

The query processor is the part of the DBMS that translates user queries (SQL) into low-level instructions the storage manager can execute, and decides how to evaluate them efficiently.

Components:

• DDL interpreter: interprets DDL statements and records the definitions in the data dictionary (metadata).
• DML compiler: translates DML statements in a query language into an evaluation plan of low-level instructions. It also performs query optimization, choosing the lowest-cost plan among the alternatives (using statistics, indexes and cost estimation).
• Query evaluation engine: executes the low-level instructions generated by the DML compiler and returns the result.

In more detail, query processing goes through parsing and translation (checking syntax and converting to relational algebra), optimization (selecting the best evaluation plan) and evaluation (executing the plan).

Normalization is the process of organizing the attributes and relations of a database by decomposing them using functional dependencies, in order to minimize redundancy and avoid insertion, deletion and update anomalies.

Functional dependencies in CUSTOMER(CustomerID, CustomerName, SalesPerson, Region), from the data:

$CustomerID \to CustomerName, SalesPerson, Region$ $SalesPerson \to Region$

(Amrit is always South, Binita always West, and so on.)

Key: CustomerID is the only candidate key. The relation is in 1NF and 2NF (single-attribute key), but not in 3NF because Region depends on SalesPerson, a non-key attribute (transitive dependency CustomerID $\to$ SalesPerson $\to$ Region). It is also not in BCNF, since SalesPerson is a determinant but not a super key.

Decomposition into BCNF:

SALESPERSON(<u>SalesPerson</u>, Region)

CUSTOMER(<u>CustomerID</u>, CustomerName, SalesPerson)

In both relations every determinant is a candidate key, so they are in BCNF. The common attribute SalesPerson is the key of SALESPERSON, so the decomposition is lossless, and both dependencies are preserved.

Mapping cardinality (cardinality ratio) expresses the number of entities of one entity set that can be associated with entities of another through a relationship set. For a binary relationship between $A$ and $B$:

• One-to-one (1:1): an entity in $A$ is associated with at most one entity in $B$, and vice versa. Example: a person has one passport.
• One-to-many (1:N): an entity in $A$ can be associated with any number of entities in $B$, but an entity in $B$ is associated with at most one in $A$. Example: one department has many employees.
• Many-to-one (N:1): an entity in $A$ is associated with at most one entity in $B$, while an entity in $B$ can be associated with many in $A$. Example: many students belong to one college.
• Many-to-many (M:N): an entity in $A$ can be associated with any number of entities in $B$ and vice versa. Example: students enrol in many courses, and each course has many students.

A distributed database is a collection of logically interrelated databases spread over several sites connected by a network. Each site has its own local database and can run local transactions, and together the sites can run global transactions; to the user it appears as a single database.

Differences from a centralized database system

Entity sets and attributes

• CUSTOMER (<u>customer_id</u>, name, address, salary)
• ORDER (<u>order_no</u>, order_date)
• ITEM (<u>item_no</u>, description)
• DEPARTMENT (<u>dept_no</u>, dept_name)
• EMPLOYEE (<u>emp_id</u>, name, address, salary)
• SUPPLIER (<u>supplier_id</u>, name, address, phone, email)

Relationship sets

E-R diagram (textual)

[CUSTOMER]--1--<PLACES>--N--[ORDER]--M--<CONTAINS>(quantity)--N--[ITEM]--N--<SUPPLIES>(price)--M--[SUPPLIER]
                                                                   |
                                                                   N
                                                               <SOLD_IN>
                                                                   |
                                                                   1
[EMPLOYEE]--N--<WORKS_IN>--1--------------------------------[DEPARTMENT]

Entity sets are drawn as rectangles, relationships as diamonds, attributes as ellipses (the keys underlined). SUPPLIES carries the attribute price because an item is supplied by several suppliers at different prices, and CONTAINS carries quantity of the item in an order. Supplier contact details (address, phone, email) are kept as attributes of SUPPLIER.

i. Insert a new employee working for IBM, a company located in Darchula (the values of the employee tuple are assumed):

$Company \leftarrow Company \cup \{(\text{IBM},\text{Darchula})\}$ $Employee \leftarrow Employee \cup \{(\text{Ram},\text{Main Street},\text{Darchula},30)\}$ $Works \leftarrow Works \cup \{(\text{Ram},\text{IBM},3000)\}$

ii. Names and cities of employees who work for Deerwalk Company:

$\pi_{employee\_name,\,city}\left(Employee \bowtie \sigma_{company\_name=\text{"Deerwalk Company"}}(Works)\right)$

iii. Delete the records of employees whose salary is greater than 5000:

$Works \leftarrow Works - \sigma_{salary>5000}(Works)$

(To remove the employees completely, also delete their other tuples: $Employee \leftarrow Employee - \left(Employee \bowtie \sigma_{salary>5000}(Works)\right)$ projected onto the Employee attributes, and the same for Managers.)

iv. Increase the salary by 10% for those whose salary is less than 2000 (the salary is stored in Works):

$Works \leftarrow \pi_{employee\_name,\,company\_name,\,salary\times 1.1}\left(\sigma_{salary<2000}(Works)\right) \cup \sigma_{salary\ge 2000}(Works)$

v. Maximum salary of an employee:

$\mathcal{G}_{\max(salary)}(Works)$

The same result without aggregation: $\pi_{salary}(Works) - \pi_{Works.salary}\left(\sigma_{Works.salary<d.salary}(Works \times \rho_d(Works))\right)$.

a. Doctors whose salary is greater than the average salary

SELECT DoctorName
FROM Doctors
WHERE Salary > (SELECT AVG(Salary) FROM Doctors);

b. Remove the record of patient with PatientID = 44

DELETE FROM Patients
WHERE PatientID = 44;

c. Doctors who do not work in Teaching Hospital

SELECT DoctorName
FROM Doctors
WHERE DoctorID NOT IN (SELECT DoctorID FROM Hospitals
                       WHERE HostpitalName = 'Teaching Hospital');

d. Ids of patients admitted to a hospital of Biratnagar whose name has exactly 3 characters

SELECT h.PatientID
FROM Hospitals h, Patients p
WHERE h.PatientID = p.PatientID
  AND h.Location = 'Biratnagar'
  AND p."Patent Name" LIKE '___';

e. Increase the salary by 12% of doctors working in General Medicine

UPDATE Doctors
SET Salary = Salary * 1.12
WHERE Department = 'General Medicine';

A transaction is a unit of program execution that accesses and possibly updates data items, consisting of a sequence of read and write operations that form one logical unit of work. It either completes entirely (commit) or has no effect (abort), and must satisfy the ACID properties.

Normalization is required to remove data redundancy and the resulting insertion, deletion and update anomalies. It keeps the data consistent, saves storage space, and gives a logical, well-structured design in which each relation represents one kind of fact.

The concurrency control manager is responsible for controlling the interaction among concurrent transactions to ensure the isolation property and consistency of the database. Its responsibilities are:

• Granting and releasing locks (or timestamps) on data items, using a protocol such as two-phase locking.
• Ensuring that concurrent schedules are serializable.
• Detecting and resolving deadlocks, and preventing lost updates, dirty reads and unrepeatable reads.
• Making transactions wait, or aborting and restarting them when conflicts arise.

A transitive dependency exists in a relation when a non-key attribute depends on another non-key attribute rather than directly on the key. If $A \to B$ and $B \to C$ (with $B \not\to A$), then $C$ is transitively dependent on $A$ through $B$. For example, $roll \to dept$ and $dept \to hod$ imply $roll \to hod$ transitively. Such a dependency must be removed to reach 3NF.

Advantages of using a DBMS:

• Reduced data redundancy and inconsistency.
• Data sharing among multiple users and applications.
• Data independence (physical and logical) from application programs.
• Data integrity through constraints.
• Security through authorization and access control.
• Concurrent access with consistent results.
• Backup and recovery from failures.
• Efficient data access through indexing and query optimization.
• Standards enforcement and easier data administration.

A naive user is an unsophisticated end user who interacts with the system by invoking one of the permanent application programs already written for them, usually through forms and menus, without any knowledge of the DBMS or query languages. Examples are bank tellers, reservation clerks and online shoppers.

Computing the closure of an attribute set $X^+$ lets us:

• Test whether $X$ is a super key (if $X^+$ contains all attributes of the relation) and find candidate keys.
• Check whether a given functional dependency $X \to Y$ holds (it does if $Y \subseteq X^+$).
• Compute the closure $F^+$ of a set of dependencies and test equivalence or find a canonical cover, which helps in normalization and in checking that a decomposition preserves dependencies.

Reflexivity rule: if $Y \subseteq X$, then $X \to Y$. (Trivial dependencies always hold; for example $\{roll, name\} \to name$.)

The other rules are augmentation (if $X \to Y$ then $XZ \to YZ$) and transitivity (if $X \to Y$ and $Y \to Z$ then $X \to Z$).

A centralized database stores all data at a single site (one computer or server), and all users access it from there. A distributed database stores data across several sites connected by a network, but users see it as one logical database.

Application areas

• Centralized: small and medium organisations, a single-branch library, school or hospital information system, a single-shop billing system.
• Distributed: banks with many branches and ATMs, airline and railway reservation, multinational companies, telecom billing, and large e-commerce systems.

A constraint is a rule defined on the database that the data must satisfy at all times, so that the data stays correct and consistent. Examples are key, domain, referential integrity and cardinality constraints.

Mapping cardinality states the number of entities of one entity set that can be associated with entities of another set through a relationship set. The types are one-to-one (1:1), one-to-many (1:N), many-to-one (N:1) and many-to-many (M:N). For example, a department has many employees (1:N), while a student can enrol in many courses and a course has many students (M:N).

Domain constraint specifies the set of permitted values for an attribute, including its data type and any range or format. For example, age must be an integer between 0 and 120, and gender must be 'M' or 'F'. Any value outside the domain is rejected.

Total participation means that every entity in an entity set must take part in the relationship. It is shown by a double line in an E-R diagram. For example, if every employee must belong to some department, the participation of EMPLOYEE in WORKS_FOR is total. If some entities may not take part, the participation is partial.

The storage manager is the DBMS component that provides the interface between the low-level data stored on disk and the application programs and queries submitted to the system. It is responsible for storing, retrieving and updating data in the database.

Components of the storage manager

• Authorization and integrity manager: checks that users are allowed to access the data and that integrity constraints are satisfied.
• Transaction manager: ensures the database stays consistent despite failures and that concurrent transactions execute without conflict.
• File manager: manages disk space allocation and the data structures used to represent information on disk.
• Buffer manager: fetches data from disk into main memory and decides which data to keep in memory (cache). This lets the database hold more data than fits in memory.

Data structures it implements: data files (the database itself), the data dictionary (metadata) and indices for fast access.

The two-phase locking (2PL) protocol is a concurrency control protocol that ensures conflict-serializable schedules. Each transaction requests and releases locks in two separate phases.

1. Growing phase: the transaction may obtain locks (shared or exclusive) but may not release any lock.
2. Shrinking phase: the transaction may release locks but may not obtain any new lock.

The point at which the transaction obtains its last lock is called its lock point. Transactions can be serialized in the order of their lock points.

Example: T1 does lock-X(A), lock-X(B), reads and writes A and B, then unlock(A), unlock(B). All locks are taken before any is released, so it follows 2PL.

Variants: strict 2PL holds all exclusive locks until the transaction commits or aborts, which avoids cascading rollbacks. Rigorous 2PL holds all locks until commit.

Drawbacks: 2PL does not prevent deadlock, and without the strict version it may cause cascading rollbacks.

Entities and attributes

• PASSENGER: id (key, underlined), name (composite: first_name, last_name), phone (multi-valued, double ellipse), birth_date, age (derived from birth_date, dashed ellipse).
• AIRCRAFT: regno (key), name, capacity.
• ROUTE: number (key), distance.

Relationships

• TRAVELS_IN between PASSENGER and AIRCRAFT: many-to-one (N:1). Each passenger is assigned to at most one aircraft; one aircraft carries many passengers. PASSENGER participation is partial.
• FLIES_ON between AIRCRAFT and ROUTE: many-to-one (N:1). An aircraft travels on only one route; a route may have one or more aircraft. AIRCRAFT has total participation.

 [PASSENGER] N ---<TRAVELS_IN>--- 1 [AIRCRAFT] N ---<FLIES_ON>--- 1 [ROUTE]
   id, name(fname,lname),            regno, name, capacity          number, distance
   phone{multi}, birth_date, age(derived)

Relational mapping: PASSENGER(id, fname, lname, birth_date, aircraft_regno), PASSENGER_PHONE(id, phone), AIRCRAFT(regno, name, capacity, route_number), ROUTE(number, distance).

Anomalies are problems that arise from redundancy in a poorly designed relation.

• Insertion anomaly: a new fact cannot be stored without also storing unrelated data. For example, a new college cannot be recorded until a student is admitted to it.
• Update anomaly: the same fact is stored in many rows, so changing it requires updating all of them; missing one causes inconsistency. For example, a student's address changes but only some rows are updated.
• Deletion anomaly: deleting a row removes other useful facts. For example, deleting the only student of a college also deletes the college's phone number.

Normalization

Assumed dependencies: Roll identifies a student, so Roll → Name, Address. The key of the given relation is (Roll, Semester), and Roll, Semester → College, Phone, Admitted_Year (the admission details of that semester).

The relation is in 1NF (all values atomic). The candidate key is (Roll, Semester).

2NF: Name and Address depend only on part of the key (Roll), a partial dependency. Remove it:

• STUDENT(Roll, Name, Address)
• ADMISSION(Roll, Semester, College, Phone, Admitted_Year)

3NF: Under these dependencies no non-key attribute determines another non-key attribute in either relation, so there is no transitive dependency. The relations are already in 3NF:

Notation: $\sigma$ select, $\pi$ project, $\bowtie$ natural join, $\leftarrow$ assignment.

(i) Delete books with price greater than 400. (Deletion applies to Book; also to the dependent Publish tuples for consistency.)

$Publish \leftarrow Publish - \pi_{bid,pid,publish\_date}\big(Publish \bowtie \sigma_{price>400}(Book)\big)$ $Book \leftarrow Book - \sigma_{price>400}(Book)$

(ii) Name of the publisher that published "Data Structure using C++":

$\pi_{name}\big(Publisher \bowtie Publish \bowtie \sigma_{title='Data\ Structure\ using\ C++'}(Book)\big)$

(iii) Change the price of "Database Management System" to 800:

$Book \leftarrow \pi_{bid,title,author,page,800}\big(\sigma_{title='Database\ Management\ System'}(Book)\big) \cup \sigma_{title\neq'Database\ Management\ System'}(Book)$

Using the generalized projection (the constant 800 replaces the price attribute).

(iv) Insert the new information (publish_date is not given, so it is null):

$Book \leftarrow Book \cup \{(509,\ 'Data\ Communication',\ 'ABC',\ null,\ null)\}$ $Publisher \leftarrow Publisher \cup \{(238,\ 'pearson',\ null)\}$ $Publish \leftarrow Publish \cup \{(509,\ 238,\ null)\}$

(v) Price of all books:

$\pi_{title,\ price}(Book)$

(i) Names of passengers travelling in the bus "Agni Yatayat":

SELECT p.name
FROM Passenger p, Assign a, Bus b
WHERE p.pid = a.pid
  AND a.bid = b.bid
  AND b.name = 'Agni Yatayat';

(ii) Add attribute price to Route:

ALTER TABLE Route ADD price DECIMAL(10,2);

(iii) Delete passengers whose name ends with 'a':

DELETE FROM Assign WHERE pid IN (SELECT pid FROM Passenger WHERE name LIKE '%a');
DELETE FROM Passenger WHERE name LIKE '%a';

(The first statement removes dependent rows so that the foreign key is not violated.)

(iv) The question is incomplete ("Display the name bus"). It is taken as displaying the names of all buses:

SELECT name FROM Bus;

A database management system (DBMS) is software that allows users to define, create, store, retrieve, update and manage a database. It provides an interface between users or application programs and the data, and controls security, integrity, concurrency and recovery. Examples are MySQL, Oracle and SQL Server.

A primary key is a minimal set of one or more attributes chosen from the candidate keys of a relation that uniquely identifies each tuple. Its values must be unique and cannot be NULL. For example, roll_no in a Student relation.

A distributed database is a collection of logically related data that is physically stored at multiple sites connected by a computer network. Each site can process local transactions, and together the sites appear to the user as a single database.

Data independence is the ability to change the schema at one level of the database without changing the schema at the next higher level. It is of two types: physical data independence (changing the internal/storage schema without changing the conceptual schema) and logical data independence (changing the conceptual schema without changing external schemas or application programs).

First Normal Form (1NF): a relation is in 1NF if every attribute holds only atomic (indivisible) values; there are no multi-valued or composite attributes or repeating groups.

Example: STUDENT(Roll, Name, Phone) with Roll 1 having Phone {9841, 9851} violates 1NF. Making each value atomic gives rows (1, Ram, 9841) and (1, Ram, 9851), or a separate table STUDENT_PHONE(Roll, Phone).

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 candidate key (no partial dependency).

Example: ENROLL(Roll, Course_ID, Student_Name, Grade) with key (Roll, Course_ID). Here Roll → Student_Name is a partial dependency. Decompose into:

• STUDENT(Roll, Student_Name)
• ENROLL(Roll, Course_ID, Grade)

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

Mapping cardinality (cardinality ratio) is the number of entities to which another entity can be associated through a relationship set. For a binary relationship between A and B, there are four types.

1. One-to-one (1:1): an entity in A is associated with at most one entity in B and vice versa. Example: a person and a passport.
2. One-to-many (1:N): an entity in A can be associated with many entities in B, but each entity in B with at most one in A. Example: a department and its employees.
3. Many-to-one (N:1): many entities in A map to at most one in B. Example: many employees work for one department.
4. Many-to-many (M:N): entities in A may be associated with many in B and vice versa. Example: students and courses.

The closure $F^+$ of a set $F$ of functional dependencies is the set of all functional dependencies logically implied by $F$. It is computed by repeatedly applying Armstrong's axioms:

• Reflexivity: if $\beta \subseteq \alpha$, then $\alpha \to \beta$.
• Augmentation: if $\alpha \to \beta$, then $\gamma\alpha \to \gamma\beta$.
• Transitivity: if $\alpha \to \beta$ and $\beta \to \gamma$, then $\alpha \to \gamma$.

Algorithm

F+ = F
repeat
    for each functional dependency f in F+
        apply reflexivity and augmentation rules on f
        add the resulting functional dependencies to F+
    for each pair of functional dependencies f1 and f2 in F+
        if f1 and f2 can be combined using transitivity
            add the resulting functional dependency to F+
until F+ does not change any further

Union, decomposition and pseudotransitivity are derived rules that can be used to shorten the process. Since F+ may be exponentially large, in practice the attribute closure $\alpha^+$ is used to test whether a given dependency $\alpha \to \beta$ is in $F^+$.

The two-phase locking (2PL) protocol ensures serializability by requiring each transaction to issue lock and unlock requests in two phases.

1. Growing phase: the transaction may acquire locks (shared or exclusive), but cannot release any lock.
2. Shrinking phase: the transaction may release locks, but cannot acquire any new lock.

The point where the transaction gets its final lock is its lock point; transactions are serialized in lock-point order, so every schedule allowed by 2PL is conflict serializable.

Example:

T1: lock-S(A); read(A); lock-X(B); read(B); write(B); unlock(A); unlock(B)

The locks on A and B are taken first (growing) and released afterwards (shrinking).

Variants: strict 2PL keeps exclusive locks until commit or abort, preventing cascading rollback. Rigorous 2PL keeps all locks until commit.

Limitation: deadlock is possible, for example when T1 holds a lock on A and waits for B while T2 holds B and waits for A.

Entity sets and attributes

• COURSE: number (key), title, credits, syllabus.
• COURSE_OFFERING (weak entity, depends on COURSE): year, semester, section_no (together the partial key), timings, classroom. Its full key is course_number + year + semester + section_no.
• STUDENT: student_id (key), name, program.
• INSTRUCTOR: id (key), name, department, title.

Relationships

• HAS_OFFERING: COURSE (1) to COURSE_OFFERING (N), the identifying relationship of the weak entity; total participation of COURSE_OFFERING.
• PREREQUISITE: recursive relationship on COURSE (M:N); a course may have several prerequisites, with roles course and prerequisite.
• TAUGHT_BY: COURSE_OFFERING (M) to INSTRUCTOR (N), many-to-many since an offering may have several instructors.
• ENROLLED_IN: STUDENT (M) to COURSE_OFFERING (N), many-to-many.

[COURSE]--1--<HAS_OFFERING>==N==[[COURSE_OFFERING]]--M--<TAUGHT_BY>--N--[INSTRUCTOR]
   |  (M:N recursive: PREREQUISITE)      |
                                    N <ENROLLED_IN> M
                                         |
                                     [STUDENT]

Assumptions

• The course number is unique, and a course offering is identified only together with its course.
• A section of an offering has one timing and one classroom.
• A student may enrol in many offerings, and an instructor may teach many offerings.
• Syllabus is a single attribute (text or file); prerequisites are modelled as a relationship rather than an attribute.
• Each instructor belongs to one department.