Databases

Every node of a B+ tree except the root must be at least half full: an internal node of order \(p\) needs at least \(\lceil p/2 \rceil\) children, and a leaf must fill about half of its key slots. This keeps the tree shallow and its space use predictable.

The root cannot always meet the rule. When the root splits, the new root starts with a single key and two children, and a small tree may hold fewer keys than half a node. So the root alone is exempt: it needs only two children, or a single key when it is also a leaf.

Leaves, internal nodes and the leftmost leaf get no such exception, so B, C and D are wrong.

Answer: A

First normal form asks only that every attribute hold atomic (indivisible) values, so a 1NF relation has no composite or multivalued attributes. It says nothing about keys.

• A: true. A key made of several attributes, such as (RollNo, CourseNo), is allowed; atomicity is about values, not keys.
• B: false. A relation in any normal form may have a foreign key referring to another relation.
• C: true. A composite attribute such as Address (street, city, PIN) is not atomic, so in 1NF it must be split into simple attributes.
• D: false. A relation can have several candidate keys, for example both RollNo and Email in a student table.

Answer: A, C

The join pairs each tuple of \(R\) with the tuples of \(S\) that have the same \(A\) value:

• \(A = 10\): \((10, 20)\) pairs with \((10, 90)\).
• \(A = 30\): \((30, 40)\) and \((30, 50)\) both pair with \((30, 45)\).
• \(A = 20\) and \(A = 50\) have no match in \(S\), and the \(S\) tuple with \(A = 40\) has no match in \(R\).

So the join has 3 tuples, whose \((B, C)\) values are \((20, 90)\), \((40, 45)\) and \((50, 45)\). The selection \(B \lt C\) keeps the first two and removes \((50, 45)\), leaving 2 tuples.

Answer: 2

• A is false. The left side of a dependency cannot just be shrunk. In a relation with the tuples \((X, Y, Z, W) = (0, 0, 0, 0)\) and \((0, 1, 1, 1)\), \((X, Y) \to (Z, W)\) holds because the tuples differ on \((X, Y)\), but \(X \to (Z, W)\) fails.
• B is true by decomposition: whatever determines \((Z, W)\) also determines \(Z\).
• C is true (pseudo-transitivity). Augmenting \(W \to Y\) with \(X\) gives \((X, W) \to (X, Y)\), and with \((X, Y) \to Z\) this yields \((X, W) \to Z\).
• D is true by transitivity, one of Armstrong’s axioms.

Answer: B, C, D

Two operations conflict when they come from different transactions, use the same item and at least one of them is a write.

• \(z\) is used only by \(T_{1}\) and \(x\) only by \(T_{2}\), so they cause no conflicts.
• On \(y\), both \(r_{3}(y)\) and \(w_{3}(y)\) come before \(r_{2}(y)\) and \(w_{2}(y)\). The conflicting pairs \(r_{3}(y)\)–\(w_{2}(y)\), \(w_{3}(y)\)–\(r_{2}(y)\) and \(w_{3}(y)\)–\(w_{2}(y)\) all order \(T_{3}\) before \(T_{2}\).

The precedence graph has the single edge \(T_{3} \to T_{2}\), and \(T_{1}\) is free. A serial schedule is conflict equivalent to \(S\) exactly when \(T_{3}\) comes before \(T_{2}\): \(T_{1}T_{3}T_{2}\), \(T_{3}T_{2}T_{1}\) and \(T_{3}T_{1}T_{2}\). Option A puts \(T_{2}\) first.

Answer: B, C, D

This is durability, the D in ACID: once a transaction has committed, its changes must survive any later failure. The DBMS ensures it by forcing the transaction's log records to stable storage before it reports the commit, so after a crash the recovery manager can redo committed changes that had not yet reached the data pages on disk.

• Atomicity is all-or-nothing execution: a transaction's changes are applied completely or not at all.
• Consistency means a transaction takes the database from one valid state to another.
• Isolation means concurrent transactions do not see each other's intermediate results.

Answer: A

A weak entity set has no key of its own. A weak entity is identified only by combining its partial key (discriminator) with the key of the owner entity it is linked to through the identifying relationship. A weak entity without an owner could not be identified at all, so every weak entity must take part in that relationship: the weak entity set has total participation.

The owner side has no such requirement. With Employee as the owner and Dependent as the weak entity set, for example, an employee may have no dependents. So the owner's participation can be partial, which rules out B and C, and D fails because the weak side must be total.

Answer: A

A scan retrieves every record of the file, so the best possible cost is to read each data page exactly once.

• Heap and sorted files keep their records packed in data pages, so a scan reads all \(B\) pages in sequence, one I/O per page. Both are I/O efficient.
• With an unclustered index, tree or hash, the records are reached through the index entries. The order of the entries has nothing to do with where the records sit on disk, so consecutive entries usually point to different pages. The scan then costs about one page I/O per record, plus the reads of the index itself, which is far more than \(B\) when a page holds many records.

Answer: A, B

Under 2PL each transaction has a growing phase, in which it may only acquire locks, followed by a shrinking phase, in which it may only release them.

• A is true. Every schedule that 2PL allows is conflict serializable, equivalent to running the transactions one after another in the order of their lock points.
• B is false. Releasing a lock right after each operation and then locking the next item mixes the two phases, which is exactly what 2PL forbids.
• C is true. This is the shrinking phase: after the first release, no new lock may be taken.
• D is true. If T1 holds a lock on X and waits for Y while T2 holds Y and waits for X, both wait forever; basic 2PL does nothing to prevent this.

Answer: A, C, D

With no grouping or counting, “at least 3 persons” has to be found as three tuples with the same city and pairwise different pids. Two cross products bring three renamed copies together:

\[\pi_{P_1.\mathit{city}}\big(\sigma_{C}(\rho_{P_1}(\mathit{Person}) \times \rho_{P_2}(\mathit{Person}) \times \rho_{P_3}(\mathit{Person}))\big)\]

where \(C\) requires equal cities and \(P_1.\mathit{pid} \ne P_2.\mathit{pid}\), \(P_1.\mathit{pid} \ne P_3.\mathit{pid}\), \(P_2.\mathit{pid} \ne P_3.\mathit{pid}\).

One cross product is not enough. An expression with at most one cross product builds each answer from at most two Person tuples. If it reported a city with three residents, it would also report that city for a relation holding only the two tuples it used, where that city has at most two residents.

Answer: B