Coverage report: /development/source/library/org/datagraph/spocq-shard/src/store/rdfcache/decimated-pattern.lisp
| Kind | Covered | All | % |
| expression | 2 | 1922 | 0.1 |
| branch | 0 | 208 | 0.0 |
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
(in-package :org.datagraph.spocq.implementation)6
;;; (load (compile-file #P"/development/source/library/org/datagraph/spocq/src/store/decimated-pattern.lisp"))8
(:documentation "Modular BGP manipulation"9
"A basic graph pattern (BGP) comprises a set of statements to be10
matched against the content of the store to yield either a boolean indication, whether11
the denoted sub-graph exists, or the set of bindings for which the sub-graph exists.12
Each bgp form comprises14
- triple statement patterns (s p o)15
- implicit quad form derived from graph form scope18
The standard semantics are, that the forms effect a null-suppressing natural join among the19
solution fields whereby the process excludes any solutions which do not satisfy the filters.21
One implementation mechanism is to interpret each statement pattern individually, to generate the22
respective solution field, apply any filter for which the solution binds all variables and23
then combine resulting fields accoding to the 'and' group operator, which produces a join.24
The combination order is arranged based on the respective and combined selectvity, to intend25
to limit the field size growth.26
An alternative is use the selectivity, order those which share27
dimensions such that those with the smallest expected solution counts come first and then interpret the28
statements in order while propagating bindings from the preceeding statements to 29
variables in successors to constrain their matches.31
The trade-off is between the space and time to perform a join between two solutions and32
the time required to perform successive matches. If the match rate is low - whether because of the communications33
delays to the data or because of the size of the repository, then the total time for34
repeated matches in succeeding statements will surpass the time for a combination against the35
scanned solutions field which results from the same pattern without the constraints.37
The constraint propagation mechanism can be implemented through dynamically compiled, iteratively38
nested lexical environments, but that makes it difficult to subsequently reorder the39
pattern evaluation or to change the strategy between propagated matching and joined scanning40
in response to the actual solution field sizes.41
The 'decimated pattern' approach implementes each pattern as an opportunistic operator in two 42
phases. an initial phase accepts a predecessor field and, in general, dependent upon the field size and43
contingent match and scan rate for the specific repository,44
either performs a match of the respective pattern with no qualification beyond that45
from the original query, followed by a scan-based combination with the argument or46
it transforms the argument field into47
additional constraints on its pattern for successive matches.48
Filters associate with the statement patterns in the same manner as49
propagated matching or joined scanning, but, as the order is not static, the filter implementation50
is computed on-demand to reflect the solution field dimensions at the point of application.52
In addition to the join which is inherent in the bgp and the filter which results from pushed53
filters, the decimated approach introduces operators to implement54
the logical implications of schema declarations:56
- and : computes the natural join. this provides the standard bgp semantics57
- or : passes the first non-null constituent solution field and suppresses all others58
- not : intended to operate constrained by an initial field, in which situation, it passes each solution59
for which the constrained immediate match fails. when applied in isolation, it yields a unit table60
for a pattern which fails to match and a null result field for one which does.61
- xor : similar to or, but passes solution succeeds only if there is exactly one.62
- sum : accumulate all matched solutions (as union), but lower-level requiring constant dimensionality64
The original standard bgp form is wrapped with an 'and' prior to processing.66
the combination operators are implemented as independent interpreter steps with the respective67
semantics. each expects an initial state (nil, a field array, or a generator controller function),68
and one or more pattern matchers. depending on the relative size of the initial field and the69
pattern matcher's sensitivity, the matcher is invoked either to propagate or to scan. in the former case,70
the field is supplied to the matcher and each individual solution is combined as per operator semantics71
in the latter case, no initial solutions are supplied to the matcher and its result field is combined72
with the initial field as per operator semantics.74
The general control structure is that each operator node in a bgp expression compiles75
into a function of two required arguments - the destination/continuation which accepts result pages76
and the repository transaction. In addition, the function accepts keyword arguments for79
- plus each variable name in the pattern81
the top-level operator is invoked by the agp generator function with a continuation which82
introduces the result field into a queue. each operator passes control to83
its arguments assembling the result field according to the respective operator semantics.84
This serializes the processing of each bgp. Any desired parallelism can be introduced86
- splitting the patterns from a bgp among explicit legs of a join87
- by distributing the matching for a single statement pattern among store shards88
- by reintroducing an asynchronous connection between the match thread and the combiniation89
thread, eg the merge-join operation which combines statements. this makes page storage more complex,90
as they would have to be cloned prior to queueing92
add the channel fd to the field.93
when the expected operation time exceeds a limit, create or claim a thread,94
put its result channel in the field,95
clone the field, keep the copy to return, give the original to the additional thread,96
and task it to execute the operation in the task context.98
upon completeion, remove the channel from the field,99
record the operation time100
and the thread start-up delay for future comparison103
sip cannot just run process-pattern, that would generate too many spurious fields.105
- change matrix match to accept a matrix which it extends106
- change match/scan choice to compute two combined function in the match case107
the first extracts values for constriant dimensions from the base field and calls the second108
the second binds them for the matrix match call with a growing matrix109
the final result is the matrix encapsulates in a field114
(defgeneric pattern-selectivity (pattern)115
(:documentation "Follows Stocker (tr ifi-2007.03), as 'the fraction of triples satisfying the pattern'."))117
(defgeneric pattern-arity (pattern)120
(defgeneric pattern-arity-and-selectivity (pattern)123
(defgeneric pattern-count (pattern)126
(defgeneric pattern-propagated-arity (pattern)129
(defgeneric pattern-propagated-arity-and-selectivity (pattern)132
(defgeneric pattern-precedes (pattern1 pattern2)135
(defgeneric process-pattern (pattern result-field bindings modifiers)136
(:documentation "Perform a step from a pattern match against the current *transaction* repository given137
a logical combination of quad patterns, and optional binding and modifier property lists.138
Any bindings constrain variables in statement patterns while any modifier specifies how to139
slice the final result.140
If a result field is supplied, the resulting solutions will be emitted to that destination."))143
(defparameter *pattern-sort-key* #'pattern-propagated-arity-and-selectivity)147
;;; field iteration support149
(defun binding-argument-list-dimensions (bindings)150
(loop for (dimension nil) on bindings by #'cddr153
(defun call-with-extended-bindings (op field bind-dimensions base-bindings)154
"given an initial binding property list, iterate over the given field, extend the bindings155
individually for each solution and invoke the given operator with the respectively156
extended binding argument list."158
(let* ((field-dimensions (solution-field-dimensions field))159
(iterator (compute-matrix-iterator (length field-dimensions)))160
(extender (compute-bindings-extender field-dimensions bind-dimensions)))161
;; (print-lexical-frame call-with-extended-bindings)162
(funcall iterator (funcall extender op base-bindings) field)))165
(defun compute-bindings-extender (field-dimensions bind-dimensions)166
(let* ((field-parameters (loop for dimension in field-dimensions167
collect (or dimension (gensym "arg"))))168
(extension-lambda `(lambda (op base-bindings)169
(function (lambda ,field-parameters170
(declare (ignorable ,@field-parameters))171
(funcall op (list* ,@(loop for parameter in field-parameters172
for field-dimension in field-dimensions173
when (find field-dimension bind-dimensions)174
append `(',field-dimension ,parameter))176
(values (spocq-compile extension-lambda)178
;;; (compute-bindings-extender '(nil sub pred nil) '(sub extra))181
(defun compute-matrix-iterator (column-count)182
(let ((lambda (compute-matrix-operator-lambda 'iterator :column-count column-count)))183
(values (spocq-compile lambda)185
;;; (compute-matrix-iterator 4)188
(defmethod compute-matrix-operator-lambda ((operator (eql 'iterator)) &key column-count)189
`(lambda (operator field)190
,(format nil "iterator operator for column count: ~s." column-count)191
(declare (type matrix-field field)192
; (optimize ,@*field-optimization*)193
(dynamic-extent operator))194
(describe-field field :label "iteration-source")195
; (print (list operator field (solution-field-solutions field)) *trace-output*)196
(finish-output *trace-output*)197
(unless (= (length (solution-field-dimensions field)) ,column-count) ()198
(matrix-dimension-error :matrix field :expected-dimensions '(* ,column-count)))200
(let ((%source-data (cffi::null-pointer))202
(declare (foreign-type (foreign-array ,+matrix-element-type+ (* ,column-count)) %source-data)203
(type sb-sys:system-area-pointer %source-data)204
(type fixnum source-row)206
(loop while (not (cffi:null-pointer-p (setf (values %source-data source-row) (next-field-row field))))208
,@(loop for source-column below column-count209
collect `(foreign-array-ref %source-data source-row ,source-column)))))))214
(defclass applicable-pattern-class (c2mop:funcallable-standard-class)217
(eval-when (#+lispworks :compile-toplevel :load-toplevel :execute)218
(defmethod c2mop:validate-superclass ((subclass applicable-pattern-class)219
(superclass standard-class))221
(defmethod c2mop:validate-superclass ((subclass applicable-pattern-class)222
(superclass c2mop:funcallable-standard-class))227
(defclass applicable-pattern (c2mop:funcallable-standard-object)229
:initform (error "operator is required.")230
:reader pattern-operator)232
:initform (error "function is required.") :initarg :function233
:reader pattern-function234
:documentation "The compiled pattern matching function for the respective form.235
It accepts three required arguments, the result matrix, the bindings, and the modifiers,236
performs its match against the transaction store and collects the result in the given matrix, or237
given a null initial result, creates a new result matrix.")239
:initarg :dimensions :initform ()240
:reader pattern-dimensions) ;;;!!! must take the internal dimension for otherise non-variable contexts241
(propagated-dimensions243
:accessor pattern-propagated-dimensions244
:documentation "caches variables available for sip bindings to be used to comute the effective arity"))245
(:metaclass applicable-pattern-class))247
(defclass applicable-pattern-combination (applicable-pattern)249
:initform (error "forms is required.") :initarg :forms 250
:reader pattern-forms)253
:accessor pattern-effective-pattern)254
(effective-pattern-lambda256
:accessor pattern-effective-pattern-lambda))257
(:metaclass applicable-pattern-class))259
(defclass applicable-pattern-statement (applicable-pattern)261
:initform (error "terms is required.") :initarg :terms262
:reader pattern-terms)264
:initform nil :initarg :count265
:reader get-pattern-count :writer setf-pattern-count)267
:initform nil :initarg :identity-predicate268
:accessor pattern-identity-predicate))269
(:metaclass applicable-pattern-class))272
(defmethod initialize-instance ((instance applicable-pattern) &rest initargs &key function)273
(declare (dynamic-extent initargs))274
(flet ((process-pattern-function (result-field bindings modifiers)275
(process-pattern instance result-field bindings modifiers)))277
(setf function #'process-pattern-function))278
(apply #'call-next-method instance281
(c2mop:set-funcallable-instance-function instance function)))283
(defmethod process-pattern ((pattern applicable-pattern) (result-field null) (bindings t) (modifiers t))284
(complete-field-data (process-pattern pattern285
(make-matrix-field :dimensions (pattern-dimensions pattern))286
bindings modifiers)))289
(defmethod print-object ((object applicable-pattern) stream)290
(print-unreadable-object (object stream :identity t :type t)291
(format stream "~s" (pattern-dimensions object))))293
(defmethod pattern-selectivity ((pattern applicable-pattern))294
;; the base method just divides the count against the repository total295
(let ((repository-count (repository-statement-count *transaction*))296
(pattern-count (pattern-count pattern)))297
(if (> repository-count 0)298
(float (/ pattern-count repository-count))302
(defun compute-intrasolution-identity-test (dimensions)303
(let ((duplicated-dimension (remove-duplicates (loop for dimension in dimensions304
when (and dimension (> (count dimension dimensions) 1))305
collect dimension))))306
(loop for duplicated in duplicated-dimension307
collect (loop with first-index = (position duplicated dimensions)308
for dimension in dimensions310
when (and (/= first-index index)311
(eq duplicated dimension))312
collect `(= (foreign-array-ref %source-data source-row ,first-index)313
(foreign-array-ref %source-data source-row ,index))315
finally (return (if (rest tests) `(and ,@tests) (first tests))))317
finally (return (if (rest tests) `(and ,@tests) (first tests))))))319
(defmethod pattern-count ((pattern applicable-pattern-combination))320
(flet ((each-pattern-count (pattern)321
(pattern-count pattern)))322
(declare (dynamic-extent #'each-pattern-count))323
(reduce #'+ (pattern-forms pattern) :initial-value 0 :key #'each-pattern-count)))326
(defmethod initialize-instance ((instance applicable-pattern-statement) &rest args &key terms dimensions graph)327
;; abstract the statement pattern terms to retain just the variables in their328
;; respective positions; reorder them to reflect the arrangement returned by the store;329
;; ensure that the context position is a variable even if the statement inclues a constant,330
;; in order to ensure that joins across named graphs limit matched to intra-graph solutions.331
;; replace other constants with unique undistingusihed variables to preclude join constains and332
;; suppress projection.334
;; this approach does not incorporate special logic for constant patterns. where that335
;; case generated code which acted as a filter over bindings to that point, this approach336
;; will generate a single-solution matrix when the constants match, of which only the337
;; context position will have a dimensions339
;; pushed filters' equivalents are handled by retaining the original statement patter, which includes340
;; the variable as the dimension bound to solutions at the position of the constant term.342
;; intra-pattern identity is implemented as an additional filter step where it is required.343
(declare (dynamic-extent args)345
(flet ((ensure-variable (term &optional (default nil))346
(cond ((variable-p term) term)348
(t (cons-variable "bgp")))))349
;; augment the pattern with explicit dimensions.350
;; a given dimension remains; a constant is replaced with an unique undistinguished variable in order351
;; to suppress it in projections and preclude joining, while the context is replaced with a singleton354
(assert (= 4 (length dimensions)) () "dimensions is invalid: ~s." dimensions)355
(assert (= 4 (length terms)) () "terms is invalid: ~s." terms))357
(setf dimensions (destructuring-bind (subject predicate object context) terms358
;; if the context was supplied, provide a singleton dimension to constrain359
;; joins, otherwise supply a unique dimension to eliminate it from joins360
(list (ensure-variable context (when context +context-variable+))361
(ensure-variable subject)362
(ensure-variable predicate)363
(ensure-variable object))))))365
(let* ((identity-test (compute-intrasolution-identity-test dimensions))366
(identity-predicate (when identity-test367
(spocq-compile `(lambda (%source-data source-row)368
(declare (foreign-type (foreign-array ,+matrix-element-type+ (* ,(length dimensions))) %source-data)369
(type sb-sys:system-area-pointer %source-data)370
(type fixnum source-row))372
(flet ((filter-process-pattern-function (result-field bindings modifiers)373
(let* ((filter-operator (ensure-matrix-operator 'filter :projection (loop for i below (length dimensions) collect i)374
:result-column-count (length dimensions))))375
(let ((intermediate-result-field (process-pattern instance nil bindings modifiers)))376
(flet ((filter-result (result-field)377
(with-input-fields (intermediate-result-field)378
(with-result-field (result-field :dimensions (solution-field-dimensions intermediate-result-field)379
:sort-order (solution-field-sort-dimensions intermediate-result-field))380
(funcall filter-operator result-field intermediate-result-field identity-predicate))383
(filter-result result-field)384
(complete-field-data (filter-result (make-matrix-field)))))))))385
(apply #'call-next-method instance386
;; always provide a context binding to make it available to joins so that patterns387
;; do not cross graph boundaries388
:dimensions dimensions389
:function (when identity-predicate #'filter-process-pattern-function)394
;;; abstract generic operator implementations396
(defmethod pattern-arity-and-selectivity ((pattern applicable-pattern))397
(cons (pattern-arity pattern) (pattern-selectivity pattern)))399
(defmethod pattern-propagated-arity-and-selectivity ((pattern applicable-pattern))400
(cons (pattern-propagated-arity pattern) (pattern-selectivity pattern)))402
(defmethod pattern-precedes ((value1 number) (value2 number))405
(defmethod pattern-precedes ((value1 cons) (value2 cons))406
(ecase (signum (- (first value1) (first value2)))408
(0 (< (rest value1) (rest value2)))411
(defmethod pattern-arity ((pattern applicable-pattern))412
(length (pattern-dimensions pattern)))414
(defmethod pattern-propagated-arity ((pattern applicable-pattern))415
(- (length (pattern-dimensions pattern))416
(length (pattern-propagated-dimensions pattern))))418
(defun interned-pattern-terms (pattern bindings)419
(let* ((wildcard-term-number nil)420
(default-context-term nil)421
(named-contexts-term nil)422
(default-graphs (dataset-default-graphs *task*))423
(named-graphs (dataset-named-graphs *task*)))424
(labels ((wildcard-term-number ()425
(or wildcard-term-number (setf wildcard-term-number (repository-wildcard-term *transaction*))))426
(default-context-term ()427
(or default-context-term (setf default-context-term (repository-default-context-term *transaction*))))428
(named-contexts-term ()429
(or named-contexts-term (setf named-contexts-term (repository-named-contexts-term *transaction*))))430
(bind-if-variable (term)431
(if (variable-p term)432
(or (getf bindings term)433
(when (boundp term) (symbol-value term))434
(wildcard-term-number))435
(if (property-path-p term)436
(intern-property-path term)437
(intern-term term))))439
(if (or (null term) (spocq:blank-node-p term) (variable-p term))440
(wildcard-term-number)441
(or (object-term-number term)442
;; if the term is not in the store, no match is possible443
(return-null-terms))))444
(effective-context (context)445
(cond ((null context)446
(remove nil (mapcar #'lookup-object-term-number447
(if (or default-graphs named-graphs) default-graphs (list (default-context-term))))))448
((variable-p context)449
;; either use an initial soution binding or, if it is unbound,450
;; if the dataset specified named graphs, iterate across them - whereby if the effective451
;; dataset includes default graphs, but no named graphs, there is nowhere to search.452
;; see rdf-sparql-query 8.2.1453
;; absent a dataset, treat it as a wild-card in whichever domain is declared for named graphs.454
(cond ((getf bindings context))455
((boundp context) (list (symbol-value context)))456
((or default-graphs named-graphs)457
(remove nil (mapcar #'lookup-object-term-number named-graphs)))459
(list (intern-term (named-contexts-term))))))460
((typep context 'iri)461
(let ((interned-context (intern-term context)))462
(when interned-context (list interned-context))))464
(error "Invalid dataset specification: graph ~s, dataset ~s."465
context (task-dataset-graphs *task*)))))466
(interned-effective-context (context)467
(or (effective-context context)468
(return-null-terms)))469
(return-null-terms ()470
(return-from interned-pattern-terms (list nil nil nil nil))))471
(destructuring-bind (subject predicate object context) (pattern-terms pattern)472
(list (bind-if-variable subject)473
(bind-if-variable predicate)474
(bind-if-variable object)475
(effective-context context))))))481
(defclass bgp:aggregate (applicable-pattern-combination)483
:initform 'bgp:aggregate :allocation :class)485
:initform (error "projection is required.") :initarg :projection486
:accessor pattern-projection))487
(:metaclass applicable-pattern-class)488
(:documentation "The class of wrapped pattern functions aggregations."))490
(defparameter bgp:aggregate 'bgp:aggregate)492
(define-compiler-macro bgp:aggregate (pattern projection &rest initargs)493
`(make-instance bgp:aggregate :forms (list ,pattern) :projection ',projection ,@initargs))496
(defun bgp:aggregate (pattern projection &rest initargs)497
(declare (dynamic-extent initargs))498
(apply #'make-instance bgp:aggregate :forms (list pattern) :projection projection initargs))501
(defmethod process-pattern ((pattern bgp:aggregate) (result-field matrix-field) bindings modifiers)502
"an aggregation pattern applies its projection to the source field as generated in the context of its503
bindings and then applies any modifiers to produce its result."505
(flet ((matrix-aggregate (&rest args)506
(error "NYI: matrix-aggregate ~s" args)))507
(destructuring-bind (base-pattern) (pattern-forms pattern)508
(apply #'matrix-aggregate result-field (process-pattern base-pattern nil bindings nil)509
(pattern-projection pattern)515
(defclass bgp:and (applicable-pattern-combination)517
:initform 'bgp:and :allocation :class))518
(:metaclass applicable-pattern-class)519
(:documentation "The class of wrapped pattern functions for conjunctively joined BGP statement patterns.520
given a repository transaction:521
- get pattern count = (selectivity * size)522
- if (pattern-count / scan-rate) < (initial-field-size / match-rate)523
- then scan: invoke the pattern w/ no solution binding524
merge join to yield a new field and emit it as the result525
- otherwise invoke the pattern iteratively w/ the bindings from the initial field and526
accumulate the results into a new field and emit it as the result"))527
;;; (funcall (make-instance bgp:and :forms (list (bgp:quad 1 2 3 nil))) nil nil)529
(defparameter bgp:and 'bgp:and)531
(define-compiler-macro bgp:and (&rest arguments)532
;; reduce the pattern in-place for one or zero arguments533
(let* ((initargs (member-if #'keywordp arguments))534
(patterns (ldiff arguments initargs)))537
`(make-instance bgp:and :forms (list ,@patterns) ,@initargs)538
(append (first patterns) initargs))539
`(bgp:null ,@initargs))))541
(defun bgp:and (&rest arguments)542
(let* ((initargs (member-if #'keywordp arguments))543
(patterns (ldiff arguments initargs)))546
(apply #'make-instance bgp:and :forms patterns initargs)547
(let ((arg (first patterns)))549
(apply #'reinitialize-instance (first patterns) initargs))551
(apply #'bgp:null initargs))))555
(defmethod initialize-instance ((instance bgp:and) &rest args &key forms dimensions)556
;; compute the effective result dimenions as the combined join result dimensions of the constituents."557
(apply #'call-next-method instance558
:dimensions (or dimensions561
(reduce #'join-result-dimensions forms :key #'pattern-dimensions)562
(pattern-dimensions (first forms)))))566
(defmethod process-pattern ((pattern bgp:and) (result-field matrix-field) bindings modifiers)567
"given an and pattern's constituent statemetn forms and initial bindings, establish the arity of each568
statement respective the successively extended bindings, order the statements based on569
(initial statement size + match rate v/s the subsequence statement expected size + scan rate),570
pick the most favorable, record the combination in the effective method and combine them as such.571
continue this until all constituents are combined.572
finally, unless bindings were present, record the effective method lambda and return the result.573
on a subsequent call reuse a saved effective method."575
(let ((forms (copy-list (pattern-forms pattern))))578
(let ((effective-pattern (pattern-effective-pattern pattern)))579
(if effective-pattern580
(funcall effective-pattern pattern result-field bindings modifiers)581
(loop with bound-variables = (binding-argument-list-dimensions bindings)582
for (next-form . remaining-forms) = (sort-bound-patterns forms bound-variables)583
for combination-operator = nil584
then (compute-pattern-combination pattern successive-result remaining-forms bound-variables)585
for successive-result = (funcall next-form nil bindings nil)586
then (funcall combination-operator pattern (unless remaining-forms result-field)587
successive-result next-form589
(unless remaining-forms modifiers))590
for pattern-expression = `(,next-form nil bindings nil)591
then `(,combination-operator ,pattern ,(unless remaining-forms 'result-field)592
,pattern-expression ,next-form594
,(unless remaining-forms 'modifiers))595
do (setf bound-variables (join-result-dimensions (solution-field-dimensions successive-result) bound-variables)596
forms remaining-forms)597
;; cache prospectively for subsequent compilation598
;; returns the successive result - as is, if it was created locally, the combination completed it599
;; otherwise leave it incomplete for continued use600
finally (let ((lambda `(lambda (pattern result-field bindings modifiers)601
(declare (ignoreable pattern))602
,pattern-expression)))604
(setf (pattern-effective-pattern-lambda pattern) lambda605
(pattern-effective-pattern pattern) (spocq-compile lambda)))606
(return successive-result)))))607
(funcall (first forms) result-field bindings modifiers))608
(matrix-null result-field (pattern-dimensions pattern)))))611
(defmethod merge-and-pattern ((op-pattern t) result-field field next-pattern bindings modifiers)612
(flet ((matrix-join (&rest args)613
(error "NYI: matrix-join ~s" args)))614
(apply #'matrix-join result-field field (funcall next-pattern nil bindings nil) modifiers)))616
(defmethod match-and-pattern (op-pattern (result-field null) field next-pattern bindings modifiers)617
(complete-field-data (match-and-pattern op-pattern (make-matrix-field) field next-pattern bindings modifiers)))619
(defmethod match-and-pattern ((op-pattern t) (result-field matrix-field) field next-pattern bindings modifiers)620
(if (plusp (solution-field-length field))621
(flet ((match-with-extended-bindings (propagated-bindings)622
;; (print-lexical-frame match-with-extended-bindings)623
(setf result-field (funcall next-pattern result-field propagated-bindings modifiers))))624
(declare (dynamic-extent #'match-with-extended-bindings))625
(call-with-extended-bindings #'match-with-extended-bindings field (pattern-dimensions next-pattern) bindings)627
(matrix-null result-field (join-result-dimensions (solution-field-dimensions field) (pattern-dimensions next-pattern)))))629
(defun sort-bound-patterns (patterns bound-variables)630
;; update each pattern to reflect the potentially reduced arity631
(loop for pattern in patterns632
do (setf (pattern-propagated-dimensions pattern) (intersection (pattern-dimensions pattern) bound-variables)))633
;; then pick the least-resource option and decide whether to merge or match634
(sort patterns #'pattern-precedes :key *pattern-sort-key*))637
(defmethod compute-pattern-combination ((pattern bgp:and) field ordered-patterns bound-variables)638
;; pick the least-resource option and decide whether to merge or match639
(let* ((next-pattern (first ordered-patterns))641
(let* ((field-count (solution-field-count field))642
(pattern-count (pattern-count next-pattern))643
(match-cost (/ field-count (repository-match-rate *transaction*)))644
(scan-cost (/ pattern-count (repository-scan-rate *transaction*))))645
(setf operator (if (or (> match-cost scan-cost)646
(null (intersection (solution-field-dimensions field)647
(pattern-dimensions next-pattern))))649
'match-and-pattern)))656
(defclass bgp:and-sum-left (applicable-pattern-combination)658
:initform 'bgp:and-sum-left :allocation :class))659
(:metaclass applicable-pattern-class)660
(:documentation "The class of wrapped pattern functions for optionally, conjunctively joined patterns.661
for a 'leftjoin', the inital pattern is dominant and the incrementally first joined and then,662
for primary solutions which fail to match, unioned with the dependent patterns. 663
as each successive combination extends the initial field, the conditions for matching can change."))665
;;; (funcall (make-instance bgp:and-sum-left :forms (list (bgp:quad 1 2 3 nil))) nil nil)667
(defmethod spocq.e:leftjoin ((field1 applicable-pattern) (field2 applicable-pattern) &rest args)668
(apply #'bgp:and-sum-left field1 field2 args))670
(defparameter bgp:and-sum-left 'bgp:and-sum-left)672
(define-compiler-macro bgp:and-sum-left (&rest arguments)673
(let* ((initargs (member-if #'keywordp arguments))674
(patterns (ldiff arguments initargs)))677
`(make-instance bgp:and-sum-left :forms (list ,@patterns) ,@initargs)678
(append (first patterns) initargs))679
`(bgp:null ,@initargs))))681
(defun bgp:and-sum-left (&rest arguments)682
(let* ((initargs (member-if #'keywordp arguments))683
(patterns (ldiff arguments initargs)))686
(apply #'make-instance bgp:and-sum-left :forms patterns initargs)687
(let ((arg (first patterns)))689
(apply #'reinitialize-instance (first patterns) initargs))691
(apply #'bgp:null initargs))))694
(defmethod process-pattern ((pattern bgp:and-sum-left) (result-field matrix-field) bindings modifiers)695
"perform the same process as for bgp:and, but with different combination operators"697
(let ((forms (copy-list (pattern-forms pattern))))700
(let ((effective-pattern (pattern-effective-pattern pattern)))701
(if effective-pattern702
(funcall effective-pattern pattern result-field bindings modifiers)703
(loop with bound-variables = (binding-argument-list-dimensions bindings)704
for (next-form . remaining-forms) = (sort-bound-patterns forms bound-variables)705
for combination-operator = nil706
then (compute-pattern-combination pattern successive-result remaining-forms bound-variables)707
for successive-result = (funcall next-form nil bindings nil)708
then (funcall combination-operator pattern (unless remaining-forms result-field)709
successive-result next-form711
(unless remaining-forms modifiers))712
for pattern-expression = `(,next-form nil bindings nil)713
then `(,combination-operator ,pattern ,(unless remaining-forms 'result-field)714
,pattern-expression ,next-form716
,(unless remaining-forms 'modifiers))717
do (setf bound-variables (join-result-dimensions (solution-field-dimensions successive-result) bound-variables)718
forms remaining-forms)719
;; cache prospectively for subsequent compilation720
;; returns the successive result - as is, if it was created locally, the combination completed it721
;; otherwise leave it incomplete for continued use722
finally (let ((lambda `(lambda (pattern result-field bindings modifiers)723
(declare (ignoreable pattern))724
,pattern-expression)))726
(setf (pattern-effective-pattern-lambda pattern) lambda727
(pattern-effective-pattern pattern) (spocq-compile lambda)))728
(return successive-result)))))729
(funcall (first forms) result-field bindings modifiers))730
(matrix-null result-field (pattern-dimensions pattern)))))733
(defmethod merge-and-sum-left-pattern ((op-pattern t) result-field field next-pattern bindings modifiers)734
(flet ((matrix-leftjoin (&rest args)735
(error "NYI: matrix-leftjoin ~s" args)))736
(apply #'matrix-leftjoin result-field field (funcall next-pattern nil bindings nil) modifiers)))738
(defmethod match-and-sum-left-pattern (op-pattern (result-field null) field next-pattern bindings modifiers)739
(complete-field-data (match-and-sum-left-pattern op-pattern (make-matrix-field) field next-pattern bindings modifiers)))741
(defmethod match-and-sum-left-pattern ((op-pattern t) (result-field matrix-field) field next-pattern bindings modifiers)742
"perform an incremental left-sum join where each step first performs a join as constrained with the743
propagated values, but then, if no solution resulted, adds the base solution without the extension."744
(if (plusp (solution-field-length field))745
(let ((projector (matrix-project-solution-operator (join-result-dimensions (solution-field-dimensions field)746
(pattern-dimensions next-pattern))747
(solution-field-dimensions field))))748
(flet ((match-with-extended-bindings (propagated-bindings)749
(let ((initial-result-count (matrix-field-length result-field)))750
(setf result-field (funcall next-pattern result-field propagated-bindings modifiers))751
(unless (> (matrix-field-length result-field) initial-result-count)752
(multiple-value-bind (%result-data result-row) (new-field-row result-field)753
(multiple-value-bind (%base-data base-row) (current-field-row field)754
(funcall projector %result-data result-row %base-data base-row)))))))755
(declare (dynamic-extent #'match-with-extended-bindings))756
(call-with-extended-bindings #'match-with-extended-bindings field (pattern-dimensions next-pattern) bindings)758
(matrix-null result-field (join-result-dimensions (solution-field-dimensions field) (pattern-dimensions next-pattern))))))761
(defmethod compute-pattern-combination ((pattern bgp:and-sum-left) field ordered-patterns bound-variables)762
;; pick the least-resource option and decide whether to merge or match763
(let* ((next-pattern (first ordered-patterns))765
(let* ((field-count (solution-field-count field))766
(pattern-count (pattern-count next-pattern))767
(match-cost (/ field-count (repository-match-rate *transaction*)))768
(scan-cost (/ pattern-count (repository-scan-rate *transaction*))))769
(setf operator (if (or (> match-cost scan-cost)770
(null (intersection (solution-field-dimensions field)771
(pattern-dimensions next-pattern))))772
'merge-and-sum-left-pattern773
'match-and-sum-left-pattern)))779
(defclass bgp:ask (applicable-pattern-combination)781
:initform 'bgp:ask :allocation :class))782
(:metaclass applicable-pattern-class)783
(:documentation "The class of wrapped pattern functions for ask queries"))786
(defparameter bgp:ask 'bgp:ask)788
(define-compiler-macro bgp:ask (pattern &rest initargs)789
`(make-instance bgp:ask :forms (list ,pattern) ,@initargs))791
(defun bgp:ask (pattern &rest initargs)792
(declare (dynamic-extent initargs))793
(apply #'make-instance bgp:ask :forms (list pattern) initargs))796
(defmethod process-pattern ((pattern bgp:ask) (result-field matrix-field) bindings modifiers)797
(flet ((matrix-ask (&rest args)798
(error "NYI: matrix-ask ~s" args)))799
(matrix-ask result-field (funcall (first (pattern-forms pattern)) nil bindings modifiers))))805
(defclass bgp:bindings (applicable-pattern)807
:initform 'bgp:bindings :allocation :class)809
:initform (error "solution-data is required") :initarg :solution-data810
:accessor pattern-solution-data))811
(:metaclass applicable-pattern-class)812
(:documentation "The class of wrapped pattern functions for generating static solution fields"))815
(defparameter bgp:bindings 'bgp:bindings)817
(define-compiler-macro bgp:bindings (&whole whole solution-data &rest initargs)818
(if (symbolp (first solution-data))820
`(make-instance bgp:bindings :solution-data ',solution-data ,@initargs)))822
(defun bgp:bindings (solution-data &rest initargs)823
(declare (dynamic-extent initargs))824
(apply #'make-instance bgp:bindings :solution-data solution-data initargs))827
(defmethod process-pattern ((pattern bgp:bindings) (result-field matrix-field) bindings modifiers)828
"gnerate a solution field for the given dimensions and solution data.829
where bindings are provided, perform any variable substitutions"830
(flet ((matrix-bindings (&rest args)831
(error "NYI: matrix-bindings ~s" args)))832
(let ((solution-data (pattern-solution-data pattern)))834
(setf solution-data (sublis bindings solution-data)))835
(matrix-bindings result-field solution-data (pattern-dimensions pattern)))))841
(defclass bgp:construct (applicable-pattern-combination)843
:initform 'bgp:construct :allocation :class)845
:initform (error "solution-data is required") :initarg :solution-data846
:accessor pattern-solution-data))847
(:metaclass applicable-pattern-class)848
(:documentation "The class of wrapped pattern functions for generating static solution fields"))851
(defparameter bgp:construct 'bgp:construct)853
(define-compiler-macro bgp:construct (&whole whole pattern solution-data &rest initargs)854
(if (symbolp (first solution-data))856
`(make-instance bgp:construct :forms (list ,pattern) :solution-data ',solution-data ,@initargs)))858
(defun bgp:construct (pattern solution-data &rest initargs)859
(declare (dynamic-extent initargs))860
(apply #'make-instance bgp:construct :forms (list pattern) :solution-data solution-data initargs))863
(defmethod process-pattern ((pattern bgp:construct) (result-field matrix-field) bindings modifiers)864
"generate a solution field for the given dimensions and solution pattern.865
resolve any bindings from the given solution field"867
(flet ((matrix-construct (&rest args)868
(error "NYI: matrix-construct ~s" args)))869
(let ((solution-data (pattern-solution-data pattern))870
(source-field (funcall (first (pattern-forms pattern)) nil bindings modifiers)))872
(setf solution-data (sublis bindings solution-data)))873
(matrix-construct result-field source-field solution-data))))879
(defclass bgp:describe (applicable-pattern-combination)881
:initform 'bgp:describe :allocation :class)883
:initform (error "resources is required") :initarg :resources884
:accessor pattern-resources))885
(:metaclass applicable-pattern-class)886
(:documentation "The class of wrapped pattern functions for generating resource-descriptions"))889
(defparameter bgp:describe 'bgp:describe)891
(define-compiler-macro bgp:describe (pattern subject-resources &rest initargs)892
`(make-instance bgp:describe :forms (list ,pattern) :resources ',subject-resources ,@initargs))894
(defun bgp:describe (pattern subject-resources &rest initargs)895
(declare (dynamic-extent initargs))896
(apply #'make-instance bgp:describe897
:forms (list pattern)898
:resources subject-resources902
(defmethod process-pattern ((pattern bgp:describe) (result-field matrix-field) bindings modifiers)903
"generate a solution field for the given dimensions and solution pattern.904
resolve any bindings from the given solution field"906
(flet ((matrix-describe (&rest args)907
(error "NYI: matrix-describe ~s" args)))908
(let ((resources (pattern-resources pattern))909
(source-field (funcall (first (pattern-forms pattern)) nil bindings modifiers)))910
(matrix-describe result-field source-field resources))))914
;;; diff : incorporates the solutions from the first sub-expression which do not appear in a successor916
(defclass bgp:diff (applicable-pattern-combination)918
:initform 'bgp:diff))919
(:metaclass applicable-pattern-class)920
(:documentation "The class of wrapped pattern functions for differentially merged BGP statement patterns.921
- scan each pattern invoke the pattern w/ no solution922
- merge-diff successive patterns to yield the result field."))925
(defparameter bgp:diff 'bgp:diff)927
(define-compiler-macro bgp:diff (&rest arguments)928
(let* ((initargs (member-if #'keywordp arguments))929
(patterns (ldiff arguments initargs)))930
(if (and (null initargs) (null (rest patterns)))932
`(make-instance bgp:diff933
:forms (list ,@patterns)936
(defun bgp:diff (&rest arguments)937
(let* ((initargs (member-if #'keywordp arguments))938
(patterns (ldiff arguments initargs)))939
(if (and (null initargs) (null (rest patterns)))941
(apply #'make-instance bgp:diff946
(defmethod process-pattern ((pattern bgp:diff) (result-field matrix-field) bindings modifiers)947
(flet ((matrix-diff (&rest args)948
(error "NYI: matrix-diff ~s" args)))949
(loop for form in (pattern-forms pattern)950
for rest-forms on (rest (pattern-forms pattern))951
for field = (funcall form952
(when (null rest-forms) result-field)954
(when (null rest-forms) modifiers))955
then (if (null rest-forms)956
(apply #'matrix-diff result-field field (funcall form nil bindings nil) modifiers)957
(matrix-diff nil field (funcall form nil bindings nil)))958
finally (return field))))962
;;; distinct : eliminate duplicates from the source field964
(defclass bgp:distinct (applicable-pattern-combination)966
:initform 'bgp:distinct))967
(:metaclass applicable-pattern-class)968
(:documentation "The class of wrapped pattern functions for distinct fields.969
- compute the source pattern970
- use the given dimensions to project and eliminate duplicates"))973
(defparameter bgp:distinct 'bgp:distinct)975
(define-compiler-macro bgp:distinct (pattern &rest initargs)976
`(make-instance bgp:distinct977
:forms (list ,pattern)980
(defun bgp:distinct (pattern &rest initargs)981
(declare (dynamic-extent initargs))982
(apply #'make-instance bgp:distinct983
:forms (list pattern)987
(defmethod process-pattern ((pattern bgp:distinct) (result-field matrix-field) bindings modifiers)988
(flet ((matrix-distinct (&rest args)989
(error "NYI: matrix-distinct ~s" args)))990
(apply #'matrix-distinct result-field (funcall (first (pattern-forms pattern)) nil bindings nil)995
;;; extend : extend the source field according to binding specifications997
(defclass bgp:extend (applicable-pattern-combination)999
:initform 'bgp:extend)1001
:initform (error "bindings is required.") :initarg :bindings1002
:accessor pattern-bindings))1003
(:metaclass applicable-pattern-class)1004
(:documentation "The class of wrapped pattern functions for extended fields.1005
- compute the source pattern1006
- extend the result according to the bindings."))1009
(defparameter bgp:extend 'bgp:extend)1011
(define-compiler-macro bgp:extend (pattern bindings &rest initargs)1012
`(make-instance bgp:extend1013
:forms (list ,pattern)1014
:bindings ',bindings1017
(defun bgp:extend (pattern bindings &rest initargs)1018
(apply #'make-instance bgp:extend1019
:forms (list pattern)1025
;;;!!!! need to change the coll patter not to pass the result1026
(defmethod process-pattern ((pattern bgp:extend) (result-field matrix-field) bindings modifiers)1027
(apply #'spocq.e:extend (funcall (first (pattern-forms pattern)) nil bindings nil)1028
(pattern-bindings pattern)1033
;;; filter : apply the test for to each solution and eliminate those which fail1035
(defclass bgp:filter (applicable-pattern-combination)1037
:initform 'bgp:filter)1039
:initform (error "test is required.") :initarg :test1040
:accessor pattern-test))1041
(:metaclass applicable-pattern-class)1042
(:documentation "The class of wrapped pattern functions for filtered fields.1043
- compute the source pattern1044
- filter the result against the test end eilinate those which fail."))1047
(defparameter bgp:filter 'bgp:filter)1049
(define-compiler-macro bgp:filter (pattern test &rest initargs)1050
`(make-instance bgp:filter1051
:forms (list ,pattern)1055
(defun bgp:filter (pattern test &rest initargs)1056
(apply #'make-instance bgp:filter1057
:forms (list pattern)1062
(defmethod process-pattern ((pattern bgp:filter) (result-field matrix-field) bindings modifiers)1063
(flet ((matrix-filter (&rest args)1064
(error "NYI: matrix-filter ~s" args)))1065
(apply #'matrix-filter result-field (funcall (first (pattern-forms pattern)) nil bindings nil)1066
(pattern-test pattern)1073
(defclass bgp:group (applicable-pattern-combination)1075
:initform 'bgp:group)1077
:initform (error "bindings is required.") :initarg :bindings1078
:accessor pattern-bindings))1079
(:metaclass applicable-pattern-class)1080
(:documentation "The class of wrapped pattern functions for grouped fields.1081
- compute the source pattern1082
- group the result according to the bindings."))1085
(defparameter bgp:group 'bgp:group)1087
(define-compiler-macro bgp:group (pattern bindings &rest initargs)1088
`(make-instance bgp:group1089
:forms (list ,pattern)1090
:bindings ',bindings1093
(defun bgp:group (pattern bindings &rest initargs)1094
(apply #'make-instance bgp:group1095
:forms (list pattern)1100
(defmethod process-pattern ((pattern bgp:group) (result-field matrix-field) bindings modifiers)1101
(flet ((matrix-group (&rest args)1102
(error "NYI: matrix-group ~s" args)))1103
(apply #'matrix-group result-field (funcall (first (pattern-forms pattern)) nil bindings nil)1104
(pattern-bindings pattern)1111
(defclass bgp:index-match (applicable-pattern)1113
:initform 'bgp:index-match :allocation :class)1115
:initform (error "index-expression is required.") :initarg :index-expression1116
:accessor pattern-index-expression)1118
:initform nil :initarg :score-dimension1119
:accessor pattern-score-dimension))1120
(:metaclass applicable-pattern-class)1121
(:documentation "The class of wrapped predicates which translate BGP statement patterns and related1122
filter expressions into indexed retrieval operations."))1125
(defparameter bgp:index-match 'bgp:index-match)1127
(define-compiler-macro bgp:index-match (subject predicates objects context &rest initargs &key dimensions score-dimension test index-expression)1128
(declare (ignore dimensions score-dimension test index-expression))1129
`(make-instance bgp:index-match1130
;; nb. terms are retained as s-p-o-c as per a quad form.1131
:terms ',(list subject predicates objects context)1134
(defun bgp:index-match (subject predicates objects context &rest initargs &key1135
dimensions score-dimension test index-expression)1136
(declare (ignore dimensions score-dimension test index-expression)1137
(dynamic-extent initargs))1138
(apply #'make-instance bgp:index-match1139
:terms (list subject predicates objects context)1142
(defmethod initialize-instance ((instance bgp:index-match) &rest initargs &key terms test index-expression)1143
(destructuring-bind (subject predicates objects context) terms1144
(declare (ignore subject context))1145
(apply #'call-next-method instance1146
:index-expression (or index-expression1147
(let ((map (loop for predicate in predicates1148
for object in objects1149
collect (cons object predicate)))1150
(index (loop with index = nil1151
for predicate in predicates1152
for predicate-index = (repository-index *transaction* predicate)1154
do (assert (eq index predicate-index))1155
else do (setf index predicate-index)1156
finally (return index))))1157
(translate-index-expression index test map)))1161
(defmethod process-pattern ((pattern bgp:index-match) (result-field matrix-field) bindings modifiers)1162
(labels ((variable-value (term)1163
(if (variable-p term)1164
(term-number-object (or (getf bindings term)1165
(symbol-value term)))1167
(ensure-variable (term &optional (default nil))1168
(cond ((variable-p term) term)1170
(t (cons-variable "bgp")))))1171
(destructuring-bind (subject predicates objects context) (pattern-terms pattern)1172
(let* ((score-dimension (pattern-score-dimension pattern))1173
(dimensions (list* (ensure-variable context +context-variable+)1174
(ensure-variable subject)1175
(append objects (when score-dimension (list score-dimension))))))1176
(let* ((solutions (matrix-field-solutions result-field))1177
(%xaction (transaction-record *transaction*))1178
(new-solutions (rdfcache::index-match %xaction solutions1180
(map-into (make-array (length predicates)) #'object-term-number predicates)1181
(pattern-index-expression pattern)1182
(not (null score-dimension)))))1183
(unless (eq solutions new-solutions)1184
(setf (matrix-field-solutions result-field) new-solutions))1185
(setf (solution-field-dimensions result-field) dimensions1186
(solution-field-sort-dimensions result-field) (remove nil dimensions))1192
(defclass bgp:not (applicable-pattern-combination)1194
:initform 'bgp:not))1195
(:metaclass applicable-pattern-class)1196
(:documentation "The class of wrapped pattern functions for inversion merged BGP statement patterns.1197
given a repository transaction:1198
- match the constituent pattern, invoking it w/any provided bindings.1199
- if it succeeds, return null, if it does not match, return a unit table."))1202
(defparameter bgp:not 'bgp:not)1204
(define-compiler-macro bgp:not (form &rest initargs)1205
`(make-instance bgp:not1209
(defun bgp:not (form &rest initargs)1210
(declare (dynamic-extent initargs))1211
(apply #'make-instance bgp:not1216
(defmethod process-pattern ((pattern bgp:not) (result-field matrix-field) bindings modifiers)1217
(destructuring-bind (form) (pattern-forms pattern) ; permit one constituent only1218
(let ((result (funcall form nil bindings (or modifiers '(:start 0 :end 1)))))1219
(if (plusp (solution-field-length result))1220
(matrix-null result-field (solution-field-dimensions result))1221
(matrix-table result-field (solution-field-dimensions result))))))1227
(defclass bgp:null (applicable-pattern)1229
:initform 'bgp:null))1230
(:metaclass applicable-pattern-class)1231
(:documentation "The class of null patterns"))1234
(defparameter bgp:null 'bgp:null)1236
(define-compiler-macro bgp:null (&rest args &key dimensions)1237
(declare (ignore dimensions))1238
`(make-instance bgp:null ,@args))1240
(defun bgp:null (&rest args &key dimensions)1241
(declare (dynamic-extent args)1242
(ignore dimensions))1243
(apply #'make-instance bgp:null args))1245
(defmethod process-pattern ((pattern bgp:null) (result-field matrix-field) (bindings t) (modifiers t))1246
(matrix-null result-field (pattern-dimensions pattern)))1250
;;; or : incorporates the solutions from the first sub-expression which supplies it1252
(defclass bgp:or (applicable-pattern-combination)1255
(:metaclass applicable-pattern-class)1256
(:documentation "The class of wrapped pattern functions for disjunctively merged BGP statement patterns.1257
given a repository transaction:1258
- scan each pattern invoke the pattern w/ no solution1259
- merge or to yield a new field and use it as the base field"))1262
(defparameter bgp:or 'bgp:or)1264
(define-compiler-macro bgp:or (&rest arguments)1265
(let* ((initargs (member-if #'keywordp arguments))1266
(patterns (ldiff arguments initargs)))1267
(if (and (null initargs) (null (rest patterns)))1269
`(make-instance bgp:or1270
:forms (list ,@patterns)1273
(defun bgp:or (&rest arguments)1274
(let* ((initargs (member-if #'keywordp arguments))1275
(patterns (ldiff arguments initargs)))1276
(if (and (null initargs) (null (rest patterns)))1278
(apply #'make-instance bgp:or1283
(defmethod process-pattern ((pattern bgp:or) (result-field matrix-field) bindings modifiers)1284
(loop for form in (pattern-forms pattern)1285
for forms on (pattern-forms pattern)1286
for field = (funcall form 1287
(when (null (rest forms)) result-field) 1289
(when (null (rest forms)) modifiers))1290
then (funcall #'merge-or-pattern pattern (when (null (rest forms)) result-field) 1294
(when (null (rest forms)) modifiers))1295
finally (return field)))1297
(defmethod merge-or-pattern ((op-pattern t) result-field field pattern bindings modifiers)1298
(flet ((matrix-or (&rest args)1299
(error "NYI: matrix-or ~s" args)))1300
(apply #'matrix-or result-field field (funcall nil pattern bindings nil) modifiers)))1304
;;; order : order the source field by ascending/descending dimensions 1306
(defclass bgp:order (applicable-pattern-combination)1308
:initform 'bgp:order)1309
(order-predicate-form1310
:initform (error "order-predicate-form is required.") :initarg :order-predicate-form1311
:accessor pattern-order-predicate-form))1312
(:metaclass applicable-pattern-class)1313
(:documentation "The class of wrapped pattern functions for ordered fields.1314
- compute the source pattern1315
- order the result according to the predicates."))1318
(defparameter bgp:order 'bgp:order)1320
(define-compiler-macro bgp:order (pattern order-predicate-form &rest initargs)1321
`(make-instance bgp:order1322
:forms (list ,pattern)1323
:order-predicate-form ',order-predicate-form1326
(defun bgp:order (pattern order-predicate-form &rest initargs)1327
(apply #'make-instance bgp:order1328
:forms (list pattern)1329
:order-predicate-form order-predicate-form1333
(defmethod process-pattern ((pattern bgp:order) (result-field matrix-field) bindings modifiers)1334
(flet ((matrix-order (&rest args)1335
(error "NYI: matrix-order ~s" args)))1336
(apply #'matrix-order result-field (funcall (first (pattern-forms pattern)) nil bindings nil)1337
:order-predicate-form (pattern-order-predicate-form pattern)1342
;;; project : reduce the filed to the given dimensions 1344
(defclass bgp:project (applicable-pattern-combination)1346
:initform 'bgp:project))1347
(:metaclass applicable-pattern-class)1348
(:documentation "The class of wrapped pattern functions for projected fields.1349
- compute the source pattern1350
- project the result according to the given dimensions"))1353
(defparameter bgp:project 'bgp:project)1355
(define-compiler-macro bgp:project (pattern dimensions &rest initargs)1356
`(make-instance bgp:project1357
:forms (list ,pattern)1358
;; ignore any keyword dimensions1359
:dimensions ',dimensions1362
(defun bgp:project (pattern dimensions &rest initargs)1363
(apply #'make-instance bgp:project1364
:forms (list pattern)1365
;; ignore any keyword dimensions1366
:dimensions dimensions1370
(defmethod process-pattern ((pattern bgp:project) (result-field matrix-field) bindings modifiers)1371
(apply #'process-project result-field (funcall (first (pattern-forms pattern)) nil bindings nil)1372
(pattern-dimensions pattern)1379
(defclass bgp:quad (applicable-pattern-statement)1381
:initform 'bgp:quad :allocation :class))1382
(:metaclass applicable-pattern-class)1383
(:documentation "The class of wrapped pattern functions individual BGP statement patterns.1384
in the context of the current *transaction* repository:1385
- establish the effective context given the current *dataset* and a variable v/s constant graph term1386
- combine the stated pattern with any given bindings to yield an effective pattern1387
- match the effective pattern with the repository1388
- accumulate successive matches if the dataset enumerates constant graphs 1389
- constrain the result given solution modifiers."))1391
(defun make-pattern (type &rest args)1392
(declare (dynamic-extent args))1393
(apply #'make-instance type args))1395
(defparameter bgp:quad 'bgp:quad)1397
(define-compiler-macro bgp:quad (subject predicate object context &key dimensions count)1398
`(make-instance bgp:quad1399
;; nb. terms are retained as s-p-o-c as per a quad form.1400
:terms ',(list subject predicate object context)1401
,@(when dimensions `(:dimensions ',dimensions))1402
,@(when count `(:count ,count))))1404
(defun bgp:quad (subject predicate object context &rest initargs &key dimensions count)1405
(declare (dynamic-extent initargs)1406
(ignore dimensions count))1407
(apply #'make-instance bgp:quad1408
;; nb. terms are retained as s-p-o-c as per a quad form.1409
:terms (list subject predicate object context)1413
;;; (bgp:quad ?::s <http://> ?::o ?::g)1414
;;; (bgp:quad ?::g <http://> ?::o ?::g)1417
(defmethod process-pattern ((pattern bgp:quad) (result-field matrix-field) bindings modifiers)1418
(destructuring-bind (subject predicate object context) (interned-pattern-terms pattern bindings)1420
(let* ((solutions (matrix-field-solutions result-field))1421
(new-solutions (repository-match-matrix *transaction* solutions1426
(set-solution-field-solutions result-field new-solutions)1427
(setf (solution-field-dimensions result-field) (pattern-dimensions pattern)1428
(solution-field-sort-dimensions result-field) (pattern-dimensions pattern))1429
(incf-stat *solutions-processed* (solution-field-row-count result-field))1430
;; (print-lexical-frame "bgp:quad")1432
;; if no context is present in the store, there can be no match1433
(matrix-null result-field (pattern-dimensions pattern)))))1436
(defmethod pattern-count ((pattern bgp:quad))1437
(or (get-pattern-count pattern)1438
(setf-pattern-count (apply #'repository-pattern-count *transaction* (pattern-terms pattern))1441
(defmethod print-object ((object bgp:quad) stream)1442
(print-unreadable-object (object stream :identity t :type t)1443
(format stream "~s.~s" (pattern-terms object) (pattern-dimensions object))))1445
;;; (compute-intrasolution-identity-test '(a nil s a))1446
;;; (compute-intrasolution-identity-test '(a s s a))1447
;;; (compute-intrasolution-identity-test '(a a nil a))1448
;;; (compute-intrasolution-identity-test '(a a a a))1454
(defclass bgp:quad-call (applicable-pattern-statement)1456
:initform 'bgp:quad-call :allocation :class)1458
:initform (error "extension-function is required.") :initarg :extension-function))1459
(:metaclass applicable-pattern-class)1460
(:documentation "The class of extension function patterns combines an operator with the s/o/c terms.1461
in the context of the current *transaction* repository:1462
- establish the effective context given the current *dataset* and a variable v/s constant graph term1463
- combine the stated pattern with any given bindings to yield an effective pattern1464
- execute the extension function with the repository1465
- accumulate successive matches if the dataset enumerates constant graphs 1466
- constrain the result given solution modifiers."))1468
(defparameter bgp:quad-call 'bgp:quad-call)1471
(defmacro bgp:quad-call (subject predicate object context &rest initargs)1472
`(make-instance bgp:quad-call1473
;; nb. terms are retained as s-p-o-c as per a quad form.1474
:terms ',(list subject predicate object context)1475
:extension-function ',predicate1478
(defmacro bgp:quad-call (subject predicate object context &rest initargs)1479
(apply #'make-instance bgp:quad-call1480
;; nb. terms are retained as s-p-o-c as per a quad form.1481
:terms (list subject predicate object context)1482
:extension-function predicate1485
(defmethod pattern-count ((pattern bgp:quad-call))1488
(defmethod process-pattern ((pattern bgp:quad-call) (result-field matrix-field) (bindings t) (modifiers t))1489
(error "quad-call is NYI."))1495
(defclass bgp:quad-entail (applicable-pattern-statement)1497
:initform 'bgp:quad-entail :allocation :class)1499
:initform (error "antecedent is required.") :initarg :antecedent1500
:accessor pattern-antecedent))1501
(:metaclass applicable-pattern-class)1502
(:documentation "The class of wrapped pattern functions for entailed BGP statement patterns.1503
in the context of the current *transaction* repository:1504
- establish the effective context given the current *dataset* and a variable v/s constant graph term1505
- combine the stated pattern with any given bindings to yield an effective pattern1506
- match the effective pattern with the repository1507
- accumulate successive matches if the dataset enumerates constant graphs 1508
- constrain the result given solution modifiers.1509
if the primary form fails to yield results, proceeed through the antecedents"))1512
(defparameter bgp:quad-entail 'bgp:quad-entail)1514
(define-compiler-macro bgp:quad-entail ((quad-op subject predicate object context) &rest arguments)1515
(declare (ignore quad-op))1516
(let* ((initargs (member-if #'keywordp arguments))1517
(patterns (ldiff arguments initargs)))1518
`(make-instance bgp:quad-entail1519
;; nb. terms are retained as per quad form.1520
:terms ',(list subject predicate object context)1521
:antecedent (bgp:or ,@patterns)1524
(defun bgp:quad-entail (form &rest arguments)1525
(destructuring-bind (quad-op subject predicate object context) form1526
(declare (ignore quad-op))1527
(let* ((initargs (member-if #'keywordp arguments))1528
(patterns (ldiff arguments initargs)))1529
(apply #'make-instance bgp:quad-entail1530
;; nb. terms are retained as per quad form.1531
;; but de/reconstructed from the arguments1532
:terms (list subject predicate object context)1533
:antecedent (apply #'bgp:or patterns)1537
(defmethod pattern-count ((pattern bgp:quad-entail))1538
(or (get-pattern-count pattern)1539
(setf-pattern-count (+ (apply #'repository-pattern-count *transaction* (pattern-terms pattern))1540
(pattern-count (pattern-antecedent pattern)))1544
(defparameter *entailing-patterns* ())1546
(defmethod process-pattern ((pattern bgp:quad-entail) (result-field matrix-field) bindings modifiers)1547
"apply an entailment pattern to a store by first attempting the base pattern. if that succeeds,1548
use the field which results. if it produces no results, attempt the antecedents, which are1549
captured as an autonomous operator."1551
(destructuring-bind (subject predicate object context) (interned-pattern-terms pattern bindings)1553
(let* ((solutions (matrix-field-solutions result-field))1554
(new-solutions (repository-match-matrix *transaction* solutions1559
(cond ((and (zerop (rdfcache:matrix-row-count solutions))1560
(not (find pattern *entailing-patterns* :test #'equalp :key #'pattern-terms)))1561
;; try the entailment 1562
(let ((*entailing-patterns* (cons pattern *entailing-patterns*)))1563
(declare (dynamic-extent *entailing-patterns*))1564
(funcall (pattern-antecedent pattern) nil bindings modifiers)))1566
(unless (eq solutions new-solutions)1567
(setf (matrix-field-solutions result-field) new-solutions))1568
(setf (solution-field-dimensions result-field) (pattern-dimensions pattern)1569
(solution-field-sort-dimensions result-field) (pattern-dimensions pattern))1571
;; if no context is present in the store, there can be no match1572
(matrix-null result-field (pattern-dimensions pattern)))))1574
(defmethod pattern-count ((pattern bgp:quad-entail))1575
(or (get-pattern-count pattern)1576
(setf-pattern-count (+ (apply #'repository-pattern-count *transaction* (pattern-terms pattern))1577
(pattern-count (pattern-antecedent pattern)))1584
(defclass bgp:quad-path (applicable-pattern-statement)1586
:initform 'bgp:quad-path :allocation :class)1588
:initform (error "path is required.") :initarg :path1589
:accessor pattern-path))1590
(:metaclass applicable-pattern-class)1591
(:documentation "The class of extension function patterns combines an operator with the s/o/c terms.1592
in the context of the current *transaction* repository:1593
- establish the effective context given the current *dataset* and a variable v/s constant graph term1594
- combine the stated pattern with any given bindings to yield an effective pattern1595
- execute the extension function with the repository1596
- accumulate successive matches if the dataset enumerates constant graphs 1597
- constrain the result given solution modifiers."))1600
(defparameter bgp:quad-path 'bgp:quad-path)1602
(define-compiler-macro bgp:quad-path (subject predicate object context &key dimensions)1603
`(make-instance bgp:quad-path1604
;; nb. terms are retained as s-p-o-c as per a quad form.1605
:terms '(,subject ,predicate ,object ,context)1607
,@(when dimensions `(:dimensions ',dimensions))))1609
(defun bgp:quad-path (subject predicate object context &rest initargs &key dimensions)1610
(declare (dynamic-extent initargs)1611
(ignore dimensions))1612
(apply #'make-instance bgp:quad-path1613
;; nb. terms are retained as s-p-o-c as per a quad form.1614
:terms (list subject predicate object context)1619
(defun process-path-pattern (pattern result-field bindings modifiers)1620
(declare (type bgp:quad-path pattern))1621
(destructuring-bind (subject predicate object contexts) (interned-pattern-terms pattern bindings)1622
;; if no context existed, then no match can succeed1624
(let ((result-field (initialize-result-field result-field :dimensions (pattern-dimensions pattern)))1626
(destructuring-bind (&key (start 0) end) modifiers1627
(flet ((process-path-pattern-continue (context subject matched-predicate object)1628
(declare (ignore matched-predicate))1629
(let ((%result-data (cffi:null-pointer))1631
(declare (foreign-type (foreign-array #.+matrix-element-type+ (* 4)) %result-data)1632
(type cffi:foreign-pointer %result-data))1633
(when (> (incf result-count) start)1634
(when (and end (>= result-count end))1635
(return-from process-path-pattern result-field))1636
(setf (values %result-data result-row) (new-field-row result-field))1637
(setf (foreign-array-ref %result-data result-row 0) context1638
(foreign-array-ref %result-data result-row 1) subject1639
(foreign-array-ref %result-data result-row 2) 0 ; predicate constant - at the moment, the object is returned1640
(foreign-array-ref %result-data result-row 3) object)))))1641
(declare (dynamic-extent #'process-path-pattern-continue))1642
(loop for context in contexts1643
do (match-property-path *transaction* context subject predicate object #'process-path-pattern-continue))))1645
(matrix-null result-field (pattern-dimensions pattern)))))1647
(defmethod process-pattern ((pattern bgp:quad-path) (result-field matrix-field) bindings modifiers)1648
;; sbcl compiles a method body once w/o a lexical environmet, which would cause the array reference to fail1649
;; therefor call out to a simple function1650
(process-path-pattern pattern bindings modifiers result-field))1652
(defmethod pattern-count ((pattern bgp:quad-path))1653
(or (get-pattern-count pattern)1654
(destructuring-bind (subject predicate object context) (pattern-terms pattern)1655
(declare (ignore predicate))1656
(setf-pattern-count (repository-pattern-count *transaction* subject nil object context)1661
;;; slice : order the source field by ascending/descending dimensions 1663
(defclass bgp:slice (applicable-pattern-combination)1665
:initform 'bgp:slice)1667
:initform (error "slice is required.") :initarg :slice1668
:accessor pattern-slice))1669
(:metaclass applicable-pattern-class)1670
(:documentation "The class of wrapped pattern functions for sliced fields.1671
- compute the source pattern1672
- slice the result according to the given bounds unless the dynamic value supersedes"))1675
(defparameter bgp:slice 'bgp:slice)1677
(define-compiler-macro bgp:slice (pattern slice &rest initargs)1678
`(make-instance bgp:slice1679
:forms (list ,pattern)1683
(defun bgp:slice (pattern slice &rest initargs)1684
(declare (dynamic-extent initargs))1685
(apply #'make-instance bgp:slice1686
:forms (list pattern)1691
(defmethod process-pattern ((pattern bgp:slice) (result-field abstract-page-channel) bindings modifiers)1692
(apply #'process-slice result-field (funcall (first (pattern-forms pattern)) nil bindings nil)1693
(append modifiers (pattern-slice pattern))))1697
;;; union : accumulate all matched solutions (as union)1699
(defclass bgp:union (applicable-pattern-combination)1701
:initform 'bgp:union))1702
(:metaclass applicable-pattern-class)1703
(:documentation "The class of wrapped pattern functions for summed BGP statement patterns.1704
given a repository transaction:1705
- scan each pattern invoke the pattern w/ no solution1706
- merge excluding anu conjunctions to yield a new field and use it as the base field"))1709
(defparameter bgp:union 'bgp:union)1711
(define-compiler-macro bgp:union (&rest arguments)1712
(let* ((initargs (member-if #'keywordp arguments))1713
(patterns (ldiff arguments initargs)))1714
(if (and (null initargs) (null (rest patterns)))1716
`(make-instance bgp:union1717
:forms (list ,@patterns)1720
(defun bgp:union (&rest arguments)1721
(let* ((initargs (member-if #'keywordp arguments))1722
(patterns (ldiff arguments initargs)))1723
(if (and (null initargs) (null (rest patterns)))1725
(apply #'make-instance bgp:union1730
(defmethod process-pattern ((pattern bgp:union) (result-field matrix-field) bindings modifiers)1731
(loop for form in (pattern-forms pattern)1732
for forms on (pattern-forms pattern)1733
for field = (funcall form (when (null (rest forms)) result-field)1735
(when (null (rest forms)) modifiers))1736
then (funcall #'merge-union-pattern pattern1737
(when (null (rest forms)) result-field)1739
(when (null (rest forms)) modifiers))1740
finally (return field)))1742
(defmethod merge-union-pattern ((op-pattern t) (result-field null) field pattern bindings modifiers)1743
(complete-field-data (merge-union-pattern op-pattern (make-matrix-field) field pattern bindings modifiers)))1745
(defmethod merge-union-pattern ((op-pattern t) (result-field matrix-field) field pattern bindings modifiers)1746
(flet ((matrix-union (&rest args)1747
(error "NYI: matrix-union ~s" args)))1748
(apply #'matrix-union result-field field (funcall pattern nil bindings nil) modifiers)))1752
;;; xor : incorporates whichever solution succeeds, but only if there is exactly one1754
(defclass bgp:xor (applicable-pattern-combination)1756
:initform 'bgp:xor))1757
(:metaclass applicable-pattern-class)1758
(:documentation "The class of wrapped pattern functions for inversion merged BGP statement patterns.1759
given a repository transaction:1760
- scan each pattern invoke the pattern w/ no solution1761
- merge excluding any conjunctions to yield a new field and use it as the base field"))1764
(defparameter bgp:xor 'bgp:xor)1766
(define-compiler-macro bgp:xor (&rest arguments)1767
(let* ((initargs (member-if #'keywordp arguments))1768
(patterns (ldiff arguments initargs)))1769
(if (and (null initargs) (null (rest patterns)))1771
`(make-instance bgp:xor1772
:forms (list ,@patterns)1775
(defun bgp:xor (&rest arguments)1776
(let* ((initargs (member-if #'keywordp arguments))1777
(patterns (ldiff arguments initargs)))1778
(if (and (null initargs) (null (rest patterns)))1780
(apply #'make-instance bgp:xor1785
(defmethod process-pattern ((pattern bgp:xor) result-field bindings modifiers)1786
(loop for form in (pattern-forms pattern)1787
for forms on (pattern-forms pattern)1788
for field = (funcall form (when (null (rest forms)) result-field)1790
(when (null (rest forms)) modifiers))1791
then (funcall #'merge-xor-pattern pattern1792
(when (null (rest forms)) result-field) 1795
(when (null (rest forms)) modifiers))1796
finally (return field)))1798
(defmethod merge-xor-pattern ((op-pattern t) result-field field pattern bindings modifiers)1799
(flet ((matrix-xor (&rest args)1800
(error "NYI: matrix-xor ~s" args)))1801
(apply #'matrix-xor result-field field (funcall pattern nil bindings nil) modifiers)))1808
;;; basic graph pattern compilation1810
(defmethod compute-bgp-lambda ((agp-repository rdfcache-decimated-matrix-repository) body &rest args &key &allow-other-keys)1811
(declare (dynamic-extent args))1812
(apply #'compute-decimated-bgp-lambda body args))1814
;; (defun query-pattern-rewrite-operators (task) (declare (ignore task)) nil)1818
(defun compute-decimated-bgp-lambda (body &key1819
(graph (second (assoc 'spocq.a:|graph| body)))1820
(slice (rest (assoc 'spocq.a:|slice| body)))1824
projection-dimensions1827
default-context-term 1836
"transform into an applicable pattern by1837
- expanding all triples to add either the graph variable/value, iff in the scope, or the current default graph term, if not.1838
- wrap the body in a bgp:|and|1839
if a graph variable is present, retain it. otherwise suppress that dimension as a join constraint"1840
(declare (ignore environment))1841
(declare (ignore base-dimensions projection-dimensions wildcard-term DATASET-GRAPHS1842
default-context-term default-graphs dynamic-variables1843
named-graphs graphs transaction trace variables))1845
(destructuring-bind (offset count) slice1846
(setf slice `(:start ,offset :end ,(+ (or offset 0) count)))))1847
;; extract any filter/triple combinations which should be handled by an index1848
;; combine the remainder into a single bgp:and, then combine the index and the match sections in an outer bgp:and1849
(labels ((graph-dimension ()1850
(cond ((variable-p graph)1854
(t ; if in a default dataset, suppress the graph dimension1856
(rewrite-body (body)1858
;; first, extend any triples to quads1859
(setf body (loop for form in body1860
for operator = (first form)1861
collect (case operator1863
(destructuring-bind (s p o &key dimensions &allow-other-keys) (rest form)1864
`(spocq.a:|quad| ,s ,p ,o ,graph1866
`(:dimensions ,(cons (graph-dimension) dimensions))))))1868
;; then, collect any statements for which an index applies and translate them into index forms 1869
(let* ((indexed-statements ())1870
(statements-by-index (loop with cache = ()1872
for operator = (first form)1875
(let* ((predicate (statement-predicate form))1876
(index (repository-index *transaction* predicate)))1878
(push form indexed-statements)1879
(push form (getf cache index))))))1880
finally (return cache)))1881
(variables-by-index (loop for (index statements) on statements-by-index by #'cddr1882
append (list index (expression-variables statements))))1883
(indexed-filters ())1884
(filters-by-index (loop with cache = ()1886
for operator = (first form)1889
(let* ((variables (expression-variables form))1890
(index (loop for (index index-variables) on variables-by-index by #'cddr1891
when (null (set-difference variables index-variables))1894
(push form indexed-filters)1895
(push form (getf cache index))))))1896
finally (return cache)))1897
(index-statements (loop for (index1 statements) on statements-by-index by #'cddr1898
for (index2 filters) on filters-by-index by #'cddr1899
do (assert (eq index1 index2) ()1900
"corrupt bgp index cache: ~s ~s ~s"1904
append (compute-index-statements index1 statements filters))))1905
;; then remove those statements from the standard matching process1906
(setf body (loop for form in body1907
unless (or (member form indexed-statements) (member form indexed-filters))1909
(let* ((collected-form `(bgp:and ,@index-statements)))1910
(flet ((append-form (form)1911
(ecase (first collected-form)1913
(push form (rest (last collected-form))))1915
(setf collected-form `(bgp:and ,collected-form ,form))))))1916
;; and generate the match expression1917
(loop for form in body1918
for (operator . operands) = form1920
((spocq.a:|graph| spocq.a:|slice| spocq.a::|id| spocq.a::|declare| spocq.a::|equivalents|)1921
;; already extracted1924
(destructuring-bind (s p o c &rest options) operands1926
(cond ((property-path-p p)1927
`(bgp:quad-path ,s ,p ,o ,c ,@options))1928
((extension-operator-p p)1929
`(bgp:quad-call ,s ,p ,o ,c ,@options))1931
#+(or) ;; entailment is bgp-based, note statement based1932
(let ((entailed-pattern (compute-entailment-pattern *task* form)))1933
(if (eq form entailed-pattern)1934
`(bgp:quad ,s ,p ,o ,c ,@options)1935
(append entailed-pattern options)))1936
`(bgp:quad ,s ,p ,o ,c ,@options)))))1937
(ecase (first collected-form)1939
(push quad-form (rest (last collected-form))))1941
(setf collected-form `(bgp:and ,collected-form ,quad-form)))))))1943
(ecase (first collected-form)1945
(setf collected-form1946
`(bgp:filter ,collected-form (spocq.a:|&&| ,@(copy-tree operands)))))1948
(setf (rest (last (third collected-form))) (copy-tree operands)))))1949
;; compound forms rewrite the body and replace the resuling and with their1950
;; respective equivalent1952
(append-form (rewrite-body operands)))1954
(append-form `(bgp:not ,@(rest (rewrite-body operands)))))1956
(append-form `(bgp:or ,@(rest (rewrite-body operands)))))1958
(append-form `(bgp:union ,@(rest (rewrite-body operands)))))1960
(append-form `(bgp:xor ,@(rest (rewrite-body operands)))))1961
(t ;; include as-is - eg index match1962
(append-form form)))1963
finally (return collected-form)))))))1964
`(lambda (&key (bindings (when *task* (let ((bindings (query-dynamic-bindings *task*))) (mapcar #'cons (first bindings) (rest bindings)))))1965
(modifiers ',slice) (result-field nil))1966
(trace-algebra bgp:bgp ',body)1967
(funcall ,(rewrite-body body) result-field bindings modifiers))))1970
;;; (parse-sparql "select * where {?s ?p ?o . filter(?o > 2) filter(?s != <http://>) }")