Join Design Notes

PROBLEM

• To implement a mechanism to perform a merge join on the results of a GPM

KNOWN

• E_n Filters for refining triples by permutations of (s,p,o).

QUESTIONS

• what components do you need to be able to perform a merge between two components of a BGP?

IDEAS

TESTS

TASKS

RESOURCES

• Demystifying Join Algorithms
• A Worst-Case Optimal Join Algorithm for SPARQL

SCRATCH NOTES

Imagine a BGP like this:

?pred rdf:domain ?dom.
?inst ?pred ?type.

Where we want to be able to infer:

?inst rdf:type ?dom .

The individual patterns consist of variables, blank nodes and constant URIs. The constants define a filter operation on the triple store. Blank nodes indicate an element should not be filtered on, but also indicates a join point between BGP elements. They should not be 'captured' in the projection, but should be used for joining.

Capturing happens in order of occurrence, and goes into a 'scope' that somehow coordinates the matches during the join process.