Databases Reference
In-Depth Information
Next, we must consider the case p < q. The additional constraint is
11−i
i + j + q−1
≥0.8
Again, consider each possible value of i.
i = 1: Then p = 9, so we require q≥10 and 10/(q + j)≥0.8. The possible
values of q and j are
1. q = 10; j = 1.
2. q = 10; j = 2.
3. q = 11; j = 1.
i = 2: Now, p = 10, so we require q≥11 and 9/(q + j + 1)≥0.8. there are no
solutions, since j must be a positive integer.
i = 3: As for i = 2, there are no solutions.
q
j = 1
j = 2
j = 3
7
x
8
x
x
i = 1
9
x
x
x
10
x
x
11
x
7
x
i = 2
8
x
x
9
x
i = 3
7
x
Figure 3.15: The buckets that must be examined to find possible matches for
the string s =
acdefghijk
with J = 0.8 are marked with an x
When we accumulate the possible combinations of i, j, and q, we see that
the set of index buckets in which we must look forms a pyramid. Figure 3.15
shows the buckets in which we must search. That is, we must look in those
buckets (x, j, q) such that the ith symbol of the string s is x, j is the position
associated with the bucket and q the su
x length.
2
3.9.7 Exercises for Section 3.9
Exercise 3.9.1 : Suppose our universal set is the lower-case letters, and the
order of elements is taken to be the vowels, in alphabetic order, followed by the
consonants in reverse alphabetic order. Represent the following sets as strings.
a{q, w, e, r, t, y}.
