Draft
The Picture That Did Not Choose
Conversation 2.2 — Sideways Information Passing
The picture that did not choose
Representing dependencies as a graph is a common technique in computer science. Let us use it to record the connections we found in 2.1:
eligible(driver, job) :-
based_at(driver, depot),
stocks(depot, item),
needs(job, item).We will give each body occurrence a vertex. Call these three $D$, $S$, and $N$. The head tells us what to return; it adds no body constraint, so it gets no vertex here.
Here are the vertices.
I want to know which two to join first. Is that what the edges will tell me?
Let us first draw the agreements required by the rule. $D$ and $S$ share depot, so connect their vertices and label the edge with the variable their tuples must agree on.
Then I can add the item edge between $S$ and $N$.
There is no variable to put on an edge from $D$ to $N$. That was our Cartesian product.
They are connected through $S$, which tests whether the depot stocks the item.
So the missing edge does not forbid me from combining $D$ and $N$ first. I would just be postponing the stock check, as we did in 2.1.
You could. Write the same condition with needs before stocks:
eligible(driver, job) :-
based_at(driver, depot),
needs(job, item),
stocks(depot, item).Keep the labels $D,S,N$ with their original atoms.
Nothing in the picture needs to move.
$D$ and $N$ are next to each other in the rule now, but they still share no variable. The required agreements have not changed.
Nor have the answers. Notice that our edges have no arrows. If $D$ must agree with $S$ on depot, then $S$ must agree with $D$ on depot.
That condition is symmetric, so we use an undirected graph.
So the line does not tell me to go from $D$ to $S$. I can start from either side and still have to make their depot values agree.
Try the same edge rule when all three body occurrences use road. Here are three roads from a common origin:
shared_origin(a, b, c) :-
road(h, a),
road(h, b),
road(h, c).Call these separate uses of road $E_1,E_2,E_3$, in written order.
$E_1$ and $E_2$ share h. So do $E_2$ and $E_3$—and $E_1$ and $E_3$. I need all three edges.
Now replace h in just the third atom:
road_choices(a, b, c) :-
road(h, a),
road(h, b),
road(other, c).Which edges would you erase?
Both edges touching $E_3$. Its variables are now other,c, and neither occurs in the first two atoms. The edge between $E_1$ and $E_2$ stays.
They all still read road, though. The separation comes from how the query uses it.
The third origin might happen to equal h, but the query no longer requires it. Joining $E_3$ with $E_1\bowtie E_2$ is a Cartesian step.
This is the sideways information-passing (SIP) graph: one vertex per relational body occurrence, with an undirected edge between two distinct vertices exactly when their atoms share a variable.
Why is it called “sideways information passing”?
Here, “sideways” refers to information passing between atoms in the same rule body. A match at one atom can narrow what we look for at another. Think of our delivery query:
eligible(driver, job) :-
based_at(driver, depot),
stocks(depot, item),
needs(job, item).Take (job1,bolt) from $N$. Its item is already known. What must a matching stock tuple contain?
bolt in its item column. I can use the value from $N$ to narrow the stock choices in $S$.
Right. The graph records where that information can pass. How much it narrows the choices depends on the tuples.
Recall the two orders for eligible in 2.1. All three inputs had three tuples. $D\bowtie S$ produced five, while $S\bowtie N$ produced three.
Then those counts were not in the picture. But the two joins check different variables. How does checking item earlier save work in the join on depot?
Let us follow one stock tuple. Here are $S$ and $N$ from that instance:
stocks
| depot | item |
|---|---|
| north | bolt |
| north | screw |
| south | nut |
needs
| job | item |
|---|---|
| job1 | bolt |
| job2 | bolt |
| job3 | nut |
Which stock tuple has no matching job?
(north,screw). No job needs a screw.
So north is gone?
(north,bolt) still has matching jobs. What did we actually remove?
Just (north,screw), one stock choice at north.
Yes. needs inspected the item, but rejected the whole stock tuple. Before that check, which drivers would have matched it?
| driver | depot |
|---|---|
| Lin | north |
| Moe | north |
| Nia | south |
Lin and Moe. We would have constructed both of these:
| driver | depot | item |
|---|---|---|
| Lin | north | screw |
| Moe | north | screw |
Removing that stock choice first avoids these two wasted tuples.
stocks admits particular depot–item pairs. Removing a pair changes the choices available to the driver join.
The edges record agreement across atoms on the same variable. The association between the different variables depot and item is inside $S$.
$D$ never sees item, but the item check can still leave it fewer stock tuples to match. Can we make the connection inside $S$ visible too?