2b:null 2c:["$","title",null,{"children":"Collated Reification | James Anderson | Observable"}] 31:T698,The `spa/ppp` [repository](https://dydra.com/sba/ppp) comprises sixty-six million statements which represent the registration data for approximately five million participants in the Small Business Administration's ["Payroll Protection Program"](https://www.sba.gov/funding-programs/loans/covid-19-relief-options/paycheck-protection-program). Many registration records are incomplete, but nine of the numerous collected attributes are present for all records. ``` prefix ppp: select ?subject $city $state $businessname ?ethnicity ?gender ?veteran ?dateapproved ?lender ?cd ?businesstype ?nonprofit ?loanrange ?address from where { ?subject ppp:City $city . ?subject ppp:State $state . ?subject ppp:RaceEthnicity ?ethnicity . ?subject ppp:Gender ?gender . ?subject ppp:Veteran ?veteran . ?subject ppp:DateApproved ?dateapproved . ?subject ppp:Lender ?lender . ?subject ppp:CD ?cd . optional { ?subject ppp:BusinessType ?businesstype . } optional { ?subject ppp:NonProfit ?nonprofit . } optional { ?subject ppp:LoanRange ?loanRange . } optional { ?subject ppp:BusinessName $businessname . } optional { ?subject ppp:Address ?address . } } ``` One way to construct those records is to join the respective statements by subject term. An alternative is to arrange the statement storage to enable collated retrieval. The time required to construct a full record respective the attribute complement is depicted below. The upper curve is the time required to construct an entity by joining the respective statements. The lower curves indicate the time required to construct it by collating those statements.32:T435,{ function dataCount(d) { return(d[0]); } function dataTime(d) { return(d[2]/1000); } return ( Plot.plot({ y: { label: "elapsed time"}, x: { label: "statement patterns"}, marks: [ Plot.line(uncollated, {x: dataCount, y: dataTime, stroke: "gray"}), Plot.dot(uncollated, {x: dataCount, y: dataTime}), Plot.text(uncollated, {x: dataCount, y: d=> (dataTime(d)+2), text: dataTime}), Plot.text([uncollated[uncollated.length-1]], {x: d=> dataCount(d), y: d=> (dataTime(d)-2), text: d=>"uncollated"}), Plot.line(collated_1, {x: dataCount, y: dataTime, stroke: "gray"}), Plot.dot(collated_1, {x: dataCount, y: dataTime}), Plot.text(collated_1, {x: dataCount, y: d=> (dataTime(d)-2), text: dataTime}), Plot.line(collated_2, {x: dataCount, y: dataTime, stroke: "gray"}), Plot.dot(collated_2, {x: dataCount, y: dataTime}), Plot.text(collated_2, {x: dataCount, y: d=> (dataTime(d)-4), text: dataTime}), Plot.text([collated_2[collated_2.length-1]], {x: d=> dataCount(d), y: d=> (dataTime(d)+2), text: d=> "collated"}), ]}) ) }33:T713,The timing was performed with generated queries: ``` (let ((sba-patterns '((spocq.a:|triple| ?::|subject| ?::|city|) (spocq.a:|triple| ?::|subject| ?::|cd|) (spocq.a:|triple| ?::|subject| ?::|lender|) (spocq.a:|triple| ?::|subject| ?::|dateApproved|) (spocq.a:|triple| ?::|subject| ?::|veteran|) (spocq.a:|triple| ?::|subject| ?::|gender|) (spocq.a:|triple| ?::|subject| ?::|ethnicity|) (spocq.a:|triple| ?::|subject| ?::|state|)))) (let ((statistics (loop for limit from 1 upto (length sba-patterns) do (sb-ext:gc :full t) collect (let* ((query `(spocq.a:|select| (spocq.a:|bgp| ,@(subseq sba-patterns 0 limit)) ((?::|count| (spocq.a:|count| SPOCQ.S:*))))) (start (get-internal-run-time)) (result (test-sparql query :repository-id "sba/ppp" :DATASET-GRAPHS '(:NAMED-GRAPHS NIL :DEFAULT-GRAPHS (|urn:dydra|:|all|)))) (time (- (get-internal-run-time) start))) (format *trace-output* "~&~a, ~a, ~a" limit (caar result) time) (finish-output *trace-output*) (list limit (caar result) time))))) (format *trace-output* "~&limit, count, milliseconds") (loop for (limit result-count time) in statistics do (format *trace-output* "~&~a, ~a, ~a" limit result-count time)) (fresh-line *trace-output*))) ``` 34:T466,viewof footnotes = footlist([ {ref: 'terms', text: `Statements are present in a graph either by reference or by value. Those incorporated by value have indefinite extent - their asserted relation is always included in a simple entailment. Those incorporated by reference have an extent limited to specific named graphs are are included under the terms of particular entailment regimes only.`}, {ref: 'pham2015', text: `"Deriving an Emergent Relational Schema from RDF Data", https://ir.cwi.nl/pub/23379/23379B.pdf`}, {ref: 'neuman2011', text: `"Characteristic Sets: Accurate Cardinality Estimation for RDF Queries with Multiple Joins", https://www.csd.uoc.gr/~hy561/papers/`}, {ref: 'galkin2017', text: `"SMJoin: A Multi-way Join Operator for SPARQL Queries", https://www.researchgate.net/profile/Mikhail-Galkin/publication/318361204_SMJoin_A_Multi-way_Join_Operator_for_SPARQL_queries/links/5965e0480f7e9b2a36807f8a/SMJoin-A-Multi-way-Join-Operator-for-SPARQL-queries.pdf`}, {ref: 'hogan', text: `"A Worst-Case Optimal Join Algorithm for SPARQL" , https://aidanhogan.com/docs/SPARQL_worst_case_optimal.pdf`} ])35:[] 2f:{"id":"35e7dc3b8631a57f","slug":"collated-reification","title":"Collated Reification","thumbnail":"0437991c78769eb7088288b846f18e9b73edc2beceb75b7bf8b1d220804b536b","access_level":"public","create_time":"$D2021-07-10T00:44:58.248Z","update_time":"$D2024-08-10T11:55:37.308Z","view_time":null,"first_public_time":"$D2021-07-10T02:11:36.508Z","fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"b452fd69977f5701","login":"lomoramic","name":"James Anderson","avatar_url":"https://avatars-next.observableusercontent.com/dc520bbc733259f2913522cf1d50607777b98a3083f290a6f182534561896497","tier":"starter_2024"},"version":180,"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"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Collated Reification","cells":[{"id":0,"value":"md`# Collated Reification\n## reasons for rdf-star\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8,"value":"One reason given for the RDF-star imperative is the difficulty presented by reified statements.\nIt is proposed that the extra storage space and the increased processing time required by a representation which involves a triple for each statement term justifies introducing a data type to represent statements more compactly and permit more efficient processing.\n\nThis document looks at the processsing required for term reification.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":10,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":21,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":129,"value":"mdfn `In order to compare reified storage alteratives for statement annotation, consider a case of an annotated statement with indefinite extent.[^terms]\nWhere the representation involves some form of typed triple term, this process involves some sort of two component join.\n\\`\\`\\`\n{ x:observation x:assertion x:subject .\n x:subject ?predicate ?object {| x:annotated ?how |} }\n\\`\\`\\`\nWhere the representation permits to collate triples, the interpretation requires no join.\n\\`\\`\\`\n{ _:subject-predicate-object rdf:subject x:subject .\n _:subject-predicate-object rdf:predicate ?predicate .\n _:subject-predicate-object rdf:object ?object .\n _:subject-predicate-object x:annotated ?how }\n\\`\\`\\`\n\nFor these two arrangements, according to the measured performance, the collated process would perform better by either\n${ Math.round(((8.162 - 7.225) / 8.162) * 100) } or\n${ Math.round(((17.029 - 7.225) / 17.029) * 100) }\npercent, depending on whether the annotation requires a two- or three-component join.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":51,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":143,"value":"mdfn `The approach constitutes a way to take advantage of implicit structure which is present in RDF datasets, without requiring preliminary analysis, preprocessor or specific schematic storage.\nWhile explicit attention can be paid to implicit schema in order to inform queries [^pham2015] [^neuman2011], unless that brings didactic benefits, an introspective mechanism just recognizes the schema implicit in the query and follows it is sufficient to take advantage of the standard index locality.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":154,"value":"mdfn`The beneficial effect is on the same order at that which is suggested for \"multi-was join operators\" [^galkin2017], but this process improves on that approach in that, where they describe a multi-stage operation, in which \"once an MJM is completed, the SMJoin operator produces three results as a Cartesian product of sets in the MJM Tail,\" this approach accomplished the entire process in-line when scanning the appropriate statement index, with internal caches reduces to the intermediate results for a single subject terms, rather than the full intermediate \"tail\" caches. \nIt is also similar to Hogan's adaption to \"Leapfrog Triejoin\"[^hogan], but also without the intermediate bindings sets.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":125,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":92,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":13,"value":"uncollated = [[1, 4961692, 1764],\n[2, 4961692, 8162],\n[3, 4961692, 17029],\n[4, 4961692, 26761],\n[5, 4961692, 35782],\n[6, 4961692, 45863],\n[7, 4961692, 54607],\n[8, 4961692, 63048]]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"// first pass, compiling query components\ncollated_1 = [[1, 4961692, 1638],\n[2, 4961692, 6685],\n[3, 4961692, 6744],\n[4, 4961692, 7225],\n[5, 4961692, 7674],\n[6, 4961692, 8093],\n[7, 4961692, 8610],\n[8, 4961692, 8867]]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":42,"value":"// second pass, query components cached\ncollated_2 = [[1, 4961692, 904],\n[2, 4961692, 5977],\n[3, 4961692, 6484],\n[4, 4961692, 6919],\n[5, 4961692, 7469],\n[6, 4961692, 7825],\n[7, 4961692, 8265],\n[8, 4961692, 8545]]\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":19,"value":"import {Plot} from \"@observablehq/plot\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":99,"value":"import { catalog } from \"@lomoramic/blog-catalog\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":118,"value":"import {mdfn, footlist, footnoteCSS} with { footnotes as footnotes } from '@formsandlines/linked-markdown-style-footnotes-with-tooltips'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":120,"value":"footnoteCSS","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 30:"$2f:body"