You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2022/11/21 20:33:13 UTC
[jena-site] branch lateral-doc updated (36d1de8af -> 9986e6c5d)
This is an automated email from the ASF dual-hosted git repository.
andy pushed a change to branch lateral-doc
in repository https://gitbox.apache.org/repos/asf/jena-site.git
discard 36d1de8af Documentation for LATERAL
new 9986e6c5d Documentation for LATERAL
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (36d1de8af)
\
N -- N -- N refs/heads/lateral-doc (9986e6c5d)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
source/documentation/query/lateral.md | 52 +++++++++++++++++------------------
1 file changed, 26 insertions(+), 26 deletions(-)
[jena-site] 01/01: Documentation for LATERAL
Posted by an...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
andy pushed a commit to branch lateral-doc
in repository https://gitbox.apache.org/repos/asf/jena-site.git
commit 9986e6c5d1da9ebf736d1e6871c8642327173e05
Author: Andy Seaborne <an...@apache.org>
AuthorDate: Mon Nov 21 20:29:57 2022 +0000
Documentation for LATERAL
---
source/documentation/query/__index.md | 1 +
source/documentation/query/lateral.md | 174 ++++++++++++++++++++++++++++++++++
2 files changed, 175 insertions(+)
diff --git a/source/documentation/query/__index.md b/source/documentation/query/__index.md
index bdb3da82b..7d9063935 100644
--- a/source/documentation/query/__index.md
+++ b/source/documentation/query/__index.md
@@ -69,6 +69,7 @@ Features of ARQ that are legal SPARQL syntax
Feature of ARQ that go beyond SPARQL syntax.
+- [LATERAL Join](lateral-join.html)
- [RDF-star](https://w3c.github.io/rdf-star/)
- Operators and functions
`[MOD](https://www.w3.org/TR/xpath-functions/#func-numeric-mod)`
diff --git a/source/documentation/query/lateral.md b/source/documentation/query/lateral.md
new file mode 100644
index 000000000..7e64fd409
--- /dev/null
+++ b/source/documentation/query/lateral.md
@@ -0,0 +1,174 @@
+---
+title: ARQ - Lateral Join
+---
+
+Lateral joins using the keyword `LATERAL` were introduced in Apache jena 4.7.0.
+
+A `LATERAL` join is like a foreach loop, looping on the results from the
+left-hand side (LHS), the pattern before the `LATERAL` keyword, and executing
+the right-hand side (RHS) query pattern once for each row, with the variables
+from the input LHS in-scope during each RHS evaluation.
+
+A regular join only executes the RHS once, and the variables from the LHS are
+used for the join condition after evaluation of the left and right
+sub-patterns.
+
+Another way to think of a lateral join is as a `flatmap`.
+
+Examples:
+```
+## Get exactly one label for each subject with type `:T`
+SELECT * {
+ ?s rdf:type :T
+ LATERAL {
+ SELECT * { ?s rdfs:label ?label } LIMIT 1
+ }
+}
+```
+
+```
+## Get zero or one labels for each subject.
+SELECT * {
+ ?s ?p ?o
+ LATERAL { OPTIONAL { SELECT * ?s rdfs:label ?label } LIMIT 1}
+ }
+}
+```
+
+### Syntax
+
+The `LATERAL` keyword which takes the graph pattern so far in the group, from
+the `{` starting of the current block, and a `{ }` block afterwards.
+
+### Evaluation
+
+[Substituting variables](https://afs.github.io/substitute.html) from the LHS into the RHS (with the same restrictions), then executing the pattern, gives the evaluation of `LATERAL`
+
+### Variable assignment
+
+There needs to be a new syntax restriction: there can no variable introduced by
+`AS` (`BIND`, or sub-query) or `VALUES` in-scope at the top level of the
+`LATERAL` RHS, that is the same name as any
+[in-scope](https://www.w3.org/TR/sparql11-query/#variableScope) variable from
+the LHS.
+
+Such a variable assignment would conflict with the variable being set in
+variables of the row being joined.
+
+```
+## ** Illegal **
+SELECT * {
+ ?s ?p ?o
+ LATERAL { BIND( 123 AS ?o) }
+}
+```
+
+See [SPARQL Grammar note 12](https://www.w3.org/TR/sparql11-query/#sparqlGrammar).
+
+In ARQ, [LET](https://www.w3.org/TR/sparql11-query/#variableScope) would work.
+`LET` for a variable that is bound acts like a filter.
+
+### Variable Scopes
+
+In looping on the input, a lateral join makes the bindings of variables in the current row
+available to the right hand side pattern, settign their value from the top down.
+
+In SPARQL, it is possible to have variables of the same name which are not
+exposed within a sub-select. These are not lateral-joined to a variable of the
+same name from the LHS.
+
+This is not speciifc to lateral joins. In
+```
+SELECT * {
+ ?s rdf:type :T
+ { SELECT ?label { ?s rdfs:label ?label } }
+```
+the inner `?s` can be replaced by `?z` without changing the results because the
+inner `?s` is not joined to the outer `?s` but instead is hidden by the `SELECT ?label`.
+```
+SELECT * {
+ ?s rdf:type :T
+ { SELECT ?label { ?z rdfs:label ?label } }
+```
+
+The same rule applies to lateral joins.
+```
+SELECT * {
+ ?s rdf:type :T
+ LATERAL {
+ SELECT ?label { ?s rdfs:label ?label } LIMIT 1
+ }
+}
+```
+
+The inner `?s` in the `SELECT ?label` is not the outer `?s` because the `SELECT
+?label` does not pass out `?s`. As a sub-query the `?s` could be any name except
+`?label` for the same results.
+
+### Notes
+
+There is a similarity to filter `NOT EXISTS`/`EXISTS` expressed as the not-legal `FILTER ( ASK { pattern } )` where the variables of the row being filtered are available to "pattern". This is similar to ab SQL [correlated subquery](https://en.wikipedia.org/wiki/Correlated_subquery).
+
+## SPARQL Specification Additional
+
+### Syntax
+
+`LATERAL` is added to the SPARQL grammar at rule `[[56] GraphPatternNotTriples](https://www.w3.org/TR/sparql11-query/#rGraphPatternNotTriples)`. As a syntax form, it is similar to `OPTIONAL`.
+
+```
+[56] GraphPatternNotTriples ::= GroupOrUnionGraphPattern | OptionalGraphPattern | LateralGraphPattern | ...
+[57] OptionalGraphPattern ::= 'OPTIONAL' GroupGraphPattern
+[ ] LateralGraphPattern ::= 'LATERAL' GroupGraphPattern
+```
+
+### Algebra
+
+The new algebra is operator is `lateral` which takes two expressions
+
+```
+ SELECT * {
+ ?s ?p ?o
+ LATERAL
+ { ?a ?b ?c }
+}
+```
+is translated to:
+```
+ (lateral
+ (bgp (triple ?s ?p ?o))
+ (bgp (triple ?a ?b ?c)))
+```
+
+### Evaluation
+
+To evaluate `lateral`:
+
+* Evaluate the first argument (left-hand side from syntax) to get a multiset of solution mappings.
+* For each solution mapping ("row"),
+ inject variable bindings into the second argument
+ Evaluate this pattern
+ Add to results
+
+Outline:
+```
+Definition: Lateral
+
+Let Ω be a multiset of solution mappings. We define:
+
+Lateral(Ω, P) = { μ | union of Ω1 where
+ foreach μ1 in Ω:
+ pattern2 = inject(pattern, μ1)
+ Ω1 = eval(D(G), pattern2)
+ result Ω1
+ }
+```
+where `inject` is the [corrected `substitute`](https://afs.github.io/substitute.html) operation.
+
+An alternative style is to define Lateral more like "evaluate P such that μ is in-scope" in some
+way, rather than rely on `inject` which is a mechanism.
+
+```
+Definition: Evaluation of Lateral
+
+eval(D(G), Lateral(P1, P2) = Lateral(eval(D(G), P1), P2)
+```