Draft
The Variables the Plan Still Needed
Conversation 2.4 — Matching, Forgetting, and Filtering
The variables the plan still needed
Let us follow the columns through a plan. Return to our delivery query, without the day:
eligible(driver, job) :-
based_at(driver, depot),
stocks(depot, item),
needs(job, item).Call the body occurrences $D,S,N$ as before.
Start with $D$, then join $S$. Which variable must match? Which is new?
depot must match. item is new.
The result has driver,depot,item.
Instead start with $D\times N$, then join $S$. Same query, same stock atom. What must $S$ check now?
Now both depot and item are already present. $S$ must match them together and adds no new column.
Suppose a product candidate is
| driver | depot | job | item |
|---|---|---|---|
| Lin | north | job3 | nut |
and $S$ contains only
| depot | item |
|---|---|
| north | bolt |
| south | nut |
Does the candidate survive?
No. Neither stock tuple matches the whole pair (north,nut).
Both values must come from one tuple, as with the dated stock in 2.3.
A join can extend a candidate or only filter it. Which it does depends on the columns already present.
So $S$ did not change; the partial result did. Could $S$ have to match three columns?
Yes—even when the columns came from different atoms. Here, available(driver,day) records a driver's available days:
ready_on(driver, job, day) :-
based_at(driver, depot),
needs(job, item),
available(driver, day),
stocks_on(depot, item, day).Use $A$ for available and $D,N,S$ for the other occurrences. Combine the first three. What must the final stock atom match? What can it add?
It matches the entire set {depot,item,day} and adds nothing.
depot arrived through based_at, item through needs, and day through available.
Suppose those earlier atoms produced
| driver | depot | job | item | day |
|---|---|---|---|---|
| Lin | north | job1 | bolt | Tue |
Use the dated stock rows from 2.3:
| depot | item | day |
|---|---|---|
| north | bolt | Mon |
| north | nut | Tue |
| south | bolt | Tue |
Keep or discard this candidate?
Discard it. The required triple (north,bolt,Tue) is absent.
The pairwise witnesses still do not supply one matching stock tuple.
Return to the query without the day or availability test:
eligible(driver, job) :-
based_at(driver, depot),
stocks(depot, item),
needs(job, item).We have computed $D\bowtie S$, with columns driver,depot,item. Only $N$ remains.
Who still needs item? Who still needs driver?
$N$ needs item to check the job's requirement. The head needs driver to report the answer.
Who still needs depot?
Neither the remaining atom nor the head.
The join has already checked the depot connection. We can keep just driver,item.
Would this work even if two depots connected the same driver and item?
| driver | depot | item |
|---|---|---|
| Lin | north | bolt |
| Lin | south | bolt |
What does projection onto driver,item return?
One tuple, (Lin,bolt), under set semantics.
$N$ can inspect only the item, and the head returns only driver and job. Two depot witnesses would not create two distinct answers.
Then why not discard depot immediately after reading $D$? Use this small instance of the same query:
| $D$: driver | depot |
|---|---|
| Lin | north |
| $S$: depot | item |
|---|---|
| south | nut |
| $N$: job | item |
|---|---|
| job3 | nut |
First, what is the correct answer?
Empty. Lin's depot is north, but the only stock tuple is at south. The $D$–$S$ match fails.
Now replace $D$ by $\pi_{driver}(D)$ before joining $S$. What happens?
The depot column that carried the required agreement is gone. driver and depot,item have no shared column, so the first combination admits (Lin,south,nut).
Joining $N$ then produces the false answer (Lin,job3).
We could discard depot after its last test, but not before that test.
After the valid $D\bowtie S$ step, could we discard driver too? No remaining body atom uses it.
The head still does. If we discard it, we cannot report which driver can do the job.
So the head counts as a remaining use too.
Yes. Suppose a completed part of the body is $C$. Who might still need one of its variables?
An unprocessed atom, the head, or a condition we have not tested yet.
Check the other starting pair in eligible: complete $S\bowtie N$ first. It has depot,item,job. What can disappear?
item. The remaining $D$ needs depot, and the head needs job. Keep {depot,job}.
Return once more to ready_on. Its final stock atom has just checked all three shared columns. What does the completed body retain for the head?
driver,job,day. Both depot and item can now disappear.
The stock test needed them; the head does not.
Does discarding an intermediate column erase its variable from the original query graph?
No. Its constraints stay in the query. The intermediate carries fewer columns because some tests are finished.
How much does that save in a plan?
Let us measure the effect. Use the first instance from 2.1 again:
| $D$: driver | depot |
|---|---|
| Lin | north |
| Moe | north |
| Nia | south |
| Omar | south |
| $S$: depot | item |
|---|---|
| north | bolt |
| south | nut |
| $N$: job | item |
|---|---|
| job1 | bolt |
| job2 | bolt |
| job3 | nut |
| job4 | nut |
Starting with $D\bowtie S$, how many rows and columns do we get before and after the safe projection?
Before: four rows and three columns. After: four rows and two columns.
The four driver–item pairs are distinct, so this projection reduces columns without reducing rows.
| driver | item |
|---|---|
| Lin | bolt |
| Moe | bolt |
| Nia | nut |
| Omar | nut |
Continue that plan through $N$, then project to the head. Annotate every step with both its row count and its schema.
Each driver–item pair matches two jobs.
Try product first. After $D\times N$, may we discard either depot or item before joining $S$?
No. $S$ still needs both, while the head needs driver,job. All four columns must stay.
Count columns immediately after each displayed join or projection. What is the largest intermediate arity in each plan?
Three in the driver-first plan, four in the product-first plan.
Without early projection, the complete body would have all four columns in both orders. The measurement depends on where the projections occur.
Now keep only answers whose job is job1. Keep the same head columns driver,job.
Apply $N'=\sigma_{job=job1}(N)$. What changed: rows, columns, or both?
Rows. $N'$ contains just (job1,bolt), but still has the two columns job,item.
The selected relation has the same schema.
The condition uses only job, which is already available in $N$. A rejected $N$ tuple could not contribute to a selected answer, so we can test it here.
What does $S\bowtie N'$ contain?
One tuple:
| depot | item | job |
|---|---|---|
| north | bolt | job1 |
Which column can disappear now? Then how many drivers match?
Discard item, keeping depot,job. $D$ matches Lin and Moe at north, giving the two answers (Lin,job1) and (Moe,job1).
Could a semijoin communicate the same restriction to the stock input? Compute $S\ltimes N'$. What is its schema?
It keeps the stock tuples having a partner in $N'$:
| depot | item |
|---|---|
| north | bolt |
The schema is still $S$'s depot,item. The semijoin filters the left relation; it does not bring job into it.
Use unrestricted $N$ again. North's bolt matches two jobs. How many copies of (north,bolt) does $S\ltimes N$ contain?
One. Existence of a partner is enough. In this instance $S\ltimes N$ has two stock tuples, whereas $S\bowtie N$ has four depot–item–job tuples.
If we need the jobs, the semijoin alone does not provide them.
We have reduced columns with projection and rows with filtering. What did your three-versus-four comparison measure?
Columns in the intermediate results. Selecting job1 reduced rows instead. We should name those quantities separately.
Does selecting job1 change the variable groups in our query hypergraph?
No. It changes which tuples pass, while the variables and overlaps stay the same. What if we write a constant inside an atom instead?
Then that occurrence is restricted by the constant. Try:
from_logan(to) :-
road("Logan", via),
road(via, to).Use the SIP convention from 2.2: mark a vertex containing a constant with a small filled dot. Call the occurrences $E_1,E_2$.
The first vertex is marked. The shared variable is still via.
The literal selects tuples of the first occurrence. It is not a query-variable vertex when we open the atoms into a hypergraph.
We can now match a whole shared set, filter tuples, and retain only needed columns. Is every surviving tuple therefore part of a complete answer?
Not yet. We have checked the constraints processed so far. A remaining constraint can still reject it.
But what if it has a partner in every other atom? Would that be enough?