Two related but distinct concepts from the SPARQL literature are relevant
here.
Query containment is a semantic property: query Q1 is contained in Q2
(written Q1 ⊑ Q2) if, for every possible RDF graph, the answers to Q1 are a
subset of the answers to Q2.
Query subsumption is a structural witness for containment: a mapping from
the variables of one query to the terms of another that demonstrates
containment holds without evaluating over any actual data.
In practice, we use a subsumption check as a lightweight proxy for
containment. A SPARQL query can be compiled into an algebra tree — a
structured representation of its joins, filters, optional patterns, unions
and so on. Given a pre-approved template query and a client-supplied query,
we walk both algebra trees in parallel and check, operator by operator,
whether the client query is a valid specialisation of the template. The
rules per operator are:
subsumes(template, client):
BGP, BGP → every template triple matches some client triple
under a consistent substitution of template variables
JOIN, JOIN → subsumes(left, left) ∧ subsumes(right, right)
FILTER, FILTER → template filters ⊆ client filters ∧ subsumes(inner,
inner)
FILTER, _ → false (client dropped a template filter)
_, FILTER → subsumes(template, inner) (client added a filter —
ok)
OPTIONAL, OPTIONAL → subsumes(left, left) ∧ subsumes(right, right)
OPTIONAL, JOIN → subsumes(left, left) ∧ subsumes(right, right)
(optional→required ok)
_, OPTIONAL → false (client introduced OPTIONAL not in template)
UNION, UNION → subsumes(left, left) ∧ subsumes(right, right)
UNION, _ → subsumes(left, client) ∨ subsumes(right, client)
_, UNION → false (client introduced UNION not in template)
MINUS, MINUS → subsumes(left, left)
_, MINUS → subsumes(template, left) (client added MINUS — ok)
MINUS, _ → false (client dropped a MINUS)
SLICE, SLICE → client limit ≤ template limit ∧ subsumes(inner, inner)
PROJECT, PROJECT → subsumes(inner, inner)
This check is sound but intentionally incomplete. Sound means that if the
check passes, containment is guaranteed — the client query cannot return
results outside the scope of the template. Incomplete means it may reject
queries that are semantically equivalent but expressed in a syntactically
different form. For a security gate this is the correct trade-off: false
negatives (over-rejection) are safe, false positives (under-rejection)
would not be.
On Sat, Mar 7, 2026 at 2:55 PM Andy Seaborne <[email protected]> wrote:
> > Claude calls this "pattern containment" or "query subsumption".
>
> Ask Claude what it thinks these terms mean.
>
> Seems like "will pattern T1, return a superset of the triples returned
> by T2". i.e variable names don't matter but they must be consistently
> used if they occur more than once.
>
> Andy
>
>
> On 05/03/2026 23:53, Justin Dowdy wrote:
> > It seems like one query is "isomorphic" to another query if and only if
> > they produce the same bindings when evaluated against all possible data
> > sets.
> >
> > If you want to do this in the general case you might need a way to
> simulate
> > all possible data sets then evaluate the queries against them, right?
> >
> > On Thu, Mar 5, 2026, 2:37 PM Martynas Jusevičius <[email protected]
> >
> > wrote:
> >
> >> Hi,
> >>
> >> What would be the way to check programatically using Jena that
> >>
> >> { <http://localhost/> rdf:type ?x }
> >>
> >> is a substitution of a binding (?s = <http://localhost/>) or VALUES
> (?s)
> >> { <
> >> http://localhost/> }
> >>
> >> on
> >>
> >> { ?s rdf:type ?type }
> >>
> >> but
> >>
> >> { <http://localhost/> another:property ?x }
> >>
> >> is not?
> >>
> >> Basically check if a query is "isomorphic" to a given query template?
> >>
> >> Claude calls this "pattern containment" or "query subsumption".
> >>
> >>
> >> Martynas
> >>
> >
>
>
