Set Algebra and Logic in RDF Languages

[AdamSobieski]

Introduction

Syntax is explored to provide set-algebraic and logical operations in RDF languages and HTTP techniques involving using the HEAD method to obtain provenance data are discussed for computational optimization.

Set Algebra

Using the * symbol, a theoretical URL-dereferencing syntax (see: #7), using the ?( ... ) operator, a theoretical syntax for creating a lambda-invocation expression (see: #9), and using the ! symbol, a theoretical expression-evaluation syntax (see: #9), syntax for set-algebraic operations might resemble:

!builtin:union?( ( *<1.uris> ) ( *<2.uris> ) ) a ex:Example .

!builtin:intersection?( ( *<1.uris> ) ( *<2.uris> ) ) a ex:Example .

!builtin:difference?( ( *<1.uris> ) ( *<2.uris> ) ) a ex:Example .

These expressions could be nested:

!builtin:union?( ( *<1.uris> ) !builtin:intersection?( ( *<2.uris> ) ( *<3.uris> ) ) ) a ex:Example .

The following set-algebraic operations, which result in xsd:boolean literals, could also be provided:

ex:result rdf:value !builtin:subset?( ( *<1.uris> ) ( *<2.uris> ) ) .

ex:result rdf:value !builtin:properSubset?( ( *<1.uris> ) ( *<2.uris> ) ) .

With the capability to use the HTTP HEAD method to obtain sets' provenance data, including any SPARQL SELECT queries with which the sets were obtained, one could analyze the SPARQL queries to produce new ones for obtaining sets resulting from set-algebraic operations without having to retrieve and exhaustively iterate or enumerate the input sets.

In a sense, one could retrieve sets' "definitions" and use these to construct new sets' "definitions" to compute with and, potentially, to utilize to download resultant sets. Both sets and their provenance data could be stored on, cached on, servers.

Logic

The HTTP HEAD method could be used on text/literal resources of the xsd:boolean variety to explore their provenance data, in particular those source ASK SPARQL queries of which they are the result. Logical operations, too, then, could be included in RDF languages, these operations also capable of analyzing SPARQL queries for optimization purposes.

ex:result rdf:value !builtin:and?( *<x.lit> *<y.lit> ) .

ex:result rdf:value !builtin:or?( *<x.lit> *<y.lit> ) .

ex:result rdf:value !builtin:not?( *<x.lit> ) .

With the capability to use the HTTP HEAD method to obtain Boolean literals' provenance data, including any SPARQL ASK queries from which the literals result, one could analyze the SPARQL queries to produce new ones for obtaining Boolean literal values resulting from Boolean algebraic operations without having to first evaluate the input values.

Dereferencing Lists into Statements

As considered, the syntax:

!builtin:intersection?( ( *<1.uris> ) ( *<2.uris> ) ) a ex:Example .

would result in a list as the subject. For example:

( ex:x ex:y ex:z ) a ex:Example .

However, with the * syntax, used to dereference a list, one could express:

*!builtin:intersection?( ( *<1.uris> ) ( *<2.uris> ) ) a ex:Example .

and the resultant list would be expanded into multiple triples, each list element being the subject of its own triple. For example:

*( ex:x ex:y ex:z ) a ex:Example .

ex:x a ex:Example .
ex:y a ex:Example .
ex:z a ex:Example .

Optimization

Using the Link HTTP response header, resources can provide links to their provenance data including any SPARQL queries used to obtain them. When used in combination with the HTTP HEAD method, this can enable or simplify: (1) performing set-algebraic operations on potentially large sets without having to download and exhaustively iterate or enumerate them, and (2) performing logical operations on Boolean literal values without having to first evaluate them.

Developers could use the HTTP HEAD method to obtain provenance data for sets of individuals (e.g., text/uri-list resources) and for sets of RDF statements (e.g., text/turtle resources) to analyze any available SPARQL queries in order to combine and compose them into new queries to use to obtain sets described or defined in relation to previous ones. Developers could, similarly, use the HTTP HEAD method to obtain and analyze provenance, e.g., ASK SPARQL queries, for text/literal resources of the xsd:boolean variety.

Examples

Drawing inspiration from PROV-AQ, the following HTTP HEAD request:

HEAD /sets/dogs.uris HTTP/1.1
Host: www.data.org
Accept: text/uri-list

might result in the following HTTP response:

HTTP/1.1 200 OK
Date: Wed, 19 August 2026 12:28:53 GMT
Content-Type: text/uri-list
Link: <http://www.data.org/sets/dogs.prov.ttl>; rel="http://www.w3.org/ns/prov#has_provenance"; type="text/turtle"

What would a dogs.prov.ttl resource resemble in order to indicate the one or more SPARQL queries used to obtain the set of individuals in dogs.uris? It might resemble:

@prefix prov: <http://www.w3.org/ns/prov#> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema> .
@prefix ex: <http://example.org/stuff/1.0/> .

<http://www.data.org/sets/dogs.uris>
    a prov:Entity ;
    prov:wasGeneratedBy ex:SparqlQueryExecution .

ex:SparqlQueryExecution
    a prov:Activity ;
    prov:used ex:SourceSparqlQuery ;
    prov:startedAtTime "2026-08-19T10:00:00Z"^^xsd:dateTime ;
    prov:endedAtTime "2026-08-19T10:00:02Z"^^xsd:dateTime .

ex:SourceSparqlQuery
    a prov:Entity ;
    prov:value """
        PREFIX ex: <http://example.org/stuff/1.0/>
        SELECT ?x WHERE { ?x a ex:Dog . ex:alice ex:hasPet ?x . }
    """^^xsd:string ;
    ex:sparqlEndpoint <http://www.data.org/sparql-endpoint/> .

Inside of the SPARQL query available in the provenance data for the resource dogs.uris, in particular inside of its WHERE clause, one can observe that the set in question is an intersection of a set of dogs and a set of Alice's pets.

Note that, in addition to text-string representations of SPARQL queries, the SPIN ontology could be utilized.

Provenance for Resources Resulting from In-progress or Pending Computation

In addition to providing provenance data for resources which have already been computed, there is to consider providing provenance data for resources which have yet to be computed. With these varieties of provenance, one could use the HTTP HEAD method to examine any SPARQL queries for resources which are to be computed, are being computed, or will only be computed only upon request.

The presence or omission of prov:startedAtTime and prov:endedAtTime predicates and their values could be of use, in addition to other semantic content, for clearly distinguishing between these cases.

Provenance for Resources which are Too Complex or Large to Compute, Store, or Transmit

Provenance, including SPARQL utilized to obtain a resource, can also be provided for resources which are estimated by a server to be too complex or large to compute, store, or transmit. For these cases, an HTTP HEAD method request might result in the following HTTP response:

HTTP/1.1 204 No Content
Date: Wed, 19 August 2026 12:28:53 GMT
Content-Type: text/uri-list
Link: <http://www.data.org/sets/dogs.prov.ttl>; rel="http://www.w3.org/ns/prov#has_provenance"; type="text/turtle"

One could still, in these cases, obtain SPARQL queries for such resources to, for example, form intersections which might be computable, storable, and transmittable.

Requirements

As presently considered, in addition to #7, for all of the envisioned features and optimizations to work, requirements would include:

1. it must be possible to canonicalize optimized queries, e.g., for hashing and equality-comparison purposes.

and SPARQL endpoints would need to be able to (including as a result of HTTP content negotiation):

2. output the results of single-variable SELECT queries to content of MIME type text/uri-list.
   1. this might involve using the isIRI() function in a FILTER clause.
3. output the results of ASK queries to content of MIME type text/literal of the xsd:boolean variety.
4. utilize HTTP 300 response codes to redirect querying clients to URL-addressable cached, or memoized, results.

Glossary

Algebra of Sets, Boolean Algebra, Extensional and Intensional Definitions, Futures and Promises, Incremental Computing, Language Integrated Query, Lazy Evaluation, Lazy Initialization, Memoization, Query Language, Query Optimization, Set-builder Notation

Conclusion

What do you think about these ideas? Thank you.