2c:null 2d:["$","title",null,{"children":"Correlated Subqueries in SPARQL | datagenous | Observable"}] 32:T12bf,In the original [1.0 version](http://www.w3.org/TR/2008/REC-rdf-sparql-query-20080115/), SPARQL provided means to express RDF graph patterns, apply them to an RDF dataset, arrange the terms matched from the given patterns into solutions, and return them as solution sequences or new RDF graphs. The language semantics described how to apply various algebra operators to combine the results from statement pattern matches to compute conjunctions and disjunctions, to constrain the results with filters, to modify their order, to apply a window to the solution sequence. In all combinations, however, an algebra expression is interpreted "from the bottom up". This means that each branch of an expression is interpreted independent of others, with the respective results combined within the operators only. Variables are bound by basic graph statement patterns, SELECT, BIND, and VALUES clauses and a binding's scope is those operators in the algebra tree to which it is supplied in solution arguments. As SPARQL implementations evolved, they introduced mechanisms which loosened the restriction. The nested loop approach to interpreting a basic graph pattern passes bindings over a JOIN operator between statement patterns.[stocker.2008] "Sideways information passing" extended this approach to communicate bindings between entire basic graph patterns by applying it to any operator which involves solution compatibility.[neuman.2009] The approaches realize the principle, that in situations where the observed cardinalities suggest that the bindings in the solutions in one branch could be used to limit the resources required to evaluate the other branch, so long as the implementation ensures that the result be the same as if the branch evaluations were independent, the other branch could be interpreted repeatedly with the statement patterns of that branch constrained by binding from successive solutions in the one branch. The appearance of SPARQL [1.1](http://www.w3.org/TR/2013/REC-sparql11-query-20130321/), however, suggested use cases which even the relaxed restriction precludes. That version introduced nested `SELECT` clauses, of which the modifier clause raised questions. Where the `SELECT` is nested, the strict interpretation is that modifiers must apply to the entire solution sequence returned by the subselect. There are, however, relations which can be established by a single query only if interpretation of the subselect clause depends on the bindings from solutions of the other clause. The "bottom-up" restriction makes it impossible to achieve some useful results because it proscribes the means to express them. - The subselect can include variables which are free within its scope, but bound in the scope of the other clause, in such a manner that they interact with groups of solutions. - slice modifiers should apply to groups of solutions of the subselect which are identified by bindings from solutions of the other clause. any order modifier would be also affected by this change. - aggregation operators are to be applied subsequent to modifiers. In the first case, a query such as ``` SELECT * { ?s ?p ?o . { SELECT { ?x ?q ?y . FILTER (?x != ?s) } } } ``` would be invalid, as the ?s variable is free in the subselect. In the second case, a query ``` SELECT ?s ?label { ?s ?p ?o { SELECT * { ?s :label ?label } LIMIT 2 } } ``` would yield just two solutions from the subselect rather than two for each `?s` binding from the initial pattern. Algebraic variants from SQL could be adapted to SPARQL to afford it the expressive power necessary to support these cases, to the extent that they are relevant. These approaches add support for correlated subqueries by changing the [scope and extent rules](https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node43.html) for variable bindings. - The "unnesting" approach for the subqueries [neumann.2015] is not directly applicable as SPARQL does not include sub-queries as single valued joins. - A form of sidewards information passing is realized for dependent joins by the `LATERAL JOIN`, or `APPLY`[galindo-legaria.2001] operators enlarge the extent of correlated bindings from the primary solutions into the secondary form. Under this mechanism their extent supplants that of the statement pattern bindings from the secondary form. We employ dynamic bindings to this effect. - An aggregation operator variant limits the extent of bindings to the solution subsets identified by respective key values which correlate with the primary clause in order to distribute modifications and aggregation operators over the distinct subsets. We define a `SEGMENT` operator for this purpose to partition the solution set and rearrange the interpretation control flow to switch the order of modify, and aggregation. 33:T5e4,## Examples This issue concerns several query variants and alternative mechanisms to support them. Changes to SPARQL semantics to permit these cases are considered for [SPARQL 1.2](https://github.com/w3c/sparql-12/issues/100), in which context cases are embodied by several tests queries in the [Jena project](https://github.com/apache/jena/blob/main/jena-arq/testing/ARQ/Lateral). These appear below as "Jena query variants". A set of additional examples follows from combinations of the constituent SELECT, GROUP, ORDER, LIMIT, OFFSET and and aggregate operators. These appear below as "combinatoric query variants". Two approaches are available to realize the dependence: - Rely on sidewards information passing (S-I-P) to repeat the interpretation process for the dependent clause in a context which constrains the values of any shared variables. - Rewrite the algebra of the dependent clause to segment the solution set and apply the modify options each segment in turn. The examples illustrate how the respective approach realizes the dependency for each individual query. Each example presents four views of the query variant. - the original SPARQL expression - the equivalent SPARQL algebra expression: this depicts the operator combination in an unambiguous form. - the preliminary query plan: this presents the query execution plan as reformulated to implement the applicable approach - the query results The example presentations are followed by a discussion of each example in turn.34:T477,### LATERAL-1 The common `?s` binding and the sub-select limit suggest that the intent is to combine each subject's `` object term(s) with the first two `` terms for each respective subject. A `JOIN` operator in a SPARQL 1.1 query cannot yield the intended combinations as the sub-query would yield just the first two solutions from all combinations generated by the `{?s :label ?label}` pattern, rather than apply the constraint from each base solution of the `{?s :p ?o}` pattern in succession to the sub-query branch. The intent of the `LATERAL` operator, rather than the `JOIN`, is to focus the effect of sub-select modifiers. While the S-I-P approach would realize the intent, in this situation, where a binding is shared between the two clauses, experience with similar operations in SQL demonstrated that it is more efficient to segment the sub-select result, modify the segments and combine them with the base solutions with a join variant. This dependent behaviour can be implemented in the sub-select alone where it is formulated as a modified segment, for which the preliminary plan is 35:T491, --- [galindo-legaria.2001](https://www.cse.iitb.ac.in/infolab/Data/Courses/CS631/2005/Project/ref/orthOptOfSubQueriesp571galindolegaria.pdf) : C. Galindo-Legaria, M. Joshi. Orthogonal Optimization of Subqueries and Aggregation [neumann.2009](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=5667528b5502e45544ecd414820e1a96edbede3e) : T. Neumann and G. Weikum. Scalable join processing on very large RDF graphs. In SIGMOD, 2009. [neumann.2015](https://dl.gi.de/bitstream/handle/20.500.12116/2418/383.pdf) : T. Neumann, A. Kemper. Unnesting Arbitrary Queries. [neumann.2017](https://15721.courses.cs.cmu.edu/spring2023/papers/17-optimizer2/hyperjoins-btw2017.pdf) : Neumann, Thomas, Viktor Leis, and Alfons Kemper. "The Complete Story of Joins (in HyPer)." In BTW, pp. 31-50. 2017. [stocker.2008](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=e2d7420e1e63257284103fecd07be789c295ee2a) : Stocker, M; Seaborne, A; Bernstein, A; Kiefer, C; Reynolds, D (2008). SPARQL Basic Graph Pattern Optimization Using Selectivity Estimation. In: 17th International World Wide Web Conference (WWW), Beijing, China, 21 April 2008 - 25 April 2008. ---36:[] 30:{"id":"c78d31f98a650608","slug":"correlated-subqueries-in-sparql","title":"Correlated Subqueries in SPARQL","thumbnail":"7686f0d1162036b97db4eaeed6d14cf9fd68954eecfed16d3193a90dd82ec5ea","access_level":"public","create_time":"$D2023-02-19T01:30:21.276Z","update_time":"$D2026-09-10T15:10:41.011Z","view_time":null,"first_public_time":"$D2023-04-06T23:28:16.569Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"ad42203b295b2120","login":"datagenous","name":"datagenous","avatar_url":"https://avatars-next.observableusercontent.com/c8136cc7228bf2ad689462f6a332e51dc9984c845619ac0f34ca730875bf0c7a","tier":"pro","bio":""},"version":414,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"987c90ad70c449c1","login":"lomoramic","name":"James Anderson","avatar_url":"https://avatars-next.observableusercontent.com/dc520bbc733259f2913522cf1d50607777b98a3083f290a6f182534561896497","tier":null,"bio":"I am one of the developers for dydra.com."}],"members":[{"type":"team","id":"ad42203b295b2120","login":"datagenous","name":"datagenous","avatar_url":"https://avatars-next.observableusercontent.com/c8136cc7228bf2ad689462f6a332e51dc9984c845619ac0f34ca730875bf0c7a","tier":"pro","role":"editor"},{"type":"individual","id":"987c90ad70c449c1","login":"lomoramic","name":"James Anderson","avatar_url":"https://avatars-next.observableusercontent.com/dc520bbc733259f2913522cf1d50607777b98a3083f290a6f182534561896497","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Correlated Subqueries in SPARQL","cells":[{"id":0,"value":"# Correlated Subqueries in SPARQL","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":266,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":347,"value":"allResults","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":344,"value":"allResults = await getSparqlResults(\"all\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":407,"value":"----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":243,"value":"viewof jenaViewName = Inputs.select(jenaViews, { label: \"Jena query variants\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"viewof variantViewName = Inputs.select(otherViews, {\n label: \"combinatoric query variants\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"----\n### Jena Example\n\nThe ${jenaViewName} query is\n

\n${ await getSparqlQuery(jenaViewName)}\n

\n\nThe algebra is\n

\n${ await getSparqlAlgebra(jenaViewName)}\n

\n\nThe preliminary plan is\n

\n${ await getSparqlPlan(jenaViewName)}\n

\n\nThe ${jenaViewName} results are","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":323,"value":"jenaResults","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":324,"value":"jenaResults = {\n var r = await getSparqlResults(jenaViewName);\n console.log(\"jenaResults\", r);\n return r;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":252,"value":"----\n### Variant Examples\n\nThe ${variantViewName} query is\n

\n${ await getSparqlQuery(variantViewName)}\n

\n\nThe algebra is\n

\n${ await getSparqlAlgebra(variantViewName)}\n

\nThe preliminary plan is\n

\n${ await getSparqlPlan(variantViewName)}\n

\n\nThe results are","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":337,"value":"variantResults","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":335,"value":"variantResults = await getSparqlResults(variantViewName)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":410,"value":"----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":258,"value":"## Discussion","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":92,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":94,"value":"----\n### LATERAL-2\nThis query demonstrates the result of a lateral combination with a unit table wich results from the presence of a unit table as the primary argument form.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":80,"value":"----\n### LATERAL-3 (-DEPENDENT, -JOIN)\n\nThis query variant explores the relation between two binding forms - in this case statement patterns, when filters are used to apply constraints in addition to variable identity.\nThe \"lateral\" form expresses an optional join between two basic graph patterns where the secondary pattern is subject to filters which incorporate bindings from the first pattern.\nIt requires that the bindings from solutions of the primary pattern constrain the interpretation of the secondary pattern.\n\nThe \"dependent\" variant replaces the optional combination with a join combination, which yields just those combinations for which the secondary pattern yielded solutions.\n\nThe \"join\" variant demonstrates that the \"lateral\" formulation is contrived, just to demonstrate the constraint.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":103,"value":"----\n### LATERAL-4, LATERAL-5\n\nThese query variants are intended to demonstrate the consequence of a select form which introduces a distinct scope for the `?S` binding in the secondary graph pattern.\nThe Jena implementation suggests that, where the scopes in \"LATERAL-5\" are distinct and share no binding, the result solutions constitute the cross join between the respective solution sets, while the appearance of the `?S` variable in the secondary projection causes the primary solutions to constrain the interpretation of the secondary pattern, and the final result to be just three joined solutions.\n\nThis distinction introduces a contradiction.\nIt would preclude free variables in any select form which did not include them among the projected variables.\nIn order to avoid that, this implementation establishes the dimensions of the dependency independent of any projection.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":98,"value":"would be invalid, as the `?s` and `?z` in the filter forms appear outside of the scope of the bindings established by the `{?s :q ?z}` BGP, earlier in the query.\n\nIn another case, a [query](https://github.com/apache/jena/blob/main/jena-arq/testing/ARQ/Lateral/lateral-1.arq) such as \n```\nPREFIX : \n\nSELECT ?s ?label {\n ?s :p ?o\n LATERAL { SELECT * { ?s :label ?label } LIMIT 2 }\n}\n```\n\ncould not yield the intended combinations as the subquery would yield just the first two solutions from all combinations generated by the `{ ?s :label ?label }` pattern, but would not apply the constraint to the results for that pattern when constrained to each `?s` term from the `{ ?s :p ?o }` branch.\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":289,"value":"$35","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":62,"value":"getSparqlQuery = {\n var viewOp = resourceAPI(server + \"/\" + repository, \"VIEW\");\n var asSparql = function (viewName) {\n return viewOp(viewName, { Accept: mimeTypes.SPARQL_QUERY });\n };\n return asSparql;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"getSparqlAlgebra = {\n var viewOp = resourceAPI(server + \"/\" + repository, \"VIEW\");\n var asSse = function (viewName) {\n return viewOp(viewName, { Accept: mimeTypes.SPARQL_QUERY_ALGEBRA });\n };\n return asSse;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"getSparqlPlan = {\n var viewOp = resourceAPI(server + \"/\" + repository, \"VIEW\");\n var asSse = function (viewName) {\n return viewOp(viewName, { Accept: mimeTypes.SPARQL_QUERY_PLAN });\n };\n return asSse;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"getSparqlResults = {\n var viewOp = resourceAPI(server + \"/\" + repository, \"VIEW\");\n var asResults = function (viewName) {\n return viewOp(viewName, { Accept: mimeTypes.JSON });\n };\n return asResults;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"getViewNames = {\n var getOp = resourceAPI(\n server +\n \"/system/accounts/\" +\n accountName +\n \"/repositories/\" +\n repositoryName +\n \"/views\",\n \"GET\"\n );\n var fromLeaf = function () {\n return getOp({ Accept: mimeTypes.TEXT });\n };\n return fromLeaf;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"server = \"https://dydra.com:8443\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"repository = accountName + \"/\" + repositoryName","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":210,"value":"accountName = \"sparql-12\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"repositoryName = \"lateral\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"import {\n resourceAPI,\n resourceAuthenticate,\n mimeTypes\n} from \"@datagenous/resource-protocol-library\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"jenaViews = allViews.filter(function (name) {\n return name.match(/lateral-[0-9].*/);\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":237,"value":"otherViews = allViews.filter(function (name) {\n return name != \"all\" && !name.match(/lateral-[0-9]/);\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"allViews = (await getViewNames()).split(\"\\n\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1"}} 31:"$30:body"