15.6

Consider the bank database of Figure 15.14, where the primary keys are underlined. Suppose that a \(B^+\) -tree index on branch_city is available on relation branch, and that no other index is available. List different ways to handle the following selections that involve negation:

  1. \(\sigma_{\neg (branch\_city < "Brooklyn")}(branch)\)

  2. \(\sigma_{\neg (branch\_city = "Brooklyn")}(branch)\)

  3. \(\sigma_{\neg (branch\_city < "Brooklyn" \lor assets < 5000)}(branch)\)

  1. \(\sigma_{\neg (branch\_city < "Brooklyn")}(branch)\)

Use the index to locate the first tuple whose branch_city field has value “Brooklyn”. From this tuple, follow the pointer chains till the end, retrieving all the tuples.

  1. \(\sigma_{\neg (branch\_city = "Brooklyn")}(branch)\)

For this query, the index serves no purpose. We can scan the file sequentially and select all tuples whose branch_city field is anything other than “Brooklyn”.

  1. \(\sigma_{\neg (branch\_city < "Brooklyn" \lor assets < 5000)}(branch)\)

This query is equivalent to the query

\[ \sigma_{(branch\_city \geq "Brooklyn" \land assets \geq 5000)}(branch) \]

Using the branch_city index, we can retrieve all tuples with branch_city value greater than or equal to “Brooklyn” by following the pointer chains from the first “Brooklyn” tuple. We also apply the additional criteria of \(assets \geq 5000\) on every tuple.