By Indirections Find Directions Out

Conversation 1.2 — From Ground Claims to Query Images

Modern Query ProcessingFall 2026

By indirections find directions out

Ada · 01

In the instance I above, is this statement true?

road("Logan", "Salt Lake City")
Alice

Yes. It is a membership check against I(road).

Ada · 02
road("Logan", "Provo")
Alice

False. The statement asks for one tuple in I(road). It does not ask whether Provo can be reached by following several stored roads. Under the closed-world assumption, the absent tuple gives us a negative answer.

Ada · 03

Consider another database instance J. It agrees with I on road_length; only its road relation changes:

J(road) = {
    ("Logan", "Salt Lake City"),
    ("Logan", "Garden City"),
    ("Garden City", "Logan"),
    ("Salt Lake City", "Provo"),
    ("Logan", "Provo")
}

Is road("Logan", "Provo") true in J?

Alice

Yes. We kept the statement fixed and changed the instance in which we tested it.

Ada · 04
road("Logan", to)
Alice

What is to? This seems to do more than evaluate a membership predicate.

Ada · 05

It is a relational atom. Here, to is a logical variable: it represents a not-yet-identified value in our known closed world. The first argument is the known value "Logan"; we say that this argument is ground.

Alice

Okay. This seems complicated, but useful. It looks like an intuitive way to represent “all cities to for which Logan has a road to to.”

Ada · 06

Then give me all values of to such that Logan has a road to to in instance J.

Alice
{"Salt Lake City", "Garden City", "Provo"}
Ada · 07

The Garden City answer produced this ground atom:

road("Logan", "Garden City")

Database researchers compress that claim to

$$J \models road(\text{"Logan"}, \text{"Garden City"}). $$
Alice

So \(\models\) says that this ground atom is true in J.

Ada · 08

Now let to name Ogden, what changes?

Alice

The assignment produces road("Logan", "Ogden"), which is false in J because its tuple is absent from J(road). .

Ada · 09

We call this assignment a valuation, written:

to -> "Ogden"
Alice

Another term! Database researchers love strange terms.

Ada · 10
road("Logan", via),
road(via, "Provo")

These two atoms share the logical variable via. What does that mean?

Alice

I does not contain a direct road from Logan to Provo. Yet its stored roads lead there through Salt Lake City. This expression is meant to find that indirect route.

Ada · 11

Try this valuation in I:

via -> "Salt Lake City"

Are both atoms true _at the same time_?

Alice

Yes. They become

road("Logan", "Salt Lake City"),
road("Salt Lake City", "Provo")

Both tuples belong to I(road) at the same time. So the comma appears to mean “and.”

Ada · 12

Now test the same two atoms in J with

via -> "Garden City"

Are both atoms true _at the same time_?

Alice

No. road("Logan", "Garden City") is true in J, but road("Garden City", "Provo") is false there.

Ada · 13

Have we written a query yet?

Alice

Not yet. We know when this conjunction is true under one valuation, but we have not said which values should become an answer relation.

Recap

What the database can make true

For a relational atom $r(t_1,\ldots,t_n)$ and a valuation $v$, satisfaction is tuple membership after applying the valuation:

$$I\models r(t_1,\ldots,t_n)[v] \quad\text{exactly when}\quad v(t_1,\ldots,t_n)\in I(r). $$

A valuation $v$ assigns each logical variable one value of the required type, consistently across all its occurrences; it leaves data literals unchanged. For a ground atom, no valuation needs to be written. If a tuple is absent from $I(r)$, the corresponding ground atom is false in the fixed instance $I$. When a positive theory $\Sigma$ describes a database, the closed-world assumption additionally permits failure to prove $r(\vec a)$ from $\Sigma$ to license inferring $\neg r(\vec a)$. It does not establish falsity in the physical world.

For relational atoms $A_1,\ldots,A_m$, one valuation must make every atom in a conjunction true at the same time:

$$I \models (A_1 \land \cdots \land A_m)[v] \quad\text{exactly when}\quad I \models A_i[v]\text{ for every }i. $$

This tells us whether the conjunction succeeds. It does not yet say which values an answer should retain.

Ada · 14

We ended with this conjunction:

road("Logan", via),
road(via, "Provo")

It fixes the two endpoints. How could the same two-road pattern range over every possible pair?

Alice

I can replace the two fixed city names with logical variables:

road(from, via),
road(via, to)

Now a valuation chooses all three cities. The conjunction succeeds when both atoms are true in the input instance under that one valuation.

Ada · 15

Use the relevant part of the same input instance:

J(road) = {
    ("Logan", "Salt Lake City"),
    ("Logan", "Garden City"),
    ("Garden City", "Logan"),
    ("Salt Lake City", "Provo"),
    ("Logan", "Provo")
}

Which ordered pairs of cities are connected by two roads in J?

Alice
{
    ("Logan", "Provo"),                   // via Salt Lake City
    ("Logan", "Logan"),                   // via Garden City
    ("Garden City", "Salt Lake City"),   // via Logan
    ("Garden City", "Garden City"),      // via Logan
    ("Garden City", "Provo")             // via Logan
}
Ada · 16

How do we store these routes in the database?

Alice
relation two_hop(from: City, to: City);

But we cannot simply assign an arbitrary relation instance to it. If I write

J(two_hop) = {
    ...,
    ("Provo", "Apple")
}

then two_hop no longer means “cities connected by two stored roads.” Its name has lost its meaning.

Ada · 17

The trick is that we do not supply J(two_hop) as part of database instance J. Instead, we let it be determined by J(road). We write

two_hop(from, to) :-
    road(from, via),
    road(via, to).
Alice

What does :- mean?

Ada · 18

Read :- as “if”:

two_hop(from, to) if
    road(from, via) and
    road(via, to)
Alice

I understand the condition after “if”: one road goes from from to via, and another goes from that same via to to.

But what does two_hop(from, to) do before :-?

Ada · 19

Whenever one valuation makes both road atoms true, the values assigned to from and to form a tuple in the answer relation named two_hop.

We call two_hop(from, to) the head of the rule and the conjunction after :- its body.

Alice

So via helps the body succeed, but it does not appear in the answer tuple.

Ada · 20

Exactly. The body determines which valuations succeed; the head determines which values they contribute to the answer, and in what order.

Now try this head:

two_hop(from, destination)
Alice

That cannot work. The body never assigns a value to destination, so it cannot produce the requested answer tuple.

Every variable in the head must also occur in the body.

Ada · 21

Exactly. The head asked for a value that the body could never supply. We can detect that mistake by reading the rule, before looking at any database instance.

This is the rule's safety guard: every variable requested by the head must be supplied by the body.

Alice

Then safety is a property of the written rule, not a property of J.

Ada · 22

Let \(q\) name the complete rule we have written. We call \(q\) a query on database instance \(J\)

Alice

Is \(q\) another part of database for \(J\)?

Ada · 23

No, \(q\) is neither instance or schema. J supplies relation instances such as J(road). The rule \(q\) is a written expression that we interpret over J.

Alice

So, \(q\) is part of DBMS.

Ada · 24

Can \(q\) only query \(J\)?

Alice

In common sense, \(q\) should be able to query a database.... as long as its a schema has road rleation.

Ada · 25

Yes. We write \(q\) applied on \(J\) as \(q(J)\), call it the image of J under \(q\). You can have \(q(J)\) as a valid statement too.

Alice

So \(q\) is the query, J is its input, and \(q(J)\) is its result relation.

Recap

The relation that was not stored

Let \(\mathcal R\) be an input database schema. A rule-based conjunctive query \(q\) over \(\mathcal R\) has the form

ans(u) :-
    R1(u1),
    ...,
    Rn(un).

Every body relation name belongs to \(\mathcal R\); the head relation name ans does not. Every head variable occurs in the body; this safety guard makes the rule range restricted.

For an input instance \(I\) over \(\mathcal R\),

$$q(I)= \left\{ v(u) \;\middle|\; v\text{ is a valuation over }var(q) \text{ and }v(u_i)\in I(R_i)\text{ for every }i \right\}. $$

The input instance supplies the extensions of the body relations. A successful valuation contributes its head tuple to the separate result relation \(q(I)\), the image of \(I\) under \(q\). The rule gives the intension of that result relation.

Evaluating \(q\) describes a property of \(I\) and produces \(q(I)\). It does not add tuples to or remove tuples from \(I\).