Add a matchBGP method for basic graph pattern matching #71

Opened by Claude on behalf of Jesse. It is waiting for Jesse's review and is open for discussion. We're looking for input and consensus so that we can update the types.

Context

Matching a basic graph pattern (a set of quad patterns whose terms may be variables) is a common need for code that sits on top of an RDF/JS dataset: rule engines, shape validators, small query helpers. Today every library writes its own join over repeated DatasetCore.match calls, and a store that could join more efficiently on its own indexes has no shared interface to expose that through.

N3.js explored a Store.matchBGP(patterns) method (formerly rdfjs/N3.js#809). It now lives in a standalone package, n3-match-bgp (npm install n3-match-bgp), which joins on the N3.js Store's internal indexes and falls back to match for any other DatasetCore. It will only land in N3.js itself if a shared interface is agreed here.

Proposal

An optional interface, added next to DatasetCore:

export interface BgpMatchable<Q extends BaseQuad = Quad, B extends Bindings = Bindings> {
    matchBGP(patterns: Iterable<Q>): Iterable<B>;
}

• Each pattern is a quad whose terms may be Variables.
• Each solution is a Bindings object (from the query spec types) mapping every variable in the patterns to a term.
• A variable that occurs in several patterns, or several times in one pattern, binds the same term everywhere.
• The order of solutions is arbitrary.

Draft PR: #72

Compatibility

The change is purely additive. It adds one new interface and changes nothing that exists, so every current implementation and caller of DatasetCore, Dataset, Source and Store keeps compiling unchanged. A dataset opts in by implementing the interface as well, for example class MyStore implements DatasetCore, BgpMatchable, and consumers can feature-detect it with typeof dataset.matchBGP === 'function'. That makes it a minor release.

Open questions

1. Method or function. A method lets a store use its own indexes. n3-match-bgp is a function matchBGP(dataset, patterns, options), which works over any DatasetCore. Should the types describe the method, the function, or both?
2. Synchronous or streaming. The proposal is synchronous (Iterable), matching DatasetCore. Should there be a Source-style variant that returns a ResultStream<Bindings>?
3. Creating bindings. n3-match-bgp takes an optional BindingsFactory so callers such as Comunica get their own Bindings class. Should that be an options argument here?
4. Wildcards. n3-match-bgp also accepts null in a pattern as an unbound wildcard. Should that be part of the contract?
5. Triple terms. With RDF 1.2, a pattern may hold a triple term that contains variables, such as quad(r, rdf.reifies, quad(s, p, o)). Should matchBGP bind variables inside triple terms (as SPARQL 1.2 does)? This connects to Matching patterns inside quads: Variable components in Quad pattern terms of match() #68 and the draft PR for matching inside triple terms.
6. Which spec. Does this belong in the dataset spec or the query spec?

Related

• n3-match-bgp: https://github.com/jeswr/n3-match-bgp
• n3-match-bgp issue for patterns inside triple terms: Match patterns inside RDF 1.2 triple terms jeswr/n3-match-bgp#1
• feat!: match Variables inside Quad pattern terms N3.js#811 (pattern matching inside triple terms, being moved to n3-match-bgp)
• Matching patterns inside quads: Variable components in Quad pattern terms of match() #68 (matching patterns inside quads)