2b:null 2c:["$","title",null,{"children":"Dydra's SPARQL Query Processing Extensions : Entailed Paths | datagenous | Observable"}] 31:Tf3d, ## Overview Dydra's SPARQL query processor enhances query processing by embedding predefined queries, views, within broader SPARQL queries. A notable recent extension allows these views to be embedded within SPARQL property paths, enabling advanced recursive entailment. ## SPARQL Property Paths Context SPARQL property paths offer graph traversal capabilities using predicates and their repetition operators (`+`, `*`). Dydra's extension enables referencing predefined views directly in paths, integrating custom logical entailment seamlessly. ### Example With a defined entailment view: ```sparql SELECT ?owner ?heir WHERE { { ?owner ?child } UNION { ?owner ?child } } ``` A query leveraging this view could be: ```sparql SELECT ?owner ?heir WHERE { ?owner + ?heir } ``` This query implicitly encapsulates multiple predicates defined within the view. The intended usage involves '+' paths. Kleene star formulations are legal syntactic forms, but likely les useful, as the path semantics intends to yield all nodes self-referentially. The entailment view projects two variables which correspond by position with those of the reference. ## Relation to SPARQL Entailment Regimes SPARQL entailment regimes typically include predefined logical reasoning (e.g., RDF, RDFS, OWL). Dydra's extension allows user-defined entailment, effectively creating a customizable regime through views. It provides recursive entailment via `+` semantics. ## Historical Context * **Standard SPARQL (1.1, 2013):** Introduced property paths. * **Federated Query (`SERVICE`):** Allowed querying external SPARQL endpoints. Dydra previously used local-service requests for views. * **Magic Properties:** Earlier extensions improved efficiency in complex queries through optimizations similar to database magic sets. This extension synthesizes these capabilities into a cohesive feature. It provides several evident benefits. * **Enhanced Flexibility:** Abstracting complex logic into reusable views. * **Expressive Power:** Simplified syntax for powerful recursive entailment. * **Seamless Integration:** Familiar property path syntax minimizes learning curve. * **Customizable Reasoning:** Allows tailored entailment beyond standard regimes. Still, there are resource issues to be kept in mind. * **Performance Overhead:** Recursive paths increase complexity and computational demands. * **Debugging Complexity:** Abstracted views complicate debugging. * **Maintenance Complexity:** Increased dependency management for complex, interrelated views. ## Comparative Table | Aspect | Standard SPARQL Paths | SPARQL Entailment Regimes | Dydra's Extension | | --------------------- | --------------------- | ------------------------- | ------------------------- | | Reasoning Flexibility | Limited | Moderate (predefined) | High (fully customizable) | | Recursive Queries | Basic | Indirect | Direct and customizable | | Modularity | Moderate | Low | High | | Standardization | High | Moderate | Low | | Performance Risk | Low-Medium | Medium-High | High | ## Conclusion Dydra's SPARQL extension effectively integrates customizable recursive entailment into property paths, significantly increasing query expressivity and modularity. However, potential drawbacks in complexity, performance, and interoperability must be managed through robust optimization, clear documentation, and careful architectural considerations. This approach is highly suitable for complex, knowledge-intensive applications needing sophisticated custom inference. 32: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.33: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 34:T467, --- [galindo-legaria.2001](https://www.comp.nus.edu.sg/~cs5226/papers/subqueries-sigmod01.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. ---35:[] 2f:{"id":"89b9515e77382331","slug":"dydras-sparql-path-entailment","title":"Dydra's SPARQL Query Processing Extensions : Entailed Paths","thumbnail":"a17eab94997183adcae85acab94e41f26f2321acbcd43f0dc78c3796dafe3fe6","access_level":"public","create_time":"$D2025-06-17T14:55:31.131Z","update_time":"$D2025-06-17T22:28:03.691Z","view_time":null,"first_public_time":"$D2025-06-17T22:28:39.144Z","fork":{"id":"c78d31f98a650608","slug":"correlated-subqueries-in-sparql","title":"Correlated Subqueries in SPARQL","owner":{"id":"ad42203b295b2120","login":"datagenous","name":"datagenous"}},"stars":0,"starred":false,"owner":{"type":"team","id":"ad42203b295b2120","login":"datagenous","name":"datagenous","avatar_url":"https://avatars-next.observableusercontent.com/c8136cc7228bf2ad689462f6a332e51dc9984c845619ac0f34ca730875bf0c7a","tier":"pro"},"version":419,"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}],"members":[{"type":"individual","id":"987c90ad70c449c1","login":"lomoramic","name":"James Anderson","avatar_url":"https://avatars-next.observableusercontent.com/dc520bbc733259f2913522cf1d50607777b98a3083f290a6f182534561896497","tier":null,"role":"editor"},{"type":"team","id":"ad42203b295b2120","login":"datagenous","name":"datagenous","avatar_url":"https://avatars-next.observableusercontent.com/c8136cc7228bf2ad689462f6a332e51dc9984c845619ac0f34ca730875bf0c7a","tier":"pro","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Dydra's SPARQL Query Processing Extensions : Entailed Paths","cells":[{"id":0,"value":"# Dydra's SPARQL Query Processing Extensions : Entailed Paths","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":5,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":266,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":347,"value":"allResults","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":344,"value":"allResults = await getSparqlResults(\"all\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":407,"value":"----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":243,"value":"viewof jenaViewName = Inputs.select(jenaViews, { label: \"Jena query variants\" })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$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"},{"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"},{"id":323,"value":"jenaResults","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$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"},{"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"},{"id":337,"value":"variantResults","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":335,"value":"variantResults = await getSparqlResults(variantViewName)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":410,"value":"----","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":258,"value":"## Discussion","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":92,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$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"},{"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"},{"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"},{"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"},{"id":289,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$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"},{"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"},{"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"},{"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"},{"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"},{"id":127,"value":"server = \"https://dydra.com:8443\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":129,"value":"repository = accountName + \"/\" + repositoryName","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":210,"value":"accountName = \"sparql-12\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":212,"value":"repositoryName = \"lateral\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$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"},{"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"},{"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"},{"id":233,"value":"allViews = (await getViewNames()).split(\"\\n\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"