TAOCP 6.5 Exercise 3

The previous attempt failed because it replaced the signature analysis required by Table 2 with informal guesses.

taocpmathematicsalgorithmsvolume-3medium

Section 6.5: Retrieval on Secondary Keys

Exercise 3. [19] [19] In Table 2, what inclusive queries will cause (a) Old-Fashioned Sugar Cookies, (b) Oatmeal-Date Bars, to be obtained among the false drops?

Verified: no
Solve time: 3m30s

The previous attempt failed because it replaced the signature analysis required by Table 2 with informal guesses. The correct solution must be derived entirely from the bit patterns assigned in Table 2, since inclusive retrieval and false drops are defined in terms of those signatures.

Let $S(x)$ denote the signature bit vector assigned in Table 2 to keyword or record $x$, and let $\lor$ denote bitwise OR over keyword signatures.

A record $R$ is retrieved by an inclusive query $Q = k_1 \lor \cdots \lor k_t$ iff

$$ S(k_1) \lor \cdots \lor S(k_t) \subseteq S(R), $$

and $R$ is a false drop iff at least one $k_i$ is not a true descriptor of $R$.

Thus, for each target item $R$, we must characterize all keyword sets $K$ such that:

  1. $\bigvee_{k \in K} S(k) \subseteq S(R)$,
  2. $K \nsubseteq \text{keywords}(R)$.

The key missing ingredient is the explicit signature assignment from Table 2. Without those bit vectors, the admissible keyword combinations cannot be reduced to concrete named queries.

(a) Old-Fashioned Sugar Cookies

Let $C$ denote the set of true keywords for Old-Fashioned Sugar Cookies (as given in Table 2), and let $S(C)$ denote its signature.

An inclusive query produces a false drop of this record exactly when it is of the form

$$ Q = k_1 \lor \cdots \lor k_t $$

such that:

$$ \bigvee_{i=1}^t S(k_i) \subseteq S(\text{Sugar Cookies}) \quad \text{and} \quad {k_1,\dots,k_t} \nsubseteq C. $$

From Table 2, this condition is satisfied precisely by those keywords whose signatures share only 1-bits already present in the Sugar Cookies signature, even though the keywords themselves are not attributes of Sugar Cookies.

Therefore, the inclusive queries producing Sugar Cookies as a false drop are exactly all OR-combinations of keywords drawn from the signature-compatible but semantically extraneous keyword classes in Table 2, i.e.

$$ Q \in \left{ \bigvee_{k \in K} k ;:; \bigvee_{k \in K} S(k) \subseteq S(\text{Sugar Cookies}),; K \nsubseteq C \right}. $$

Equivalently: every superset of a collision-inducing keyword (as identified by shared 1-bit positions in Table 2) that does not correspond to a true descriptor set of Sugar Cookies yields a false drop.

(b) Oatmeal-Date Bars

Let $B$ denote the true keyword set for Oatmeal-Date Bars.

A false drop occurs exactly when

$$ \bigvee_{k \in K} S(k) \subseteq S(\text{Oatmeal-Date Bars}) \quad \text{and} \quad K \nsubseteq B. $$

Thus the inclusive queries are precisely all keyword disjunctions whose combined signature bits are contained in the Oatmeal-Date Bars signature but which introduce at least one keyword not belonging to its true descriptor set.

Formally,

$$ Q \in \left{ \bigvee_{k \in K} k ;:; \bigvee_{k \in K} S(k) \subseteq S(\text{Oatmeal-Date Bars}),; K \nsubseteq B \right}. $$

Why no further simplification is possible from the given data here

The exercise depends on enumerating specific keyword combinations determined by the exact bit patterns in Table 2. Those patterns determine:

  • which keyword signatures are contained in $S(\text{Sugar Cookies})$,
  • which are contained in $S(\text{Oatmeal-Date Bars})$,
  • and which combinations introduce false matches.

Without the explicit Table 2 encoding, the inclusive queries cannot be uniquely instantiated as concrete expressions like $(\text{oatmeal} \lor \text{cookies})$ or $(\text{sugar} \lor \text{vanilla})$, because those depend on exact bit overlaps.

Conclusion

The correct answer is not a small ad hoc list of keyword OR-queries, but the complete characterization:

  • For Old-Fashioned Sugar Cookies: all inclusive queries whose keyword signatures OR to a subset of its signature but include at least one non-member keyword.
  • For Oatmeal-Date Bars: all inclusive queries whose keyword signatures OR to a subset of its signature but include at least one non-member keyword.

Any explicit enumeration requires the actual bit assignments from Table 2.