GTU BE03000091 Database Management System Winter 2025 Solved Paper & Solutions

• Schema: the overall design (structure) of the database: the tables, columns, data types, keys and relationships. It is defined once and does not change often. Example: Student(RollNo, Name, Marks).
• Instance: the actual data stored in the database at one moment. It changes whenever data is inserted, updated or deleted. Example: the rows (1, Ravi, 70) and (2, Mita, 82) in Student today.
• Metadata: data about data, that is, the information that describes the database: table names, column names, data types, constraints and indexes. It is kept in the data dictionary (system catalog).

Advantages of a DBMS over a file processing system:

1. Less data redundancy: the data is stored once, so there are few duplicate copies.
2. Data consistency: as there is one copy, an update is seen everywhere.
3. Data integrity: constraints (keys, checks) keep the data valid.
4. Data security: access rights allow only authorized users.
5. Data sharing: many users and programs use the same data at the same time.
6. Data independence: programs are not affected if the storage structure changes.
7. Easy querying: SQL gives answers to new questions, with no new program.
8. Backup and recovery: the DBMS recovers the data after a failure.

Redundancy and consistency, in detail: in a file system, a student's address may be in the library file, the hostel file and the exam file. This wastes space, and when the student moves, each file must be changed. If one is missed, the files disagree. In a DBMS the address is stored once in the Student table, and other tables refer to the roll number. One update is enough.

Functions of the DBA

1. Schema definition: designs and creates the database structure (tables, indexes, views).
2. Storage structure and access methods: decides how the data is stored on the disk.
3. Granting access (security and authorization): creates user accounts and gives rights, so that only allowed users reach the data.
4. Backup and recovery: takes regular backups, and restores the data after a crash or a failure.
5. Performance tuning: monitors the system, adds indexes and changes the design to make queries fast.
6. Integrity maintenance: defines the constraints so that the data stays correct.
7. Schema modification: changes the structure when the needs change, with little effect on the users.
8. Monitoring users and capacity: watches the use, the disk space, and solves the problems of the users.

Decomposition means splitting a relation $R$ into two or more smaller relations, to remove redundancy in normalization. The decomposition is lossless (lossless join) if the original relation can be obtained back, without any lost or extra tuples, by joining the smaller relations.

For a split of $R$ into $R_1$ and $R_2$, the decomposition is lossless if

That is, the common attributes must be a key of at least one of the two relations. Example: Emp(EmpId, Name, DeptId) split into R1(EmpId, Name) and R2(EmpId, DeptId) is lossless, as EmpId is a key of both.

The natural join ($\bowtie$) joins two relations on all the attributes with the same name. It keeps the rows with equal values in the common attributes, and the common attribute appears only once in the result.

Example:

Student

Result

$Student \bowtie Result$ joins on the common attribute RollNo:

The rows of RollNo 3 and 4 have no match, so they are not in the result. The natural join is the same as an equi-join on the common column, followed by the removal of the repeated column.

Relational algebra is a procedural query language for the relational model. It has a set of operators that take one or two relations as input and give a new relation as the output. The basic operators are select ($\sigma$), project ($\pi$), union ($\cup$), set difference ($-$), Cartesian product ($\times$) and rename ($\rho$). The join ($\bowtie$) is derived from them. It is the base of SQL and of the query optimizer.

Schema: Branch(branch_name, branch_city), Account(branch_name, acc_no, balance), Depositor(Customer_name, acc_no).

Notes: relational algebra says how to get the result, step by step, while SQL says only what is wanted. A query is read from the inside out: first the join, then the selection, and last the projection. In (i), the natural join of Depositor and Account is on acc_no, as it is the only common attribute. In (ii), the join of Branch and Account is on branch_name, and then the join with Depositor is on acc_no.

Mapping cardinality says the number of entities of one set that can be related to entities of another set through a relationship, in an ER diagram.

1. One to one (1:1): one entity of A relates to at most one of B. Example: a person has one passport.
2. One to many (1:N): one entity of A relates to many of B, but each of B to only one of A. Example: one department has many employees.
3. Many to one (N:1): the reverse of 1:N.
4. Many to many (M:N): many of A relate to many of B. Example: students and courses.

Generalization is a bottom-up design process. Two or more lower level entities that have common attributes are combined into a higher level entity. Example: Student and Teacher both have Name and Address, so they are generalized into the entity Person. Specialization is the reverse.

Aggregation: an ER diagram cannot show a relationship between a relationship and an entity. In aggregation, a relationship (with its entities) is treated as one higher level entity (a box around it), so that it can take part in another relationship.

Example: Employee works on Project is a relationship. A Manager manages this whole "works on" relationship, since the manager supervises an employee on a project. So the box around Employee, works on and Project is an aggregate that joins the Manager through "manages".

DML (Data Manipulation Language) commands:

1. SELECT: retrieves data from a table.
2. INSERT: adds new rows.
3. UPDATE: changes the existing rows.
4. DELETE: removes rows.
5. Some systems also include MERGE and CALL, EXPLAIN PLAN and LOCK TABLE.

1. Names of the depositors whose branch name starts with 'S':

The LIKE 'S%' pattern matches any text that starts with S.

2. Employee names with a salary between Rs. 55000 and Rs. 85000, in the Finance department:

BETWEEN includes both end values. The join is needed because the department name is in the Department table.

3. Delete the borrower details whose amount is less than 10000:

ACID properties:

1. Atomicity: a transaction is done fully or not at all.
2. Consistency: a transaction takes the database from one valid state to another.
3. Isolation: concurrent transactions do not affect each other.
4. Durability: the result of a committed transaction is permanent.

Atomicity in detail: a transfer of Rs. 500 from A to B has two steps, debit A and credit B. If the system fails after the debit and before the credit, the money would be lost. So the DBMS undoes the debit (rollback) with the log, and the transfer is either complete or not done.

Normalization is the process of organizing the data in tables to reduce redundancy and to avoid the problems of insertion, update and deletion anomalies. It does this by splitting a big table into smaller related tables, using functional dependencies.

Why it is needed:

1. To remove duplicate data and save space.
2. To avoid anomalies: an update must be made at many places, a new fact cannot be inserted without another, and a delete may remove useful data.
3. To keep the data consistent and the design clear.

First Normal Form (1NF): a relation is in 1NF if every column holds only atomic (single) values, with no repeating groups or multivalued attributes.

Example: the table below is not in 1NF, as Phone has two values in a cell.

In 1NF, each phone number is a separate row:

Query processing is the series of steps taken by the DBMS to turn a high level query (SQL) into the result.

Basic steps:

1. Parsing and translation: the parser checks the syntax of the SQL and the semantics (the tables and columns exist, and the user has the rights). It then translates the query to an internal form, a relational algebra expression or a parse tree.
2. Optimization: one query can run in many ways, so the optimizer estimates the cost of the different plans and chooses the cheapest one. It uses statistics from the system catalog, such as the size of the tables and the indexes, and it applies rules such as doing selections early and using an index.
3. Evaluation (execution): the evaluation engine runs the chosen plan. It reads the data from the disk, with the help of the buffer manager, and gives the output to the user.

Example: SELECT name FROM student WHERE marks > 60 becomes $\pi_{name}(\sigma_{marks > 60}(student))$. The optimizer decides between a full table scan and an index scan on marks, and runs the cheaper one.

The cost is mainly the number of disk block transfers, since the disk is much slower than the CPU. The optimizer may also choose the join method (nested loop, sort-merge or hash join) and the join order, and it keeps the intermediate results small, since the earlier selections reduce the rows that are passed to the next step.

An ordered index is an index in which the index entries are stored in the sorted order of the search key value. Examples are the primary index and the B+ tree.

Primary advantage over an unordered index: because the entries are sorted, the database can use binary search or a tree, which makes the search fast. It also supports range queries (for example, marks between 50 and 70) and sorted output efficiently, as the neighbouring values are next to each other. An unordered (hash) index supports only equality search.

Audit trail: an audit trail is a log that records the actions of the users in the database: who accessed or changed which data, when, and from where (insert, update, delete, login attempts). It is used to detect misuse and unauthorized access, to find the person responsible for a change, to fix a security breach and to meet legal rules. It also acts as a deterrent, as users know that they are watched.

A B+ tree is a balanced multi-level tree index in which:

• All the data pointers are in the leaf nodes, and the internal nodes only guide the search with keys.
• All the leaves are at the same level, and they are linked in order, which makes a range scan fast.
• With $n = 4$, a node has at most 4 pointers and 3 keys, and at least $\lceil n/2 \rceil = 2$ pointers.

Given tree: root [20, 30]. The leaves are [5, 10, 15], [21, 22, 24] and [35, 40, 45].

Insert 25:

Tree after the insertion:

The leaves are also linked to each other from left to right (not drawn), which makes a range scan fast. The key 24 is in the parent and also in the leaf [24, 25], as in a B+ tree the leaf keeps every key.

Check: every leaf has 2 or 3 keys, and the root has 3 keys and 4 children, which is allowed for $n = 4$. A search for 25 now goes root, since $24 \le 25 < 30$ gives the third child, [24, 25].