Coverage report: /development/source/library/org/datagraph/spocq-shard/src/store/rlmdb/bgp-streaming.lisp
| Kind | Covered | All | % |
| expression | 741 | 1798 | 41.2 |
| branch | 89 | 282 | 31.6 |
Key
Not instrumented
Conditionalized out
Executed
Not executed
Both branches taken
One branch taken
Neither branch taken
1
;;; -*- Mode: lisp; Syntax: ansi-common-lisp; Base: 10; Package: org.datagraph.spocq.implementation; -*-3
;;; compile a bgp into a function which matches against an lmdb database and4
;;; performs the nested interation on the results.7
(in-package :org.datagraph.spocq.implementation)9
bgp compilation for simple quad indices contributes solution fields to the algebraic reduction process.11
Field ::= [] | (Solution . Field)12
Solution ::= [] | (Var -> Term) x Solution13
BGP ::= [] | (Pattern x BGP)14
Pattern ::= (Var + Term)*15
BGPProcess ::= match(BGP x Quad*) -> Field16
match(BGP x Quad*) ::= (Pattern x Quad*) . match(BGP x Quad*)18
Pattern x Quad* ::= (Pattern x Quad) + (Pattern x Quad*)20
Pattern x Quad ::= Solution + []22
where a pushed filter is present24
FilteredBGPProcess ::= (BGP + Filter) x Quad* -> Field25
Filter x Solution ::= Solution + []27
(BGP + Filter) x Quad* ::= (BGP x Quad*) x Filter28
Field x Filter ::= (Filter x (Solution + [])) . (Field x Filter)30
where an event filter is present31
1. a statement pattern match yields a solution with an event identifer bound in addition to any other variables in the pattern32
2. the variable is specified with a special statement pattern { ?s dydra:event ?eventID }, for which a statement is 33
never present in the dataset. it indicates that the temporal index is to be used and the respective value bound in34
solutions which share the subject.35
3. the functions event-ordinal, event-timestamp, and event-uuid return the respective value when applied to an event identifier36
4. this predicate must be present in a bgp to cause it to use an event index.37
5. filters which include a single event variable are pushed to the bgp which binds it and used to control the scan.42
(defun revision-max-uuid () (rlmdb:revision-record-uuid (transaction-max-revision-record *transaction*)))43
(defun revision-min-uuid () (rlmdb:revision-record-uuid (transaction-min-revision-record *transaction*)))44
(defun revision-max-timestamp () (rlmdb:revision-record-uuid (transaction-max-revision-record *transaction*)))45
(defun revision-min-timestamp () (rlmdb:revision-record-uuid (transaction-min-revision-record *transaction*)))46
(defun revision-max-ordinal () (transaction-max-revision-ordinal *transaction*))47
(defun revision-min-ordinal () (transaction-min-revision-ordinal *transaction*))49
(unless (fboundp 'temporal-expression-p)50
(defun temporal-expression-p (form)51
(declare (ignore form))54
#+(or) ;; old version sorted55
(defgeneric sort-bgp-statements (repository iteration-patterns initial-bindings)57
"order bgp patterns and filters to prefer constants early and paths late58
ensure that filters and functional predicates follow the respective bindings59
and the filters precede predicates")60
(:method ((repository lmdb-repository) iteration-patterns initial-bindings)61
(labels ((free-variable-p (term)62
(and (variable-p term) (not (member term initial-bindings))))64
(+ (if (free-variable-p (statement-subject stmt)) 1 0)65
(if (free-variable-p (statement-object stmt)) 1 0)66
(if (property-path-p (statement-predicate stmt)) 1 0)))67
(filters-pattern-p (filter stmt)68
"return true iff the filter depends on a variable from the statement"69
(let ((stmt-terms (subseq stmt 1 4))70
(filter-vars (expression-variables filter)))71
(intersection filter-vars stmt-terms)))72
(functional-predicate-p (stmt)73
"return true iff the pattern predicate is a function"74
(let ((predicate (third stmt)))75
(and (symbolp predicate) (fboundp predicate))))76
(path-statement-p (stmt)77
(when (eq (first stmt) 'spocq.a:|triple|)78
(property-path-p (statement-predicate stmt))))79
(statement-precedes-p (s1 s2)80
;; temporal filters go first, then patterns by cost, then functional predicates85
(or (and (functional-predicate-p s2) (not (functional-predicate-p s1)))86
(and (path-statement-p s2) (not (path-statement-p s1)))87
(< (pattern-cost s1) (pattern-cost s2))))89
(and (not (temporal-expression-p (rest s2)))90
(not (functional-predicate-p s1))91
(filters-pattern-p s2 s1)))))95
(or (temporal-expression-p (rest s1))96
(functional-predicate-p s2)97
(not (filters-pattern-p s1 s2))))99
(temporal-expression-p (rest s1))))))))100
(declare (dynamic-extent #'statement-precedes-p))101
(partial-order-sort iteration-patterns #'statement-precedes-p)))102
(:method ((repository bitemporal-repository) iteration-patterns initial-bindings)103
(let ((patterns (call-next-method))106
(loop for pattern in patterns107
do (if (repository-temporal-predicate-p repository (statement-predicate pattern))108
(push pattern bt-patterns)109
(push pattern nbt-patterns)))110
(append bt-patterns nbt-patterns))))112
(defgeneric sort-bgp-statements (repository iteration-patterns initial-bindings)114
"order bgp patterns and filters to prefer constants early and paths late115
ensure that filters and functional predicates follow the respective bindings116
and the filters precede predicates")117
;; first do a dependency-based sort, then reorder for other preferences118
(:method ((repository lmdb-repository) iteration-patterns initial-bindings)119
(when (null (rest iteration-patterns))120
(return-from sort-bgp-statements iteration-patterns))125
(loop for form in iteration-patterns126
do (case (first form)127
(spocq.a:|triple| (push form triples))128
(spocq.a:|filter| (push form filters))130
(log-warn "sort-bgp-statements: unsortable form: ~s" form)131
(push form unsortable))))132
(setf triples (reverse triples))133
(labels ((free-variable-p (term)134
(and (variable-p term) (not (member term initial-bindings))))136
(+ (if (free-variable-p (statement-subject stmt)) 1 0)137
(if (free-variable-p (statement-object stmt)) 1 0)138
(if (property-path-p (statement-predicate stmt)) 1 0)))139
(functional-predicate-p (stmt)140
"return true iff the pattern predicate is a function"141
(let ((predicate (third stmt)))142
(and (symbolp predicate) (fboundp predicate))))143
(path-statement-p (stmt)144
(when (eq (first stmt) 'spocq.a:|triple|)145
(property-path-p (statement-predicate stmt))))147
(let ((cost (pattern-cost stmt))148
(function-p (functional-predicate-p stmt))149
(path-p (path-statement-p stmt)))150
(append `(:cost ,cost)151
(when function-p '(:functional t))152
(when path-p '(:path t)))))154
(flet ((functional-p (annotation) (getf annotation :functional))155
(path-p (annotation) (getf annotation :path))156
(cost-of (annotation) (getf annotation :cost)))157
(or (and (functional-p k2) (not (functional-p k1)))158
(and (path-p k2) (not (path-p k1)))159
(< (cost-of k1) (cost-of k2)))))160
(filters-pattern-p (filter stmt)161
"return true iff the filter depends on a variable from the statement"162
(let ((stmt-terms (subseq stmt 1 4))163
(filter-vars (expression-variables filter)))164
(intersection filter-vars stmt-terms))))165
(setf triples (sort triples #'precedes-p :key #'annotation))168
(setf triples (reverse triples))170
(loop for filter in filters171
collect (cons filter (loop for triple in triples when (filters-pattern-p filter triple) collect triple))))172
(let ((independents ())174
(loop for (filter . filtered-triples) in filter-triples175
do (if (or (null filtered-triples) (temporal-expression-p (rest filter)))176
(push filter independents)177
(push (cons filter filtered-triples) dependents)))178
;; (print (list independents dependents))179
(let* ((result (append180
;; add each triple, preceded by the eventual dependents181
(loop for triple in triples182
append (loop for dependency in dependents183
for (filter . filtered-triples) = dependency184
when (find triple filtered-triples)185
do (setf (rest dependency) nil)188
;; add all independent filters190
;; check that nothing was lost191
(let ((lost (loop for dependent in dependents if (rest dependent) collect dependent)))192
(when lost (warn "lost filter: ~s" lost)))193
;; reorder to put dependents later199
(:method ((repository bitemporal-repository) iteration-patterns initial-bindings)200
(let ((patterns (call-next-method))203
(loop for pattern in patterns204
do (if (repository-temporal-predicate-p repository (statement-predicate pattern))205
(push pattern bt-patterns)206
(push pattern nbt-patterns)))207
(append bt-patterns nbt-patterns))))210
(defmethod rlmdb:map-repository-statements (operator (repository lmdb-repository) quad-pattern &rest args)211
(declare (dynamic-extent args))212
(apply #'rlmdb:map-repository-statements operator (repository-lmdb-repository repository)216
(defmethod rlmdb:map-repository-statements (operator (transaction lmdb-transaction) (quad-pattern t)218
(apply #'rlmdb:map-repository-statements operator (transaction-revision transaction)222
(defmethod rlmdb:map-repository-statements (operator (revision lmdb-revision) (quad-pattern t)227
(apply #'rlmdb:map-repository-statements operator (repository-lmdb-repository revision)229
:revision-predicate (compute-revision-predicate (list :first (revision-min-revision-ordinal revision)230
:last (revision-max-revision-ordinal revision)))234
;;(defparameter *revision-relation* nil)236
(defgeneric resolve-version-constraint (repository expression)237
(:method ((repository lmdb-repository) (expression list))238
(flet ((resolve-revision-designator (designator)241
(string (or (rlmdb:get-revision-ordinal repository designator)242
(spocq.e:revision-not-found-error :identifier designator)))243
((satisfies variable-p) `(rlmdb:term-value ,designator))245
(declare (dynamic-extent #'resolve-revision-designator))246
(map-tree #'resolve-revision-designator expression))))248
(defun extend-triple (triple graph)249
(destructuring-bind (tag s p o . rest) triple250
(declare (ignore tag rest))251
`(spocq.a:|quad| ,s ,p ,o ,graph)))253
(defun compute-term-precedence (triple-pattern sort-order graph-variable event-variable)254
(destructuring-bind (tag s p o c . rest) triple-pattern255
(declare (ignore tag rest))256
(let ((precedence ()))257
(unless (variable-p s) (push :subject precedence))258
(unless (variable-p p) (push :predicate precedence))259
(unless (variable-p o) (push :object precedence))260
(unless (variable-p c) (push :graph precedence))261
(loop for variable in sort-order263
do (pushnew :subject precedence)264
else if (eq variable p)265
do (pushnew :predicate precedence)266
else if (eq variable o)267
do (pushnew :object precedence)268
else if (eq variable graph-variable)269
do (pushnew :graph precedence)270
else if (eq variable event-variable)271
do (push :event precedence))272
(reverse precedence))))273
;;; (compute-term-precedence '(spocq.a:|quad| ?::s <http://example.org/p> ?::value ?::g) '(?::s ?::e) '?::g '?::e)274
;;; (compute-term-precedence '(spocq.a:|quad| ?::s <http://example.org/p> ?::value <urn:dydra:all>) '(?::e ?::s) '?::g '?::e)276
(defgeneric pattern-scan-order (pattern sort-order)277
(:documentation "Given a wild pattern and a sort order, return a list of statement roles278
order as per the sort order")279
(:method ((pattern t) (sort-order list))280
(loop for dimension in sort-order281
for position = (statement-variable-position pattern dimension)285
(defgeneric statement-variable-position (pattern variable)286
(:method ((pattern cons) variable)287
(let ((position (position variable (rest pattern))))288
(when position (aref #(:subject :predicate :object :graph) position))))289
(:method ((pattern spocq:triple) variable)290
(cond ((eq variable (spocq:triple-subject pattern)) :subject)291
((eq variable (spocq:triple-predicate pattern)) :predicate)292
((eq variable (spocq:triple-object pattern)) :object)))293
(:method ((pattern spocq:quad) variable)294
(cond ((eq variable (spocq:quad-subject pattern)) :subject)295
((eq variable (spocq:quad-predicate pattern)) :predicate)296
((eq variable (spocq:quad-object pattern)) :object)297
((eq variable (spocq:quad-graph pattern)) :graph)))298
(:method ((pattern vector) variable)299
(cond ((eq variable (aref pattern 0)) :subject)300
((eq variable (aref pattern 1)) :predicate)301
((eq variable (aref pattern 2)) :object)302
((and (= (length pattern) 4) (eq variable (aref pattern 3))) :graph))))305
(defgeneric compute-lmdb-statement-lambda (repository body &key) )307
(defgeneric compute-bgp-star-lambda (repository body &key) )309
(defmethod compute-bgp-lambda ((repository lmdb-repository) body &rest args &key &allow-other-keys) ;;!!! temporaril310
(declare (dynamic-extent args))311
(when (assoc 'spocq.a:|quad| body)312
(error "invalid bpg pattern: ~s" body))313
(cond ((star-bgp-p body)314
(apply #'compute-bgp-star-lambda repository body args))316
(apply #'compute-lmdb-statement-lambda repository body args))))318
(defmethod compute-lmdb-statement-lambda ((repository lmdb-repository) (body list) &key319
(base-dimensions ()) ; initial solution field variables320
(projection-dimensions (bgp-projected-dimensions body))321
(wildcard-term (repository-wildcard-term repository))322
(default-context-term (repository-default-context-term repository))323
(named-contexts-term (repository-named-contexts-term repository))324
graph ; if in a graph clause, then either a variable or a literal326
(named-graphs (dataset-named-graphs dataset-graphs))327
(default-graphs (dataset-default-graphs dataset-graphs)) 329
(variables (if (variable-p graph)330
(cons graph (expression-variables body))331
(expression-variables body)))332
(dynamic-variables ())333
(transaction *transaction*)334
(trace *compute-bgp-lambda.trace*))335
"Generate a matching operator from a BGP for direct LMBD access path.337
The base logic is the same as for rdfcache-based BGP evaluation:338
- graphs are recognized as for multigraph streaming339
- initial constraints are accepted343
(setf variables (remove-duplicates variables :from-end t))345
(warn "graphs ignored ~s." graphs)346
(log-warn "graphs ignored ~s." graphs))347
;; use the dimensions provided in the call348
;; (setf projection-dimensions (expression-dimensions body))349
(let* (;; if the query had a literal graph term, provide a variable350
(graph-variable (if (variable-p graph) graph '.graph))351
;; note if the graph variable is among the initial solutions352
(initial-solution-graph-variable (find graph base-dimensions))353
(event-pattern (find-if #'(lambda (form) (triple-form-p form) (eq (third form) *predicate.event*)) body))354
(event-variable (if (and event-pattern (variable-p (fourth event-pattern)))355
(fourth event-pattern)356
(cons-variable "event-")))357
;; indicate whether the graph needs to be set on first query358
;; (set-graph-variable (and (variable-p graph) (not initial-solution-graph-variable)))359
;; extract just the expressions to be included in the matching and bindings propagation code360
(iteration-patterns (remove-if-not #'bgp-pattern-form-p (remove event-pattern body)))361
(id (second (assoc 'spocq.a::|id| body)))362
;; extract and consolidate anu declaration clauses363
(declarations (reduce #'append (mapcar #'rest (remove 'spocq.a::|declare| body :test-not #'eq :key #'first))))364
;; get the a-list of variables which were inferred to be related through a sameTerm filter constraint365
;; in order to mirror any binding/setting366
(equivalents (rest (assoc 'spocq.a::|equivalents| body)))368
;;!!! still builds state for triples with paths even though cursors and terms are handled out-of-line369
;; adjust bounds to account for per-thread cursors370
(match-counters (loop for i from 0 below pattern-count collect (gensym "COUNTER")))371
(temp-match-counters match-counters)372
(slice (rest (assoc 'spocq.a:|slice| body)))373
(perform-slice (or (getf slice :start) (getf slice :offset)))374
(projection-variable-count (length projection-dimensions))375
(equivalent-variables (mapcar #'first equivalents))376
(collection-variables (difference-dimensions projection-dimensions equivalent-variables))377
(blank-nodes (expression-blank-nodes iteration-patterns))378
(blank-node-map (loop for node in blank-nodes379
collect (cons node (if (spocq:blank-node-constant-p node)380
(rlmdb:value-term-number node)382
(default-context-term-number (rlmdb:value-term-number default-context-term))383
(named-contexts-term-number (rlmdb:value-term-number named-contexts-term))384
;; track the match nesting; the outer loop only must bind the graph386
(base-bindings base-dimensions)387
(initial-bindings (union-dimensions base-bindings dynamic-variables))388
(term-id-map (make-hash-table :test 'eql))389
(id-term-map (make-hash-table :test 'eql))390
(event-filter (assoc 'spocq.a::|event-filter| body))391
(sort-order (assoc 'spocq.a::|sort-order| body))394
(labels ((intern-if-constant (object)395
(cond ((variable-p object)397
((spocq:blank-node-p object)398
(or (rest (assoc object blank-node-map))399
(error "lost a blank-node: ~a" object)))400
((property-path-p object)401
(rlmdb:intern-property-path object))403
(let ((number (rlmdb:value-term-number object)))404
(setf (gethash number id-term-map) object)405
(setf (gethash object term-id-map) number)))))406
(intern-graph-if-constant (object)407
(cond ((variable-p object)410
(rlmdb:graph-term-number object :allow-all t))))411
(intern-predicate (expression)413
(cons (cons (first expression) (mapcar #'intern-predicate (rest expression))))414
(t (rlmdb:value-term-number expression))))415
(index-statement-p (statement)416
(and (consp statement) (member :test statement)))417
(compute-filter-continuation (triples accumulated-variables)418
(let* ((form (first triples))419
(cc (compute-next-continuation (rest triples) accumulated-variables))420
(test-expression (second form))421
(test-variables (expression-variables test-expression))422
(test-expression `(handler-case (ebv ,test-expression) (error () nil))))424
(let ((test-aliases (loop for variable in test-variables collect (make-symbol (symbol-name variable)))))425
`(if ((lambda ,test-aliases426
(symbol-macrolet ,(loop for variable in test-variables427
for alias in test-aliases428
collect `(,variable (rlmdb:term-number-value ,alias)))429
(trace-bgp bgp.filter ',test-expression ',test-variables (list ,@test-aliases) (list ,@test-variables))433
;; must provide a true result if the filter fails for the scan to continue435
`(if ,test-expression ,cc t))))436
(compute-statement-continuation (triples accumulated-variables)437
(let* ((form (first triples))438
(dimensions (cons graph-variable (statement-dimensions form)))439
;; the first match must always use the graph term - either a constant from/from-named iri440
;; or one of the wild-card, designators default/named/all.441
;; if wild, then the result matters, but if constant, then the result does not.442
;; all subsequent iterations use the result from the first match and do not need to rebind443
(is-first-iteration (= 1 (incf iteration-level)))444
(last-triple-p (null (assoc 'spocq.a:|triple| (rest triples))))445
;; set the graph from each result for the outermost iteration only. that means:446
;; trying w/o this: nb. in contrast to the term-pointer version, which sets the pointer447
;; once only, the term-id based version must retrieve the id each iteration448
(match-result-arguments (loop ;; for term in (cons graph-variable (statement-terms form))449
for term in dimensions450
collect (cond ((or (not (variable-p term)) (member term accumulated-variables))452
((and (eq term graph-variable)453
(not is-first-iteration))454
(gensym "constant-graph"))457
(uniqued-result-arguments (loop for vars on match-result-arguments458
for v in match-result-arguments459
collect (if (member v (rest vars))462
(labels (#+(or) (local-variable-p (v) (member v match-result-arguments))463
#+(or) (wild-variable-p (v) (and (local-variable-p v) (not (eq v graph)))))464
(let* ((match-pattern (cons graph-variable 465
;; replace a variable which was not yet returned from a match466
;; (loop for term in (statement-terms form) collect (if (wild-variable-p term) wildcard-term term))467
(statement-terms form)469
(concrete-match-pattern (let ((graph-term (first match-pattern)))470
(cons graph-term (loop for term in (rest match-pattern)471
collect (if (eq term graph-term)472
`(max 0 ,term) ; cannot pass non-concrete term474
;; replaced with rlmdb call475
;; (match-form `(match-quad-cursor transaction-record ,@concrete-match-pattern *match-target-graph* nil nil))476
(count-form `(count-quad-cursor transaction-record ,@concrete-match-pattern))477
(accumulated-variables (append accumulated-variables (remove-if-not #'symbol-package match-result-arguments)))478
(body (cond ((property-path-p (third match-pattern))479
;; interpret a property path through an out-of-line call to the path matcher480
(let* ((path-continuation (gensym "PATH-CONTINUATION"))481
(ignored-variables (remove-if #'symbol-package uniqued-result-arguments))482
(match-aliases (loop for v in match-result-arguments483
for v-eq = (rassoc v equivalents)486
and do (setf equivalents (remove v-eq equivalents))))487
(continuation-form (compute-next-continuation (rest triples) accumulated-variables)))489
;; constrain aliased variables490
(unless (equal uniqued-result-arguments match-result-arguments)491
(setf continuation-form492
`(if (and ,@(loop for v in match-result-arguments493
for u in uniqued-result-arguments499
#+(or) ; eliminate alias-rebinding in favor of original dimensions500
(setf continuation-form501
`(let ,(loop for (alias . v) in match-aliases502
collect `(,alias ,v))503
,continuation-form)))504
`(flet ((,path-continuation (,@uniqued-result-arguments)505
,@(when ignored-variables `((declare (ignorable ,@ignored-variables))))506
(trace-bgp bgp.pp-matched ,@uniqued-result-arguments)507
(unless (task-active-p *query*)508
(log-debug "bgp premature completion: ~a" *query*)509
(complete-solutions))510
;; when coercing solution graph, restore the match to the initial graphs511
,@(when is-first-iteration512
`((note-graph-reference ,(first uniqued-result-arguments))))513
,(if (and perform-slice last-triple-p)514
;;when here, to return nil to statement mapper515
`(when (minusp (decf solution-offset))518
(declare (dynamic-extent #',path-continuation))519
(trace-bgp bgp.pp-to-match ',concrete-match-pattern)520
(when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))521
(match-property-path transaction ,@concrete-match-pattern #',path-continuation))))523
((active-verb-p (third match-pattern))524
;; interpret a property function through an out-of-line call to funcall-extension525
(let* ((pattern-predicate (third match-pattern))526
(match-result-arguments (active-verb-results pattern-predicate))527
;; no identical result variables (uniqued-result-arguments (unique-result-arguments match-result-arguments))528
(match-parameters (active-verb-parameters pattern-predicate))529
(accumulated-variables (append accumulated-variables (remove-if-not #'symbol-package match-result-arguments)))530
(extension-continuation (gensym "ACTIVE-VERB-CONTINUATION"))531
(ignored-variables (remove-if #'symbol-package match-result-arguments))532
(continuation-form (compute-next-continuation (rest triples) accumulated-variables)))534
`(flet ((,extension-continuation (,@match-result-arguments &rest extra-results)535
(declare (ignore extra-results))536
,@(when ignored-variables `((declare (ignorable ,@ignored-variables))))537
(trace-bgp bgp.active-verb-matched ,@match-result-arguments)538
(unless (task-active-p *query*)539
(log-debug "bgp premature completion: ~a" *query*)540
(complete-solutions))541
,(if (and perform-slice last-triple-p)542
;;when here, to return nil to statement mapper543
`(when (minusp (decf solution-offset))546
(declare (dynamic-extent #',extension-continuation))547
(trace-bgp bgp.extension ',concrete-match-pattern)548
(when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))549
(invoke-active-verb ,pattern-predicate551
#',extension-continuation552
,@match-parameters))))554
((extension-operator-p (third match-pattern))555
;; interpret a property function through an out-of-line call to funcall-extension556
(let* ((extension-continuation (gensym "EXTENSION-CONTINUATION"))557
(ignored-variables (remove-if #'symbol-package uniqued-result-arguments))558
(match-aliases (loop for v in match-result-arguments559
for v-eq = (rassoc v equivalents)562
and do (setf equivalents (remove v-eq equivalents))))563
(continuation-form (compute-next-continuation (rest triples) accumulated-variables)))565
;; constrain aliased variables566
(unless (equal uniqued-result-arguments match-result-arguments)567
(setf continuation-form568
`(if (and ,@(loop for v in match-result-arguments569
for u in uniqued-result-arguments575
#+(or) ; eliminate alias-rebinding in favor of original dimensions576
(setf continuation-form577
`(let ,(loop for (alias . v) in match-aliases578
collect `(,alias ,v))579
,continuation-form)))580
`(flet ((,extension-continuation (,@uniqued-result-arguments)581
,@(when ignored-variables `((declare (ignorable ,@ignored-variables))))582
(trace-bgp bgp.extension-matched ,@uniqued-result-arguments)583
(unless (task-active-p *query*)584
(log-debug "bgp premature completion: ~a" *query*)585
(complete-solutions))586
;; when coercing solution graph, restore the match to the initial graphs587
,@(when is-first-iteration588
`((note-graph-reference ,(first uniqued-result-arguments))))589
,(if (and perform-slice last-triple-p)590
;;when here, to return nil to statement mapper591
`(when (minusp (decf solution-offset))594
(declare (dynamic-extent #',extension-continuation))595
(trace-bgp bgp.extension ',concrete-match-pattern)596
(when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))597
(funcall-extension transaction ,@concrete-match-pattern #',extension-continuation))))599
((index-statement-p form)600
;; this is here, but meaningless as the work in dydra-ndk was never done601
(let* ((options (member-if #'keywordp form))602
(test (getf options :test))603
(index (getf options :index)))604
(declare (ignore index)) ; held in case one wants to reintroduce the uri605
(let ((match-index-form `(match-quad-cursor transaction-record ,@concrete-match-pattern target-graph nil606
',(intern-predicate test))))607
;; indexed pattern match608
`(progn (trace-bgp bgp.cspo-to-match-index ',(nthcdr 3 match-index-form))609
(incf match-requests)610
(let ((%match-cursor nil))611
(when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))613
(if (setf %match-cursor ,match-index-form)615
;; the innermost loop skips past the solution offset616
,@(when (and perform-slice last-triple-p)617
`((when (and (plusp solution-offset)618
(plusp (decf solution-offset (dydra-ndk::quad-cursor-skip %match-cursor solution-offset))))619
(return-from :cursor-loop))))621
(unless (dydra-ndk::quad-cursor-next %match-cursor) (return))623
(incf ,(pop temp-match-counters))624
(let* (,@(loop for term in match-result-arguments625
for uniqued-term in uniqued-result-arguments626
for accessor in '(dydra-ndk::quad-cursor-graph-id627
dydra-ndk::quad-cursor-subject-id628
dydra-ndk::quad-cursor-predicate-id629
dydra-ndk::quad-cursor-object-id)630
if (symbol-package term) collect `(,uniqued-term (,accessor %match-cursor))))631
(declare (ignorable ,@(remove-if-not #'symbol-package uniqued-result-arguments)))632
;; !once! the new bindings are established, compute the next continuation633
,@(when is-first-iteration634
`((note-graph-reference (dydra-ndk::quad-cursor-graph-id %match-cursor))))635
,(let ((form (compute-next-continuation (rest triples) accumulated-variables)))636
(if (equal uniqued-result-arguments match-result-arguments)638
`(if (and ,@(loop for v in match-result-arguments639
for u in uniqued-result-arguments646
(dydra-ndk::free-quad-cursor %match-cursor))))))))648
((or (find-if #'variable-p match-pattern)650
(not (= default-context-term-number rlmdb:*default-context-number*)))651
(destructuring-bind (g s p o) concrete-match-pattern652
(let* ((lmdb-continuation (gensym "LMDB-CONTINUATION"))653
(ignored-variables (remove-if #'symbol-package uniqued-result-arguments))654
(continuation-form (compute-next-continuation (rest triples) accumulated-variables))655
(quad-pattern `(vector ,g ,s ,p ,o))656
(filter (getf (statement-properties form) :filter))657
(temporal-predicate (when filter658
(compute-domain-predicate-form (cons 'spocq.a:|&&| filter) o)))659
(apply-sort-order? (and is-first-iteration (wild-quad-pattern-p form) sort-order)))660
;; constrain aliased variables661
(unless (equal uniqued-result-arguments match-result-arguments)662
(setf continuation-form663
`(if (and ,@(loop for v in match-result-arguments664
for u in uniqued-result-arguments669
;; scan over matched triples670
;; the implementation resolves to the pattern-specific index671
;; which constitutes adjacency appropriate for the pattern and672
;; structure appropriate for the predicate.673
;; anyconstraining properties are passed to the implementation to be interpreted674
`(flet ((,lmdb-continuation (%quad)675
(let ,(loop for var in uniqued-result-arguments677
collect `(,var (cffi:mem-aref %quad 'rlmdb:term-id ,index)))678
,@(when ignored-variables `((declare (ignorable ,@ignored-variables))))679
(trace-bgp bgp.lmdb-matched ,@uniqued-result-arguments)680
(unless (task-active-p *query*)681
(log-debug "bgp premature completion: ~a" *query*)682
(complete-solutions))683
;; when coercing solution graph, restore the match to the initial graphs684
,@(when is-first-iteration685
`((note-graph-reference ,(first uniqued-result-arguments))))686
,continuation-form)))687
(declare (dynamic-extent #',lmdb-continuation))688
;; if the first iteration and the intended sort order can be satisfied689
;; indicate that in the result channel690
,@(when (and apply-sort-order?691
(rlmdb.i::repository-scan-database repository sort-order))692
`((when (channel-p bgp-destination)693
(setf (channel-sort-dimensions bgp-destination)694
',(pattern-scan-order form sort-order)))))695
(trace-bgp bgp.lmdb-to-match ',concrete-match-pattern)696
(when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))697
(rlmdb:map-repository-statements #',lmdb-continuation transaction699
:revision-predicate (compute-revision-predicate transaction)700
,@(when temporal-predicate701
`(:temporal-predicate ,temporal-predicate))702
,@(when apply-sort-order?703
`(:scan-order ',(pattern-scan-order form sort-order))))))))705
;; if all are constant, just count706
(let ((continuation-form (compute-next-continuation (rest triples) accumulated-variables)))707
(unless (equal uniqued-result-arguments match-result-arguments)708
(setf continuation-form709
`(if (and ,@(loop for v in match-result-arguments710
for u in uniqued-result-arguments715
(if (and perform-slice last-triple-p)717
`(progn (incf match-requests)718
(let ((count ,count-form))719
(cond ((and (plusp count)720
(not (plusp (decf solution-offset count))))722
(incf ,(pop temp-match-counters))726
`(progn (incf match-requests)727
(cond ((plusp ,count-form)729
(incf ,(pop temp-match-counters))734
(compute-base-continuation ()735
;; set the next solution row736
(let ((collect-form `(collect-solution ,@collection-variables)))738
`(if (minusp (decf solution-offset))739
(if (and solution-count (minusp (decf solution-count)))745
(compute-next-continuation (triples accumulated-variables)747
(let* ((form (first triples))) ; (triple ?s ?p ?o)750
;; compule a triple/quad into a query/next continuation751
(compute-statement-continuation triples accumulated-variables))753
;; compile a filter into a constraint on the solutions which pass through it754
(compute-filter-continuation triples accumulated-variables))))755
(compute-base-continuation)))756
(compute-collated-continuation (ts-triples accumulated-variables)757
;; the general intent is to collate "entities" - events or resources.758
;; the match/scan process for given patterns varies according to the their specificity,759
;; any event filter, and any sorting.760
;; this compilation step prepares the arguments.761
;; the implementation is associated with the respective index.762
;; at this level, the patterns for (g.s.p.*)+filter combinations are collated.763
;; predicate sets with wild subject and graph are the intended case.764
;; the compilation result dictates the arguments to the mapping operator and the765
;; continuation signature767
;; the purpose of the indices is not to provide a quad pattern solution stream, as768
;; from a general hex index respective pattern specificity, but to arrange for769
;; an optimally ordered stream for certain pattern/event-filter/sort-clause770
;; combinations, such as the following alternatives771
;; - egsp : temporal complex event streaming ce/se/subject/predicate (eg a monitored object772
;; - esgp : temporal subject streaming (eq. a cluster of multi-valued sensors773
;; - sgep : subject temporal streaming (eg. a single multi-valued sensor774
;; - psge : property streaming776
;; whereby the relation is g-s*, that is, for events, a given event comprises multiple subject,777
;; but the subject is present in just one event graph per revision779
;; eg. dimensions . filter . sort781
;; p* . event bounds? . event identifier782
;; given either event predicates or an event id filter,783
;; - if no predicate is given, use all ts predicates784
;; - a sort context indicates which order, by default: egsp786
;; s.p* . event bounds . event identifier787
;; given a specific subject with an event bounds filter or sort by event id788
;; - if the sort context indicates a predicate : spge791
;; e* . event bounds . -792
;; for a specific complex event or all of them over a range793
;; - the sort context indicates precedence : egsp, epgs795
;; g.s*.p* . - . - either s specific simple event or all of a class796
;; a specific simple event or event class over time798
;; - sort and group the patterns by subject.799
;; -- create a continuation with variables to bind the800
;; event(ce) identifier801
;; the graph(se) identifier802
;; the collected subject variables803
;; all respectively collected object variables804
;; -- translate the event filter in to a predicate which closes over any variables805
;; which are free wrt the patterns807
;; in the simpler case of subject-star resources809
;; s.p* . star pattern scans all predicates811
;; arrange for the continuation to accept a vector of keyed term numbers.812
;; this applies when the store does not declare the predicates t be scanned814
;; invoke the repository map operator, capture the results and continue with them815
;; as for other patterns.816
;; any event predicate must be generated here in order to close over matching state,818
;; as the last step, if the event term is bound or used in a819
;; filter, it must be mapped to the respective object's term820
;; number in order to be in the correct domain. the actual value823
(multiple-value-bind (ts-subject ts-predicates ts-variables)824
(loop for (tag s p o) in ts-triples826
collect p into predicates827
collect o into variables828
finally (return (values subject predicates variables)))829
(when *compute-bgp-lambda.debug*830
(print (list :time-series-continuation ts-subject ts-predicates ts-variables)))831
(let* ((lmdb-continuation (gensym "LMDB-TS-CONTINUATION"))832
(is-first-iteration (= 1 (incf iteration-level)))833
(accumulated-variables (append accumulated-variables ts-variables))834
(match-result-arguments ts-variables)835
(uniqued-result-arguments (loop for vars on match-result-arguments836
for v in match-result-arguments837
collect (if (member v (rest vars))840
(ignored-variables (remove-if #'symbol-package uniqued-result-arguments))841
(continuation-form (compute-next-continuation nil accumulated-variables))842
(event-predicate-form (when event-filter843
(compute-domain-predicate-form (cons 'spocq.a:|&&| event-filter)845
(repository-predicate-ids (repository-time-series-predicate-ids repository))846
(result-indexes (loop for predicate in ts-predicates847
for position = (or (position predicate repository-predicate-ids)848
(error "Invalid collection predicate: ~s: ~s"851
(quad-patterns (loop for (tag s p o) in ts-triples852
when (find p repository-predicate-ids)853
collect `(vector ,graph-variable ,s ,p ,o)))855
(unless (equal uniqued-result-arguments match-result-arguments)856
(setf continuation-form857
`(if (and ,@(loop for v in match-result-arguments858
for u in uniqued-result-arguments863
`(flet ((,lmdb-continuation (result-vector)864
(let ((,event-variable (aref result-vector 0))865
,@(when (variable-p graph-variable) `((,graph-variable (aref result-vector 1))))866
,@(when (variable-p ts-subject) `((,ts-subject (aref result-vector 2))))867
;;;!!! this should ust the repositry predicate list as the arrangement868
;;;!!! in order to leave some empty869
,@(loop for var in uniqued-result-arguments870
for index in result-indexes871
collect `(,var (aref result-vector ,(+ 3 index)))))872
(declare (ignorable ,event-variable))873
,@(when ignored-variables `((declare (ignorable ,@ignored-variables))))874
(trace-bgp bgp.lmdb-ts-matched ,@uniqued-result-arguments)875
(unless (task-active-p *query*)876
(log-debug "bgp premature completion: ~a" *query*)877
(complete-solutions))878
;; when coercing solution graph, restore the match to the initial graphs879
,@(when is-first-iteration880
`((note-graph-reference ,(first uniqued-result-arguments))))881
,continuation-form)))882
(declare (dynamic-extent #',lmdb-continuation))883
(trace-bgp bgp.lmdb-ts-to-match ',ts-predicates ',ts-variables)884
;; (when *match-target-graph* (setf ,graph-variable effective-dataset-graphs))885
(rlmdb:map-repository-events #',lmdb-continuation transaction886
(list ,@quad-patterns)887
:revision-predicate (compute-revision-predicate transaction)888
,@(when event-predicate-form889
`(:domain-predicate ,event-predicate-form))890
;; all triples in the set should follow the same pattern891
:term-precedence ',(compute-term-precedence (extend-triple (first ts-triples)896
(event-pattern-p (form)897
(and (triple-form-p form)898
(eq (third form) *predicate.event*)))899
(compute-first-continuation (triples accumulated-variables)900
(if (find 'collated declarations)901
(compute-collated-continuation triples accumulated-variables)902
(compute-next-continuation triples accumulated-variables)))906
(setf body (remove event-filter body))907
(setf event-filter (rest event-filter)))909
(setf body (remove sort-order body))910
(setf sort-order (rest sort-order)))912
;;; if some pattern requires a term which is not found, the bgp has to yield no result.913
(setf iteration-patterns (loop for (tag . spo) in iteration-patterns916
(destructuring-bind (s p o &rest args) spo917
`(,tag ,(intern-if-constant s)918
,(cond ((extension-operator-p p)923
(intern-if-constant p)))924
,(intern-if-constant o)928
;; prefer constants early and paths late929
(setf iteration-patterns (sort-bgp-statements repository iteration-patterns initial-bindings))930
(setf default-graphs (mapcar #'intern-graph-if-constant default-graphs))931
(setf named-graphs (mapcar #'intern-graph-if-constant named-graphs))932
(when (and (null default-graphs) (null named-graphs))933
;; compose the "default dataset"934
(setf default-graphs (list default-context-term-number)935
named-graphs (list named-contexts-term-number)))936
(when (some (complement #'plusp) named-graphs)937
;; permit a singleton abstract graph only938
(assert (null (rest named-graphs)) ()939
"Invalid wildcard dataset named graphs specification: ~a." named-graphs)940
(setf named-graphs (first named-graphs)))941
(when (some (complement #'plusp) default-graphs)942
(assert (null (rest default-graphs)) ()943
"Invalid wildcard dataset default graph specification: ~a." default-graphs)944
(setf default-graphs (first default-graphs)))945
(setf equivalents (loop for (var . value-or-var) in equivalents collect (cons var (intern-if-constant value-or-var))))947
;; allow for just the graph as a variable for literal bgp patterns?948
(when (variable-p graph)949
(setf projection-dimensions (union-dimensions (list graph) projection-dimensions)))951
(let* (;; the interface operator accepts the repository, and optionally an initial spo solution field, and/or a graph sequence952
;; this wraps an operator which iterates outer over the spo field to bind the starting values for those variables 953
;; for each pass and then iterates secondarily over the graph field to perform the pattern matches.955
;; the top-level match form starts with all patterns, _no_ bound variables, and the cursor lists956
;; corresponding to the patterns. not even the solution variables are bound initially, as they may themselves957
;; start out as wild cards.958
#+(or) ;; the initial call no longer includes constant terms959
(base-bindings (if (or graphs (not graph))960
(union-dimensions (list graph-variable) base-dimensions)962
;; this cannot work in this way, as it causes all variables to963
;; be handled as if they are pre-bound, with the consequence, that964
;; they are matched, but never extractedd from the cursor...965
;; (initial-bindings (union-dimensions base-bindings variables))966
(match-invocation-form967
;; the effective process depends on a combination of :969
;; - the query graph term: null, variable, constant, abstract970
;; - the dataset default graphs: null, constant, singleton abstract971
;; normalized above to reflect the default v/s declare composition972
;; - the dataset named graphs: null, constant, singleton abstract973
;; normalized above to reflect the default v/s declare composition974
;; - a propagated solution graph: null, variable976
;; if graph is bound, the bgp is in a graph clause977
;; - if dataset.named-graphs are supplied : they provide the argument for the initial978
;; match and the result serves for successive, nested calls979
;; - allow for propagation to be constrained by the dataset980
;; - allow for - and constrain, a constant graph981
;; - no dataset.named-graphs982
;; no match is possible983
;; no graph indicates the bgp is outside the scope of a graph clause984
;; - if dataset.default-graphs are supplied : match them the first time _and_985
;; also for subsequent matches, but substitute the default graph in the result field986
;; - no dataset.default-graphs987
;; no match is possible989
;; the dataset definition can be a singleton set of a designator for default, named, or all990
;; graphs, in which case the role when matching is the same os that of a concrete graph993
;; in the scope of a graph clause995
;; if the dataset definition includes named graphs, permit propgation, constants, or a dynamic binding996
(cond (initial-solution-graph-variable997
;; propagate form outside the bgp998
`(if (eql ,wildcard-term ,initial-solution-graph-variable)999
(match-patterns ',named-graphs)1000
(when ,(or (eql named-contexts-term-number named-graphs)1001
(eql wildcard-term named-graphs)1002
(if (consp named-graphs)1003
`(member ,initial-solution-graph-variable ',named-graphs)1004
`(eql ,initial-solution-graph-variable ,named-graphs)))1005
(match-patterns ,initial-solution-graph-variable))))1007
`(if (not (eql ,graph ,wildcard-term))1008
(when ,(or (eql named-contexts-term-number named-graphs)1009
(eql wildcard-term named-graphs)1010
(if (consp named-graphs)1011
`(member ,graph ',named-graphs)1012
`(eql ,graph ,named-graphs)))1013
(match-patterns ,graph))1014
(match-patterns ',named-graphs))1015
;; bind aa request argument or match as wild1017
`(let ((argument (query-binding-value ',graph)))1018
(if (integerp argument)1019
;; execute with a request parameter if the dataset graphs permit1020
(when ,(or (eql named-contexts-term-number named-graphs)1021
(eql wildcard-term named-graphs)1022
(if (consp named-graphs)1023
`(member argument ',named-graphs)1024
`(eql argument ,named-graphs)))1025
(match-patterns argument))1026
;; otherwise, start the match unbound1027
(match-patterns ',named-graphs))))1029
(setf graph (intern-graph-if-constant graph))1030
;; match concrete literal or abstract (named, all)1031
(when (or (eql named-contexts-term-number named-graphs)1032
(eql wildcard-term named-graphs)1033
(eql graph named-graphs)1034
(and (consp named-graphs) (member graph named-graphs)))1035
`(match-patterns ,graph)))1037
(error "Invalid graph term: ~s." graph))))1039
;; if the dataset includes no named graph, then a graph term cannot match1040
;; see 13.2.1: the dataset includes no named graphs1042
(cond (default-graphs1043
;; iff merging into the default graph, the match result must be coerced1044
`(match-patterns ',default-graphs ,default-context-term-number))1047
(filtered-p (when (assoc 'spocq.a:|filter| iteration-patterns) t))1048
(triple-matching-form (compute-first-continuation iteration-patterns initial-bindings)))1050
;;(print :added-stringdb-context)1051
(setf triple-matching-form1052
`(rlmdb:with-string-database (bgp-db) ,triple-matching-form)))1054
;; (print (list :match-invocation-form match-invocation-form :graph graph :named-graphs named-graphs))1056
(format *trace-output* "~&*compute-bgp-lambda.trace*~%body ~s~%graph ~s~%named ~s~%default ~s~%initial-solution-graph-variable ~s~%graph-variable ~s"1057
body graph named-graphs default-graphs initial-solution-graph-variable graph-variable))1058
;; the actual query operator takes one of two forms. iff base dimensions are included, it is1059
;; generated to expect a solution field source, and to iterate the entire operator over the field's solutions.1060
;; without base dimensions, it runs autonomously.1061
;; the combination makes it possible to construct query processing both as reduction through bottom-up combination1062
;; and as solution combination, and even as some combination of the two1063
;; where evaluation materialized all intermediate solutions, it did not matter that the reduction order agree1064
;; with the matching order. the intermediate matching results were cached for delayed use as combination arguments.1065
;; where the solution data flows form one operator tot he next, with the intent to limit the space required for1066
;; intermediate fields by streaming results, the contradictory evaluation order would still require buffered1067
;; materialization. for example an expression of the form1069
;; (join (?a ?b ?c) (join (?b ?c) (?c))) 1071
;; would reduce with data flow1073
;; ((?b ?c) . (?c) . (?a ?b ?c))1075
;; but match with data flow1076
;; (?c) -> (?b ?c) -> (?a ?b ?c)1078
;; which entail inverted match orders. the question is, how to enable both?1080
(let* ((all-bgp-variables1081
;; look for a dynamic binding for all variables in the bgp1082
;; this allows to specify dynamic variables retrospectively, but it may introduce1083
;; an issue related to extracting them from the cursor1084
(set-difference variables base-bindings))1086
`(lambda (bgp-destination ,@(when base-dimensions '(source)))1087
(declare (optimize ,@*field-optimization*))1088
(assert-argument-types bgp-match1089
(bgp-destination (or channel function))1090
,@(when base-dimensions '((source (or channel function)))))1091
(let* ((repository-id (repository-id *repository*))1092
(revision-id (repository-revision-id *task*))1093
(transaction *transaction*)1094
(transaction-record (transaction-record transaction))1095
(*thread-operations* (cons (list 'spocq.a:|bgp| ',body) *thread-operations*))1099
(result-page-length (channel-page-length bgp-destination))1100
(result-index *field-page-length*)1103
(graph-ids-read (make-term-id-cache :single-thread t))1104
(*wildcard-identifier* ,wildcard-term)1105
(*default-context-identifier* ,default-context-term-number)1106
,@(loop for var in match-counters collect `(,var 0))1107
;; the original formulation looked for dynamic bindings for all variables1108
;; which were specified as dynamic in the first request but provided to1109
;; be accepted from a propagation source1111
,@(loop for var in (intersection (set-difference dynamic-variables base-bindings) variables)1112
collect `(,var (query-binding-term-number ',var)))1113
,@(loop for var in all-bgp-variables1114
collect `(,var (query-binding-term-number ',var)))1115
,@(loop for (nil . var) in blank-node-map1116
when (variable-p var)1117
collect `(,var ,wildcard-term))1118
,@(when perform-slice1119
(destructuring-bind (&key (start 0) (offset start) end (count (when end (- end offset))))1121
`((solution-offset ,offset)1122
(solution-count ,count))))1124
(declare (ignorable repository-id revision-id transaction-record) ; if just paths1126
,@(when all-bgp-variables ; a variable may have been folded into a constant1127
`((declare (ignorable ,@all-bgp-variables))))1129
(labels ((coerce-to-term-id (term-number)1130
(typecase term-number1131
(fixnum term-number)1132
(t (log-warn "bgp match result not a term number: ~s." term-number)1134
(collect-solution ,collection-variables1135
(trace-bgp bgp.match.collect-solution ,@collection-variables)1136
(case *match-target-graph*1139
(t (log-warn "anomalous match target graph: ~s." *match-target-graph*)))1141
,(if projection-dimensions1142
`(let ,(loop for (alias . equivalent) in equivalents ; bind left-over constants1143
collect (list alias equivalent))1144
(next-solution-location)1145
(locally (declare (type (simple-array fixnum (* ,projection-variable-count)) result-page)1146
(type fixnum result-index)1147
(ftype (function (t) fixnum) coerce-to-term-id)1148
(optimize ,@*field-optimization*))1149
(setf ,@(loop for var-index from 01150
for variable in projection-dimensions1151
nconc `((aref result-page result-index ,var-index)1152
(coerce-to-term-id ,variable))))))1153
'(next-solution-location))1155
(next-solution-location ()1156
;; return a page (possible newly created) and the next free location in that page1157
(when (>= (incf result-index) result-page-length)1158
(unless (check-query-status)1159
(complete-solutions))1160
(when result-page (put-result result-page))1161
(setf result-page (new-field-page bgp-destination result-page-length ,projection-variable-count)1163
(values result-page result-index))1164
(complete-solutions ()1165
(trace-bgp bgp.match.complete-solutions result-count)1166
(incf *match-requests* match-requests)1167
(incf *match-responses* match-results)1168
(when (plusp (hash-table-count graph-ids-read))1169
(with-locked-cache ((transaction-read-graph-ids transaction))1170
(loop for id being each hash-key of graph-ids-read1171
do (setf (transaction-graph-id-read transaction id) t))))1172
(log-debug "bgp matches+counts: ~s: requests: ~s, matches: (~s ~s), solutions: ~s"1173
repository-id match-requests match-results (list ,@match-counters) result-count)1175
(let ((page-result-count (1+ result-index)))1176
(when (< page-result-count result-page-length)1178
(adjust-page result-page (list page-result-count ,projection-variable-count)))))1179
(put-result result-page))1180
(complete-field bgp-destination)1181
(incf-stat *solutions-constructed* result-count)1182
(return-from :bgp-match result-count))1184
(trace-bgp bgp.put bgp-destination ',projection-dimensions page)1185
(put-field-page bgp-destination page)1186
(unless (task-active-p *query*)1187
(complete-field bgp-destination)1188
(return-from :bgp-match result-count)))1189
(note-graph-reference (graph)1190
(unless (eql graph last-graph-id)1191
(setf last-graph-id graph)1192
(setf (gethash graph graph-ids-read) t))))1193
(trace-bgp bgp.start ',id (task-id *query*)1194
repository-id revision-id ',projection-dimensions)1195
;; (print (list :bgp.start ',id (task-id *query*) repository-id revision-id ',projection-dimensions))1196
(incf-stat *algebra-operations*)1197
(trace-bgp bgp.repository *repository* repository-id revision-id :dataset ',dataset-graphs)1198
(if ,(if (find-if #'property-path-p body :key #'third) t 'revision-id)1199
;; unless there are paths present (actually zero-length paths is the issue)1200
;; require an id to perform the query. otherwise there can be no result - skip it1202
; push this logic to the outer-most match call to pass1203
; the entire graph set as the context argument1204
,(let ((iterate-over-graphs `(flet ((match-patterns (effective-dataset-graphs &optional (*match-target-graph* nil)1205
,@(when (eq graph-variable '.graph)1206
'(&aux (.graph *wildcard-identifier*)))1208
;; effective-dataset-graphs is the initial match set1209
;; *match-target-graph*, if bound indicates to coerce the graph term to that1210
;; if the graph is coerced, subsequent matches re-use the original set1211
;; this manages, eg. the case where a set of graphs is 'merged' into the1212
;; default graph, but the result must indicate the default graph only1213
(trace-bgp bgp.next-graph effective-dataset-graphs *match-target-graph*)1214
(let ((*match-property-path-context* effective-dataset-graphs))1215
(when (= *wildcard-identifier* ,graph-variable)1216
(setf ,graph-variable effective-dataset-graphs))1217
,triple-matching-form)))1218
,match-invocation-form)))1219
(when *compute-bgp-lambda.debug*1220
(pprint iterate-over-graphs))1222
`(do-pages (page source)1223
,(let ((macros (loop for variable in base-dimensions1225
collect `(,variable (aref page page-index ,i)))))1226
`(locally (declare (type (simple-array fixnum (* ,(length base-dimensions))) page)1227
(optimize ,@*field-optimization*))1228
(assert (and (typep page '(simple-array fixnum))1229
(= (array-dimension page 1) ,(length base-dimensions)))1231
"Invalid propagated page: ~s" page)1232
(trace-data bgp-match.dequeue bgp-destination ',base-dimensions page (term-value-field page))1233
(loop for page-index from 0 below (array-dimension page 0)1234
do (symbol-macrolet ,macros1235
,iterate-over-graphs)))))1236
iterate-over-graphs))1237
(trace-bgp bgp.complete-after-graph-iteration)1238
(complete-solutions))1239
(progn (trace-bgp bgp.suppress repository-id)1240
(log-debug "suppress query for empty repository: ~a" repository-id)1241
(complete-solutions))))1242
(log-warn "incomplete bgp: ~s." ',id)1244
(log-trace "query [~a] bgp [~a] lambda: ~s"1245
(task-id *query*) id query-lambda)1246
(values query-lambda1247
projection-dimensions))))))1249
(defmethod compute-repository-pattern-partitions1250
((repository time-series-repository) patterns)1251
"A time-series repository collates results from graph patterns which pertain to1252
its declared predecates. Statements which involve those predicates are isolated1253
into paritions which share subject."1254
(let ((triples (remove-if-not #'triple-form-p patterns))1255
(non-triples (remove-if #'triple-form-p patterns)))1256
;; partition based on three interacting indicators1257
;; -- a statement pattern with a |urn:dydra|:|event| predicate1258
;; -- statements with declared event predicates1259
;; -- an event filter1261
;; separate those triples which involve a constant time-series predicate and a variable object.1262
;; the ts index keys omit the object values and substitute a event designator term1263
;; (ordinal, uuid, or timestamp) which is understood as the complex event id.1264
;; when matching, the event id may be constant or variable depending on the term1265
;; which appears in the event statement pattern and/or the boounds expressed in any event filter1266
;; the graph and the subject may be constant or variable.1267
;; consistent with rsp, the graph identifes the "simple event object", or sample,1268
;; while the event designator identifies the complex event1269
;; - http://ontologydesignpatterns.org/wiki/Submissions:EventProcessing1270
;; - https://www.w3.org/community/rsp/wiki/RDF_Stream_Models1271
;; different patterns yield different match processes and different binding streams.1272
;; in any case, the basic partition is those which are present in the time-series indices.1274
;; the partition process expects at most one set of patterns which pertains to a given subject1275
;; and produces one of1276
;; - no partition, if no event indicator is present1277
;; - a two-statement partition with the event statement pattern and a wild pattern1278
;; - a multi-statement partition with the event pattern and those which include egent predicates.1279
(loop with collections = (make-hash-table)1280
for triple in triples1281
for (tag . spo) = triple1282
if (or (and (repository-time-series-predicate-p repository (second spo))1283
(variable-p (third spo)))1284
(eq (second spo) *predicate.event*))1285
do (push triple (gethash (first spo) collections))1286
else collect triple into other-triples1287
finally (return (append (loop for partition-triples being each hash-value of collections1288
collect (cons '(spocq.a::|declare| collated) (append non-triples partition-triples)))1289
(call-next-method repository other-triples))))))1291
;;; domain index support1293
(defun statement-mapping-properties (statement)1294
(loop for (keyword value) on (statement-properties statement)1295
append (statement-mapping-property keyword value)))1297
(defgeneric statement-mapping-property (keyword value)1298
(:method ((keyword (eql :filter)) (value t))1300
(:method ((keyword t) (value t))1303
(defgeneric annotate-bgp-statements (repository body)1304
(:documentation "Annotate the bgp statement to reflect the repository indices.1305
Where the repository implements domain indices pertinent to present filter constraints,1306
extract them merge them into statements as annotations to permit the respective map1307
operator to tailor its match/scan process to them.")1308
(:method ((repository t) (body list))1309
"The base method returns the body unchanged."1312
(:method ((repository lmdb-temporal-repository) (body list))1313
"If the target is a temporal repository, migrate any filter in which one1314
variable is constraind by constants to that statement pattern which binds1316
Other variables may be present, but not in relation to constants.1317
If the filter is an expression list or a conjunction, attempt to deconstruct it."1318
;; that property is present in a statement, migrate the expression1319
(setf body (copy-tree body))1320
(let ((temporal-statements ; index temporal statement patterns by variable object1321
(loop for form in body1322
when (and (triple-form-p form)1323
(variable-p (statement-object form))1324
(repository-temporal-predicate-p repository (statement-predicate form)))1325
collect (cons (statement-object form) form)))1326
(unrelated-filters ()))1327
(labels ((migrate-form (variable form)1328
;; push any components possible onto the respective triple1329
;; return the remaining filter or nil if no clause remains1330
(let ((statement (rest (assoc variable temporal-statements))))1332
(push form (getf (statement-properties statement) :filter)))))1333
(associate-filter (filter &aux (expression (second filter)))1334
(case (first expression)1336
(loop for form in (rest expression) do (associate-filter form)))1337
((spocq.a:! spocq.a:!=)1338
(push expression unrelated-filters))1339
((spocq.a:< spocq.a:> spocq.a:=)1340
(destructuring-bind (a1 a2) (rest expression)1341
(cond ((migrate-form a1 expression))1342
((migrate-form a2 expression))1344
(push expression unrelated-filters)))))1346
(loop for form in (rest expression) do (associate-filter form)))1348
(push expression unrelated-filters)))))1350
(append (loop for statement in body1351
if (triple-form-p statement)1353
else if (filter-form-p statement)1354
do (associate-filter statement)1355
else collect statement)1356
(loop for form in unrelated-filters1357
collect `(spocq.a:|filter| ,form))))1358
(call-next-method repository body)))))1361
(:documentation "domain predicates"1362
"Indices which include a domain value in the index record are intended1363
to support interval retrieval by scanning within bounds.1364
This require predicate combine tests for term-id->term bindings and1365
variables bound directly to domain values.1366
In order to permit variant values, they also use local variables which1367
convert between temporal object and timeline locations as well as1368
various uuid forms.")1370
(defun compute-domain-predicate-form (expression domain-variable)1371
"given an expression and the respective domain variable, return a form1372
which constructs a predicate function object which captures the min/max bounds1373
for the variable as well as a test function which accepts the variable as1374
its single argument."1377
(variables (expression-variables expression))1378
(other-variables (remove domain-variable variables))1380
(assert (member domain-variable variables) ()1381
"Domain expression must involve variable: ~a: ~a"1382
domain-variable expression)1383
(labels ((extract-bounds (form)1387
(loop for form in (rest form) do (extract-bounds form)))1390
(unless (assoc 'spocq.a:!= macros)1391
(push '(spocq.a:!= (v1 v2) (list 'not (list 'domain-= v1 v2))) macros)))1393
(unless (assoc 'spocq.a:< macros)1394
(push '(spocq.a:< (v1 v2) (list 'domain-< v1 v2)) macros)))1396
(unless (assoc 'spocq.a:<= macros)1397
(push '(spocq.a:<= (v1 v2) (list 'domain-<= v1 v2)) macros)))1399
(let ((constraint (relation-constraint form)))1400
(when constraint (push constraint min) (push 'spocq.a:> op)))1401
(unless (assoc 'spocq.a:> macros)1402
(push '(spocq.a:> (v1 v2) (list 'domain-> v1 v2)) macros)))1404
(let ((constraint (relation-constraint form)))1405
(when constraint (push constraint min) (push 'spocq.a:>= op)))1406
(unless (assoc 'spocq.a:>= macros)1407
(push '(spocq.a:>= (v1 v2) (list 'domain->= v1 v2)) macros)))1409
(let ((constraint (relation-constraint form)))1410
(when constraint (push constraint min) (push 'spocq.a:= op)))1411
(unless (assoc 'spocq.a:= macros)1412
(push '(spocq.a:= (v1 v2) (list 'domain-= v1 v2)) macros)))1413
((spocq.a:&& spocq.a:|\|\||)1414
(loop for form in (rest form) do (extract-bounds form)))))1416
(relation-constraint (form)1417
(cond ((eq (second form) domain-variable) (third form))1418
((eq (third form) domain-variable) (second form)))))1419
(setf expression (extract-bounds expression))1420
`(let ,(loop for variable in other-variables1421
collect `(,variable (rlmdb:term-number-value ,variable)))1422
(multiple-value-bind (min op)1423
(domain-lower-bound (list ,@min) ',op)1424
(make-domain-predicate1426
:test (lambda (,domain-variable)1428
(handler-case (ebv ,expression) (error () nil))))))))))1430
(defgeneric domain-< (v1 v2)1431
(:method ((v1 integer) (v2 spocq:temporal-location))1432
(< v1 (temporal-timeline-location v2)))1433
(:method ((v1 spocq:temporal-location) (v2 integer))1434
(< (temporal-timeline-location v1) v2))1435
(:method ((v1 t) (v2 t))1437
(defgeneric domain-<= (v1 v2)1438
(:method ((v1 integer) (v2 spocq:temporal-location))1439
(<= v1 (temporal-timeline-location v2)))1440
(:method ((v1 spocq:temporal-location) (v2 integer))1441
(<= (temporal-timeline-location v1) v2))1442
(:method ((v1 t) (v2 t))1443
(spocq.e:<= v1 v2)))1445
(defun domain-> (v1 v2)1447
(defun domain->= (v1 v2)1450
(defgeneric domain-= (v1 v2)1451
(:method ((v1 integer) (v2 spocq:temporal-location))1452
(= v1 (temporal-timeline-location v2)))1453
(:method ((v1 spocq:temporal-location) (v2 integer))1454
(= (temporal-timeline-location v1) v2))1455
(:method ((v1 t) (v2 t))1458
(defun domain-lower-bound (values operators)1459
(loop with value = (pop values)1460
with operator = (pop operators)1461
for next-value in values1462
for next-operator in operators1463
when (or (domain-< next-value value)1464
(and (eq next-operator 'spocq.a:>)1465
(domain-= next-value value)))1466
do (setf operator next-operator1468
finally (return (values value operator))))1470
(defclass domain-predicate (c2mop:funcallable-standard-object)1471
((min :initarg :min :initform nil1472
:reader domain-predicate-min)1473
(min-op :initarg :min-op :initform nil1474
:reader domain-predicate-min-op)1475
(test :initarg :test :initform nil1476
:reader domain-predicate-test))1477
(:metaclass c2mop:funcallable-standard-class))1479
(defun make-domain-predicate (&rest args)1480
(declare (dynamic-extent args))1481
(apply #'make-instance 'domain-predicate args))1483
(defmethod initialize-instance ((instance domain-predicate) &rest args1485
(declare (ignore max))1486
(assert (typep test '(or function null)) ()1487
"domain-predicate: invalid test function: ~s" test)1488
(apply #'call-next-method instance1492
(spocq:temporal-location (temporal-timeline-location min)))1494
(c2mop:set-funcallable-instance-function instance (or test (constantly t))))1496
(defun domain-predicate-p (data)1497
(typep data 'domain-predicate))1501
(compute-domain-predicate-form '(spocq.a:|\|\|| (spocq.a:> ?::|y| 2) (spocq.a:< ?::|y| 3))1503
(let ((tp (make-instance 'domain-predicate :test (lambda (v) (= v 3))))) (funcall tp 2))1504
(let ((tp (make-instance 'domain-predicate :test nil))) (funcall tp 2))1508
(defun compute-temporal-predicate-lambda (expression)1509
"walk the expression to extract all variables other then ?::timeSeries.1510
return a predicate which accepts a time series identifier1511
- rebind variables to resolved values1512
- bind constants to resolved values1513
- evaluate the expression"1515
(let ((constants ())1518
(labels ((replace-expressions (form)1521
(destructuring-bind (op &optional arg1 arg2) form1523
((> >=) (when (eq arg1 '?::|timeSeries|) (setf first arg2)))1524
((<= <) (when (eq arg2 '?::|timeSeries|) (setf first arg1)))))1527
(cond ((eq form '?::|timeSeries|)1528
'time-series-identifier)1529
((eq (symbol-package form) *variable-package*)1530
(push `(,form (resolve-time-series-identifier ,form))1536
(let ((variable (gensym "tsid-value-")))1537
(push `(,variable (resolve-time-series-identifier ,form))1540
(setf expression (map-tree #'replace-expressions expression))1541
(values `(let (,@constants ,@variables)1542
(lambda (time-series-identifier)1546
;;; (compute-temporal-predicate-lambda '(and (< ?::|timeSeries| #@"2020-01-01T00:00:00") (>= ?::|timeSeries| ?::tsStart)))1548
(defclass revision-predicate (c2mop:funcallable-standard-object)1549
((min :initarg :min :initform nil1550
:reader revision-predicate-min)1551
(min-op :initarg :min-op :initform nil1552
:reader revision-predicate-min-op)1553
(test :initarg :test :initform nil1554
:reader revision-predicate-test))1555
(:metaclass c2mop:funcallable-standard-class))1557
(defmethod initialize-instance ((instance revision-predicate) &rest args1559
(declare (ignore max))1560
(assert (typep test '(or function null)) ()1561
"revision-predicate: invalid test function: ~s" test)1562
(apply #'call-next-method instance1567
(c2mop:set-funcallable-instance-function instance (or test (constantly t))))1569
(defgeneric compute-revision-predicate (transaction)1571
(:method ((transaction lmdb-transaction))1572
(let ((first (transaction-min-revision-ordinal transaction))1573
(last (transaction-max-revision-ordinal transaction))1574
(highest (transaction-highest-revision-ordinal transaction)))1575
(compute-revision-predicate (list :first first :last last :highest highest))))1576
(:method ((bounds list))1577
(destructuring-bind (&key first (last first) highest1578
(element-size (load-time-value (cffi:foreign-type-size 'revision-ordinal))))1580
(flet ((test-visibility (%vector byte-count)1581
;; (print (list byte-count element-size highest))1582
(or (null byte-count) (= byte-count 0)1583
(let ((visibility-count (/ byte-count element-size)))1584
(or (and (oddp visibility-count) highest (>= first highest)) ; head, just the last revision matters1585
(rlmdb.i::%test-visibility-range first last %vector visibility-count))))))1586
(make-instance 'revision-predicate :min first :test #'test-visibility)))))1588
(defun revision-predicate-p (data)1589
(typep data 'revision-predicate))1594
(defmethod repository-query-by-verb ((continuation t) (transaction lmdb-transaction) context subject (predicate integer) object)1595
"if the predicate is an integer, it as a term number - perform the actual match and upon success1596
invoke the continuation with the concrete terms under cycle constraints"1597
(cond ((null (transaction-parent-p transaction))1598
(trace-paths "pp.rqbv.suppress : query-by-verb for empty repository: ~a" transaction)1601
(trace-paths "pp.rqbv.lmdb : ~a(~a) ~a(~a) ~a(~a) : ~a,~a~%"1602
(format-term-number-object subject) subject1603
(format-term-number-object predicate) predicate1604
(format-term-number-object object) object1605
*match-target-graph*1606
*match-property-path-context*)1607
(when *match-target-graph* (setf context *match-target-graph*))1608
(when *match-property-path-context* (setf context *match-property-path-context*))1609
(flet ((continue-with-quad (%quad)1610
(call-path-continuation continuation1611
(or *match-target-graph* (%quad-context %quad))1612
(%quad-subject %quad)1613
(%quad-predicate %quad)1614
(%quad-object %quad))1616
(declare (dynamic-extent #'continue-with-quad))1617
(rlmdb:map-repository-statements #'continue-with-quad transaction1625
(defmethod repository-match-matrix ((transaction lmdb-transaction) matrix context subject predicate object1627
"generate a new solution matrix for the statements which match the argument pattern.1628
If the context is not yet interned, intern all terms and recurse. should some term not be present, then return1629
a null matrix. Associate a (possible sparse) dimension list with the result to indicate which columns1632
(assert (typep start '(integer 0)) () "repository-match-matrix: invalid start: ~s" start)1633
(assert (or (null end) (and (typep end '(integer 0)) (>= end start))) () "repository-match-matrix: invalid end: ~s" end)1634
(let* ((contexts (if (consp context) context (list context)))1637
(limit (when end (- end start))))1638
(flet ((match-context (context)1639
(flet ((continue-with-quad (%quad)1640
(cond ((and limit (zerop limit))1643
(push %quad results)1644
(incf result-count))1647
(declare (dynamic-extent #'continue-with-quad))1648
(rlmdb:map-repository-statements #'continue-with-quad transaction1649
(vector context subject predicate object)))))1650
(loop for context in contexts1651
until (and limit (zerop limit))1652
do (match-context context))1653
(let ((%matrix (rdfcache:make-matrix result-count 4)))1654
(declare (type cffi-sys:foreign-pointer %matrix))1655
(loop for %quad in results1656
for offset from (* (1- result-count) 4) downto 01657
do (rlmdb.i::copy-quad-record %quad %matrix offset))1658
(values %matrix result-count)))))1660
(defmethod repository-matrix-field ((transaction lmdb-transaction) context subject predicate object1661
&key (start 0) end dimensions (wild-blank-nodes-p t))1662
(declare (ignore context subject predicate object start end dimensions wild-blank-nodes-p))1666
(defmethod map-repository-statements (function (transaction lmdb-transaction) subject predicate object context &key1667
(wildcard-term (repository-wildcard-term transaction)) (offset 0) count)1668
(flet ((continue-with-quad (%quad)1670
(%quad-context %quad)1671
(%quad-subject %quad)1672
(%quad-predicate %quad)1673
(%quad-object %quad)))1674
(continue-with-sliced-quad (%quad)1675
(cond ((<= (decf offset) 0)1676
;; continue until any limit is reached1677
(when (or (null count) (>= (decf count) 0))1679
(%quad-context %quad)1680
(%quad-subject %quad)1681
(%quad-predicate %quad)1682
(%quad-object %quad))))1684
(declare (dynamic-extent #'continue-with-quad #'continue-with-sliced-quad))1685
(rlmdb:map-repository-statements #'continue-with-quad transaction1686
(vector (or context (repository-default-context-term-number (transaction-repository transaction)))1687
(or subject wildcard-term)1688
(or predicate wildcard-term)1689
(or object wildcard-term)))))1691
(defmethod map-repository-statements ((operator t) (index rlmdb:index-database) subject predicate object context &rest args)1692
(declare (dynamic-extent args))1693
(flet ((continue-with-quad (%quad)1695
(%quad-context %quad)1696
(%quad-subject %quad)1697
(%quad-predicate %quad)1698
(%quad-object %quad))))1699
(declare (dynamic-extent #'continue-with-quad))1700
;; no nil==wildcard support . this is intended to be used from describe, where everything is known1701
(apply #'rlmdb::map-index-statements #'continue-with-quad index1702
(vector context subject predicate object)1705
(defmethod transaction-call-with-matched-terms (op (transaction lmdb-transaction) subject predicate object &key1706
(wildcard-term (repository-wildcard-term *transaction*))1707
(context wildcard-term)1708
(target-graph nil) (ordered-p nil))1709
(declare (ignore ordered-p))1710
(flet ((continue-with-quad (%quad)1712
(or target-graph (%quad-context %quad))1713
(%quad-subject %quad)1714
(%quad-predicate %quad)1715
(%quad-object %quad))))1716
(declare (dynamic-extent #'continue-with-quad))1717
(rlmdb:map-repository-statements #'continue-with-quad *transaction*1718
(vector (or context (repository-default-context-term-number (transaction-repository *transaction*)))1719
(or subject wildcard-term)1720
(or predicate wildcard-term)1721
(or object wildcard-term)))))