Past exam of the computer science course of the University of Oxford / 2015 / Databases / 2

Find the salesperson identifiers satisfying each price condition using relational selection and relational projection:Intersect these identifier sets, relational join the result to the salesperson records, and apply relational projection to names:If intersection is not a primitive of the chosen relational algebra, use $L\cap H=L-(L-H)$ with relational difference. There is no need to access Car: the foreign key already ensures that every sale refers to a car.

Intersecting names instead of identifiers is wrong. Two different salespeople called Alex, one making only $10000$ sales and the other only $30000$ sales, would make Alex appear in both name sets although neither person satisfies the condition. Nor can one sale satisfy both price tests: the two distinct prices require distinct sale records.

A simple valid database query plan uses a block nested-loop join with the salesperson records on the outside, checking both sale conditions during the same inner scan. It avoids materializing the potentially much larger set of matching sale pairs.

Let $p\le SPT$ be the actual number of salesperson data pages and $k$ the number of outer data pages that fit along with the flags and working buffers. With the usual convention of $B-2$ outer pages, one inner input page and one output page, take $k=B-2$ for $B\ge 3$. If flag storage requires an extra reserved page, reduce $k$ accordingly. The number of outer records is at most $pSPR$, and there are $\lceil p/k\rceil$ outer blocks. Every such block requires a complete scan of the $ST$ sales data pages.

Count a database page read or write as one I/O. Conservatively charge $H_{SP}$ to locate the first salesperson leaf and $H_S$ to locate the start of each inner scan; this permits a small double charge if a definition of height includes a data leaf. The estimated read cost isIn the common convention that scan startup and cached internal pages are ignored, the usual upper estimate isFor an empty outer input there are no inner scans. This database query plan requires neither a sorted sale input nor a price index. In particular, the clustered database index on invoiceno cannot locate records by price. The quantities $TN$ and $THO$ describe the amount of qualifying data; they do not justify replacing a complete scan cost $ST$ by $TN+THO$. They can bound the retained work within each scan by roughly $(TN+THO)SR$ sale records, if those page counts describe packed qualifying records. Comparison cost against the outer block is CPU work rather than additional I/O.

Finally let $D_{\delta }$ be the extra I/O for eliminating repeated output names, including any temporary writes and reads, and let $w$ be the final result size in database pages if materialization is required. The total estimate isIf enough additional memory is available to retain all distinct qualifying names while producing the stream, then $D_{\delta }=0$. This extra memory is an additional assumption, separate from the $B$ join buffers. More generally, for $q$ pages of raw qualifying names, external merge sort gives $D_{\delta }=O\left(q\left[1+{\log }_{B-1}\max \{1,\lceil q/B\rceil \}\right]\right)$ for $B\ge 3$, including spooling. Names can be deduplicated during the merges. Counting this work matters because a database primary key on empid does not make names unique. No claim of optimality is needed for this database query plan.

Use fan-out four to mean at most four child pointers per internal node. A height increase requires a B+ tree node split at the root. Immediately after that B+ tree node split, the new root has exactly two children.

One further insertion follows one search path. Any chain of B+ tree node splits along that path can pass at most one additional separator and child pointer to the root. Its number of children therefore rises from two to at most three, below the maximum four. ThusThe argument includes an initially leaf-only B+ tree: its first root split likewise creates a root with two children. Even if the next insertion causes a child split immediately, the new root still has room. The conclusion assumes the standard insertion operation with one overflowing node split into two; it does not depend on whether height counts edges or levels.

A serial database schedule is obtained by running the three database transactions in the order $T_1,T_2,T_3$:A genuinely interleaved conflict-serializable database schedule with the same serial order isThe early $R_3(B)$ conflicts with nothing: all accesses to $B$ are reads. The conflicts on $A$ give edges $T_1\to T_2$, $T_1\to T_3$ and $T_2\to T_3$ in the database precedence graph, while the writes to $C$ give the already present edge $T_1\to T_2$. This database precedence graph has no directed cycle and admits the order $T_1,T_2,T_3$. Moving the early $R_3(B)$ after $R_2(B)$ swaps it only past non-conflicting operations, recovering the displayed serial database schedule.

For a database schedule that is not a conflict-serializable database schedule, takeOn $A$, $W_1(A)$ before $W_2(A)$ forces $T_1\to T_2$. On $C$, $W_2(C)$ before $W_1(C)$ forces $T_2\to T_1$. The resulting directed cycle prevents any serial ordering from preserving all conflicts. Each of the three displayed database schedules preserves the operation order inside every database transaction.