theater_address(h, a) :-
    Movies(t, d, c),
    Pariscope(h, t, s),
    Location(h, a, p).

$t$ connects a movie to its showings, and $h$ connects a showing's theater to its address.

The atom reads $u$'s Title into $t$, its Director into $d$, and its Actor into $c$:

Then Pariscope(h, t, s) asks for the showings of filmA:

the two Champo showings.

From $P$, of course.

Hmm. The selection says which tuples to return. It does not say where they are. How does the computer find them?

• (Champo,filmA,18:00): yes
• (Champo,filmA,21:00): yes
• (Rialto,filmB,20:00): no

Three tests, two matches.

No. The second showing was still coming.

After the second yes, I would have lost nothing here. But I know that only because I tested the third tuple.

Yes. Every tuple it keeps passes the test, and it tests every tuple.

But with a million showings, that is a million tests for one movie.

It gives $\nu=\{t/\mathrm{filmA},\ d/\mathrm{Bergman},\ c/\mathrm{actor2}\}$: filmA again. We already found its showings, so we can skip this one.

actor1 gives two and actor3 gives one: three. But the first two atoms have five valuations, one for each tuple of $M\bowtie P$.

Oh. actor2 needs both showings too. I cannot skip the tuple. I only want to skip the search.

What is the second table? It holds the same showings, grouped by Title.

So when the second atom has $t$ bound, I look up $\nu(t)$. For actor2, I look up filmA and get both showings. No tests.

One showing: (Rialto,filmB,20:00).

And filmC? There is no filmC row.

Empty. So returning nothing is the right answer, not a failure.

Its filmA lookup returns one showing, but $\sigma_{\mathrm{Title}=\mathrm{filmA}}(P)$ has two. So actor1 gets one valuation instead of two.

theater_address still finds Champo through the 18:00 showing. But a query that also asked for the schedule would lose 21:00. No: a lookup must return every tuple with that Title.

Does a search key have to pick out one tuple, like a key of the relation?

Two tuples. So Title is a search key for this index, but not a key of Pariscope.

Nothing happens to either. $P$ still has three tuples, and the selection still has two. Only my work changes: I would scan again.

So the index is not part of $P$. It sits beside it.

No. Building it took one scan, and keeping it takes space. If a showing is added to Pariscope, the index must change too.

Then does every index keep its own copy of the tuples? That seems wasteful.

Row IDs 0 and 1. That is not a showing yet.

I still have to read the array at 0 and 1 to get (Champo,filmA,18:00) and (Champo,filmA,21:00).

Both indexes point into the same array. The showings are stored once.

It is a column in the table, so yes?

Now (Rialto,filmB,20:00) is at 0, and the filmA showings are at 1 and 2. Pariscope is still the same set of three showings.

So a row ID is not an attribute. It records where this array put a tuple. And both indexes are now wrong: they still point to the old places.

No fetch. The lookup already has Theater and Schedule, and the Title is the search key itself.

But this index copies the rest of every tuple, which is what I worried about. Which design is right?

So the design changes the work, not the answer.

For each Movies tuple, the first atom binds $t$. I look up $\nu(t)$, fetch each row, and extend $\nu$:

Five valuations, one for each tuple of $M\bowtie P$.

With the index: 3 lookups and 5 fetches, and no Title test on Pariscope. With scans: 3 scans of 3 tuples, so 9 tests.

Is 3 plus 5 less than 9?

A lookup, a fetch, and a test. Those are different operations.

Then I should not add them. The index made 3 lookups and 5 fetches; the scans made 9 tests.

$y$ was the dst of the first edge. So an index on dst, with search key Ogden.

edge(y, z). Here $y$ is in the first position, src. The second atom wants edges that start at Ogden.

So the index is on src, with search key $\nu(y)=\mathrm{Ogden}$. It returns row 2, (Ogden,SLC), and extends the valuation to $\nu\cup\{z/\mathrm{SLC}\}$.

The atom being matched. The position of $y$ in that atom names the stored attribute. The variable alone says nothing about columns.

Four lookups, two fetches, and two valuations, one through Ogden and one through Tremonton. Both give (Logan,SLC), so two_hop has one answer.

$\nu=\{a/\mathrm{Logan},\ b/\mathrm{Ogden}\}$, so the second atom is edge(Ogden, Logan). Both positions are known.

Nothing is left to find. I only ask whether (Ogden,Logan) is stored. It is not.

Nothing to look up with. I scan.

So the bound positions decide: none bound, scan; some bound, look up on their stored attributes; all bound, test one tuple.

Movies(t, d, c): nothing is bound, so scan.

Pariscope(h, t, s): $t$ is bound in the second position, so look up Pariscope on Title with $\nu(t)$.

Location(h, a, p): $h$ is bound in the first position, so look up Location on Theater with $\nu(h)$.

With the right indexes, only the first atom scans. Should every relation keep an index on every attribute, then?

Each atom has a constant in the Director position, so each looks up the index on Director. A scan would test 100 tuples for either query.

For bergman_films: 1 lookup and 2 fetches. For director_a_films: 1 lookup and 80 fetches. The lookup avoids the 100 tests, but I still fetch 80 tuples, one row ID at a time.

It depends on how many tuples match and where they sit. The index finds the group; it does not make the group smaller.

And every index has to be built and kept up to date, even for queries that never use it.

No. Only the index with one showing per Title did, and it did not return exactly the selection. The correct ones changed only the work: tests, lookups, fetches, space, and updates.

If it checked the search keys one by one, that would be a scan of the index. The index needs its own way to find an entry without checking every key.