Coverage report: /development/source/library/org/datagraph/spocq-shard/src/algebra/operators/bgp.lisp

KindCoveredAll%
expression358481 74.4
branch2238 57.9
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; -*-
2
 
3
 (in-package :org.datagraph.spocq.implementation)
4
 
5
 (:documentation "This file implements the BGP operator for the 'org.datagraph.spocq' RDF engine."
6
 
7
  (copyright
8
   "Copyright 2010 [james anderson](mailto:james.anderson@setf.de) All Rights Reserved."
9
   "Copyright 2019 [james anderson](mailto:james.anderson@setf.de) All Rights Reserved.")
10
 
11
  (long-description
12
   "The bgp operator arranges to match its statement patterns against the content
13
  of a repository and combine their results to yield a solution stream.
14
  The ultimate arrangement is likely not the direct join of the original
15
  statement pattern sequence. It is the result of various transformations aimed
16
  at optimization, query abstraction and composition or extension functions.
17
  Each aim is addressed by its own phase
18
    - :statement-combinations : combine statement patterns with possible
19
        joined partitions, filters, property path expansion, ...
20
    - :inferences : extend the bgps entailment through pattern-based inference rules
21
    - :views : coalesce and bind view references
22
    - :functions : coalesce and bind function calls
23
 
24
  20210527:
25
   - expand property paths       - introducing statements which may migrate separately
26
   - annotate patterns           - augment them with cardinality and dimensions
27
   - fold filters                - rewrite for constant and same term filters
28
   - expand n3 formula           - migrate any nested formula to yield a join tree
29
                                  expand any formula into either a constant reference
30
                                  or variable to join with an additional graph pattern.
31
   - rewrite per inference rules - rewrite statement patterns as per inference rules
32
   - collate index forms         - isolate statements and filters which utilize an alternative index
33
   - collate star patterns       - collect and isolate patterns for respective subjects
34
   - iterate or join             - arrange statements for either nested loops or scanned joins
35
   - expand function references  - arrange to invoke a function to extend bindings
36
   - expand views                - arrange to invoke a view and incorporate its solutions
37
   - suppress null results       - test statement cardinality and eliminate the bgp if some yields no solution
38
   - construct agp
39
 
40
  one macroexpand-bgp-phase method corresponds to each step.
41
  where the operation requires a complex implementation, the individual
42
  steps are implemented in core/agp.lisp
43
  each step accepts a sequence of forms - statement patterns, folded operators, annotations, and produces a form.
44
  in most cases that is a bgp
45
 "))
46
 
47
 
48
 (defmacro spocq.a:|bgp| (&body body &environment env)
49
   (macroexpand-bgp body env))
50
 
51
 (defmacro base-bgp (&body body &environment env)
52
    (macroexpand-bgp body env *macroexpand-bgp-base-phases*))
53
 
54
 (defmacro collated-bgp (&body body &environment env)
55
   (macroexpand-bgp body env *macroexpand-bgp-base-phases*))
56
 
57
 
58
 (defun macroexpand-bgp (body env
59
                         &optional
60
                         (phases *macroexpand-bgp-phases*))  
61
   "Given the bgp statement patterns &co, rewrite it as per ordered phases.
62
   Each phase must return either
63
   - null, which yields a unit table
64
   - bgp, which is further expanded
65
   - agp, which is returned
66
   - an express tree of algebra operators, agp and brb forms
67
   For each which returns a bgp form, the operator is popped tand the process continues.
68
   Once either the phases are completed or some other form is returned, return the
69
   last result.
70
   If no phase is specified, then just compute an agp."
71
   (if phases
72
       (labels ((walk-expansion (form)
73
                  (typecase form
74
                    (null
75
                     `(spocq.a:|table| ,(expression-dimensions body)))
76
                    (cons
77
                     (case (first form)
78
                       (spocq.a:|bgp|
79
                        ;; return the result from the remaining phases
80
                        (macroexpand-bgp (rest form) env phases))
81
                       ((spocq.a:|agp| spocq.a:|null| spocq.a:|filter| spocq.a:|extend|)
82
                        ;; return as final result
83
                        form)
84
                       ;; deconstruct other forms and continue
85
                       ;; must to perform expansion from the next stage, rather
86
                       ;; than return the entire form as that would start form the beginning
87
                       (spocq.a:|join|
88
                        (destructuring-bind (arg1 arg2 . rest)
89
                                            (rest form)
90
                          `(,(first form)
91
                            ,(walk-expansion arg1)
92
                            ,(walk-expansion arg2)
93
                            ,@rest)))
94
                       (spocq.e:slice
95
                        (destructuring-bind (field . rest) (rest form)
96
                          `(,(first form) ,(walk-expansion field) ,@rest)))
97
                       (t
98
                        (error "invalid bgp expansion ~a : ~a" body form))))
99
                    (t
100
                     (error "invalid bgp expansion ~a : ~a" body form)))))
101
         (walk-expansion (macroexpand-bgp-phase (pop phases) body env)))
102
       ;; with no phases left, just compute the agp instance
103
       (macroexpand-bgp-base body env)))
104
 
105
 
106
 (defgeneric macroexpand-bgp-phase (phase body env)
107
   (:documentation "Expand a BGP in named phases")
108
 
109
   (:method ((phase (eql :annotate-patterns)) body env)
110
     "Augment a collection of bgp element forms with information about
111
      dimensionality and cardinality.
112
      Include a naive aggregate cardinality.
113
      Replace blank nodes with fresh identifiers in order to isolate it
114
      from any context, but do so here, as the first step, in order to effect
115
      natural joins across any decompositions.
116
      This is intended to be the first phase, as others depend on the
117
      annotations."
118
     (let* ((graph (second (assoc 'spocq.a:|graph| body)))
119
            (annotated-body (annotate-statement-patterns
120
                             *repository*
121
                             body
122
                             :graph (etypecase graph
123
                                      ((satisfies variable-p) (or (dataset-named-graphs *task*) |urn:dydra|:|all|))
124
                                      (null (dataset-default-graphs *task*))
125
                                      (iri graph))))
126
            (cardinality (compute-bgp-cardinality annotated-body)))
127
       (list* 'spocq.a:|bgp|
128
              `(declare (spocq.e::cardinality ,cardinality))
129
              (sublis (loop for node in (expression-blank-nodes annotated-body)
130
                        collect (cons node (cons-variable "BGP_")))
131
                      annotated-body)))))
132
 
133
 
134
 (defmethod macroexpand-bgp-phase ((phase (eql :rewrite-paths)) body env)
135
   ;; expand any simple paths
136
   (expand-bgp-property-paths body))
137
 
138
         
139
 (defmethod macroexpand-bgp-phase ((phase (eql :fold-filters)) body env)
140
   (declare (ignore env))
141
   (multiple-value-bind (patterns equivalents filters)
142
                        (fold-filter-constants body)
143
     ;; any filters which have been left over did not permit folding
144
     (let ((result `(spocq.a:|bgp| ,@patterns ,@filters)))
145
       ;; any equivalents need to be reintroduced by extending the field
146
       (loop for (variable . constraint) in equivalents
147
         do (setf result `(spocq.a:|extend| ,result ,variable ,constraint)))
148
      result)))
149
 
150
 
151
 (defmethod macroexpand-bgp-phase ((phase (eql :rewrite-formula)) body env)
152
   "Replace any bgp forms in a subject or object term position with
153
  the bgp graph's content identifier if it is constant or a reference
154
  join a graph form which unifies a variable graph term with its
155
  delegate in-lin in the original bgp.
156
   Returns an expansion with components which permit further expansion."
157
   (let* ((nested-bgps ()))
158
     (labels ((unnest-statement (statement)
159
                (destructuring-bind (subject predicate object . rest) (rest statement)
160
                  `(spocq.a:|triple| ,(unnest-term subject)
161
                            ,predicate
162
                            ,(unnest-term object)
163
                            ,@rest)))
164
              (unnest-term (term)
165
                (if (bgp-form-p term)
166
                    (compute-bgp-reference term)
167
                    term))
168
              (compute-bgp-reference (bgp)
169
                (if (null (expression-variables bgp))
170
                    ;; substitute for the graph hash
171
                    (compute-formula-identifier bgp)
172
                    (let ((variable (cons-variable))
173
                          (nested-bgp (macroexpand-bgp-phase :rewrite-formula (rest bgp) env)))
174
                      (push `(spocq.a:|bgp| (spocq.a:|graph| ,variable) ,@(rest nested-bgp)) nested-bgps)
175
                      variable))))
176
       ;; iterate over statements to examine each one and either
177
       ;; turn it into a reference to the designated from or
178
       ;; return it unchanged
179
       (let ((result `(spocq.a:|bgp| ,@(loop for statement in body
180
                                         collect (if (triple-form-p statement)
181
                                                     (unnest-statement statement)
182
                                                     statement)))))
183
         (loop for nested-bgp in nested-bgps
184
           do (setf result `(spocq.a:|join| ,nested-bgp ,result)))
185
         result))))
186
 
187
 
188
 ;;; the entailment expansion replaces or augments the statement patterns with
189
 ;;; others which match the related, antecedent statements.
190
 
191
 (defmethod macroexpand-bgp-phase ((phase (eql :rewrite-inferences)) body env)
192
   "Compute an 'entailment expansion'.
193
  Replaces and/or augment the statement patterns with others which match their
194
  related, antecedent statements."
195
   (let ((library (query-library *task*))
196
         (repository (task-repository *task*)))
197
     (if library
198
         (multiple-value-bind (expansion cached-p)
199
                              (find-bgp-expansion repository body library)
200
           (if cached-p
201
               expansion
202
               (let ((rewritten (rewrite-bgp body library repository env)))
203
                 (values (setf (find-bgp-expansion repository body library) rewritten)
204
                         t))))
205
         (cons 'spocq.a:|bgp| body))))
206
 
207
 (defmethod macroexpand-bgp-phase ((phase (eql :collate-indexes)) body env)
208
   (declare (ignore env))
209
   (multiple-value-bind (indexed-partitions other-partition slice-form)
210
                        (collate-indexed-bgp-forms body)
211
     (let ((indexed-forms (loop for partition in indexed-partitions
212
                            ;; all predicates are constant: no further transformation necessary
213
                            collect (list 'spocq.a:|agp|
214
                                          (cons '(declare (spocq.e::processing-mode indexed))
215
                                                partition))))
216
           (other-form (when other-partition (cons 'spocq.a:|bgp| other-partition))))
217
        (if indexed-forms
218
           (let ((join-form (compute-nested-join (if other-form
219
                                                     (cons other-form indexed-forms)
220
                                                     indexed-forms))))
221
             (if slice-form
222
                 `(spocq.e:slice ,join-form ,@(rest slice-form))
223
                 join-form))
224
           (append other-form (when slice-form (list slice-form)))))))
225
 
226
 (defmethod macroexpand-bgp-phase ((phase (eql :collate-subjects)) body env)
227
   (declare (ignore env))
228
   (multiple-value-bind (subject-partitions other-partition slice-form)
229
                        (collate-subject-bgp-forms body)
230
     (let ((subject-forms (loop for partition in subject-partitions
231
                            ;; all predicates are constant: no further transformation necessary
232
                            collect (list 'spocq.a:|agp|
233
                                          (if (> (count-if #'triple-form-p partition) 1)
234
                                              (cons '(declare (spocq.e::processing-mode :collated))
235
                                                    partition)
236
                                              partition))))
237
           (other-form (when other-partition (cons 'spocq.a:|bgp| other-partition))))
238
       (if subject-forms
239
           (let ((join-form (compute-nested-join (if other-form
240
                                                     (cons other-form subject-forms)
241
                                                     subject-forms))))
242
             (if slice-form
243
                 `(spocq.e:slice ,join-form ,@(rest slice-form))
244
                 join-form))
245
           (append other-form (list slice-form))))))
246
 
247
 
248
 (defmethod macroexpand-bgp-phase ((phase (eql :iterate-or-join)) body env)
249
   "Examine a sequence of bgp forms to determine whether to execute them iteratively or
250
    to combine them as nested joins.
251
    To this point all cases which concern indices or star patterns have already been
252
    factored into other bgp forms, all rules have been expanded as well as all static property paths.
253
    Each statement pattern has been annotated with its cardinality, which determines
254
    which arrangement to follow.
255
 
256
    the repository is used to specialize the logic only. statement counts have alread been established."
257
   (let* ((repository (task-repository *task*)))
258
     (cond ((null (rest body))
259
            body)
260
           (t
261
            (let* ((partitions (compute-repository-pattern-partitions repository body))
262
                   (match-scan-partitions
263
                    (loop for partition in partitions
264
                      append (compute-match-scan-partitions repository
265
                                                            (sort partition
266
                                                                  #'<
267
                                                                  :key #'(lambda (form)
268
                                                                           (if (triple-form-p form)
269
                                                                               (statement-count form)
270
                                                                               1))))))
271
                   (match-scan-forms (loop for partition in match-scan-partitions
272
                                       collect (cons 'spocq.a:|bgp| partition))))
273
              (compute-nested-join match-scan-forms))))))
274
 
275
 
276
 (defmethod macroexpand-bgp-phase ((phase (eql :suppress-null-cardinality)) body env)
277
   (let ((statements (remove-if-not #'elementary-bgp-statement-form-p body))
278
         (graph (second (assoc 'spocq.a:|graph| body))))
279
     (cond ((and *bgp.suppress-null-patterns*
280
                 (operation-read-only-p *task*))
281
            ;; suppress graph patterns which _statically_ fail to match the store.
282
            ;; this must not take bindings into account as that would compromise the query's abstraction
283
            ;; the probe is against _all_ graphs + default.
284
            ;; otherwise this would need to emulate the from/from named semantics (see sparql11/construct/constructwhere04
285
            (loop for pattern in statements
286
              do (when (zerop (or (statement-count pattern) 1))
287
                   (log-notice "suppress bgp : (~s . ~a) due to ~a" graph statements pattern)
288
                   (let ((dimensions (expression-dimensions statements)))
289
                     (when (variable-p graph)
290
                       (pushnew graph dimensions))
291
                     (return-from macroexpand-bgp-phase
292
                       (values `(spocq.a:|null| ,dimensions)
293
                               t)))))
294
            (cons 'spocq.a:|bgp| body))
295
           (t
296
            (values (cons 'spocq.a:|bgp| body)
297
                    (not (null (find 0 (remove-if-not #'elementary-bgp-statement-form-p body)
298
                                     :test #'eql :key #'statement-count))))))))
299
 
300
 
301
 (defmethod macroexpand-bgp-phase ((phase (eql :bind-views)) body env)
302
   "if any view references are present, coalese and transform them into sub-select operations"
303
   (let* ((triples (remove-if-not #'triple-form-p body))
304
          (views (remove-duplicates (loop for triple in triples
305
                                     for predicate = (statement-predicate triple)
306
                                     if (and (iri-p predicate)
307
                                             (let ((repository-id (iri-service-repository-id predicate)))
308
                                               (and repository-id
309
                                                    (repository-exists-p repository-id))))
310
                                     collect predicate))))
311
    (cons 'spocq.a:|bgp|  (if views
312
                              (coalesce-bgp-views views body)
313
                              body))))
314
 
315
 
316
 (defmethod macroexpand-bgp-phase ((phase (eql :bind-functions)) body env)
317
   "if any function references are present, coalese and transform them into sub-select operations."
318
   (let* ((triples (remove-if-not #'triple-form-p body))
319
          (functions (remove-duplicates (loop for triple in triples
320
                                          for predicate = (statement-predicate triple)
321
                                          if (extension-operator-p predicate)
322
                                          collect predicate))))
323
     (cons 'spocq.a:|bgp| (if functions
324
                              (coalesce-bgp-functions functions body)
325
                              body))))
326
 
327
 
328
 (defmethod macroexpand-bgp-phase ((phase (eql :base)) body env)
329
   "if any function references are present, coalese and transform them into sub-select operations."
330
   (macroexpand-bgp-base body env))
331
 
332
           
333
 (defun macroexpand-bgp-base (body env)
334
   "The base expansion phase operates on a static body.
335
   all splitting, path expansion, formulae or rule rewriting has happened.
336
   the argument body is transformed in to a form which constructs an agp.
337
 
338
   the bgp may be in a declaration scope
339
   - base dimensions : some dimensions may be declared crossed over from an
340
     opposite join leg to cause the bgp to accept a base solution field.
341
   - reference-dimensions : dimensions refered to in forms for which this bgp
342
     contributes a solution field
343
 
344
   the bgp may carry annotations:
345
   - equivalents : variable or variable-value pairs which are to be enforced
346
     against matches
347
   - slice : solution generation start/count constraints
348
   - graph : the graph expression from a containing scope
349
   - default/named graph : carried from the dataset definition
350
   - bindings : pushed bindings from a values clause to be treated
351
     as the equivalent of a base solution field
352
 
353
   reduce the statements to just the pattern, buindings and filters and
354
   create an agp with those as the body and the other attributes as slot
355
   bindings.
356
 "
357
   (let* ((statements (remove-if-not #'bgp-statement-form-p body))
358
            (filter-forms (remove-if-not #'filter-form-p body))
359
            ;; marshal annotations
360
            ;; ... from the query expression
361
            (graph (second (assoc 'spocq.a:|graph| body)))
362
            (default-graph-term (assoc 'spocq.a::|from| body))
363
            (named-graph-term (assoc 'spocq.a::|from-named| body))
364
            (slice-form (assoc 'spocq.a:|slice| body))
365
            ;; ... from folded filter predicates
366
            (equivalents (rest (assoc 'spocq.a::|equivalents| body)))
367
            ;; ... from joined values clauses
368
            (bgp-bindings (assoc 'spocq.a:|bindings| body))
369
            (bind-forms (remove-if-not #'bind-form-p body))
370
            ;; marshal relevant declarations
371
            ;; incorporate dimensionality of propagation sources
372
            (reference-dimensions (declaration-information 'spocq.e::reference-dimensions env))
373
            ;; ... for visibility constraints per temporal value or revision
374
            (temporal-attributes (declaration-information 'spocq.e::temporal-attribute env))
375
            (version-constraints (declaration-information 'spocq.e::version-constraint env))
376
            (join-scope (declaration-information 'spocq.e::join-scope env))
377
            (processing-mode (declaration-information 'spocq.e::processing-mode env))
378
            ;; extract the variable - constant equivalents
379
            (pattern-variables (expression-variables statements))
380
            (temporal-constraints (loop for (variable binding) in temporal-attributes
381
                                    when (find variable pattern-variables)
382
                                    collect `(,variable ,binding))))
383
       (labels ((construct-agp (patterns)
384
                  (let ((pattern-dimensions (expression-dimensions patterns)))
385
                    (flet ((propagation-arity (declared-dimensions)
386
                             (length (intersection declared-dimensions pattern-dimensions))))
387
                      (declare (dynamic-extent #'propagation-arity))
388
                      (let* ((base-dimension-declarations (remove-if #'zerop (declaration-information 'spocq.e:base-dimensions env)
389
                                                                     :key #'propagation-arity))
390
                             ;; select the possible source which contributes the most
391
                             (base-dimensions (first (if (rest base-dimension-declarations)
392
                                                     (sort (copy-list base-dimension-declarations) #'> :key #'propagation-arity)
393
                                                     base-dimension-declarations)))
394
                             (variables (expression-variables patterns))
395
                             (equivalents (remove-if-not #'(lambda (equiv) (find (rest equiv) variables)) equivalents))
396
                             (agp-body `((,@(when graph `((spocq.a:|graph| ,graph)))
397
                                            ,@(when default-graph-term (list default-graph-term))
398
                                            ,@(when named-graph-term (list named-graph-term))
399
                                            ,@(append bind-forms filter-forms patterns)
400
                                            ,@(when slice-form (list slice-form))
401
                                            ,@(when equivalents `((spocq.a::|equivalents| ,@equivalents))))
402
                                         :base-dimensions ',base-dimensions
403
                                         :reference-dimensions ',reference-dimensions
404
                                         :join-scope ',join-scope
405
                                         :temporal-constraints ',temporal-constraints
406
                                         :version-constraints ',version-constraints
407
                                         ,@(when processing-mode `(:processing-mode ',processing-mode)))))
408
                        ;; retitle the bgp to indicate the augmentation
409
                        (cons 'spocq.a:|agp| agp-body))))))
410
         (let ((result (construct-agp body)))
411
           (when bgp-bindings
412
             (setf result `(spocq.a:|join| ,bgp-bindings ,result)))
413
           result))))
414
 
415
 
416
 #+(or)
417
 (
418
 (macroexpand-bgp-phase :formula 
419
                        '((ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
420
                                                       (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
421
                                                                                    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <_:f1>
422
                                                                                                                 <http://example.org/superpred1> 0)
423
                                                                                    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <_:f1>
424
                                                                                                                 <http://example.org/superpred1> 1)
425
                                                                                    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <_:f1>
426
                                                                                                                 <http://example.org/superpred2> 2))
427
                                                       <http://example.org/predicate> 3))
428
                        nil)
429
 (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
430
   (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
431
    <urn:n-triples:6a9a7cab8c7b33e8775b7011555dbca97b8e0425597b78413a7f6c4730051084>
432
    <http://example.org/predicate> 3))
433
 
434
 (macroexpand-bgp-phase :formula 
435
                        '((ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
436
                                                       <http://example.org/subject>
437
                                                       <http://example.org/predicate>
438
                                                       (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
439
                                                                                    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <_:f1>
440
                                                                                                                 <http://example.org/superpred1> 0)
441
                                                                                    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <_:f1>
442
                                                                                                                 <http://example.org/superpred1> 1)
443
                                                                                    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <_:f1>
444
                                                                                                                 <http://example.org/superpred2> 2))))
445
                        nil)
446
 (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
447
   (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <http://example.org/subject>
448
                                         <http://example.org/predicate>
449
                                         <urn:n-triples:6a9a7cab8c7b33e8775b7011555dbca97b8e0425597b78413a7f6c4730051084>))
450
 
451
 (macroexpand-bgp-phase :formula 
452
                        '((ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
453
                                                       <http://example.org/subject>
454
                                                       <http://example.org/predicate>
455
                                                       (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
456
                                                                                    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <_:f1>
457
                                                                                                                 <http://example.org/superpred1> ?::o))))
458
                        nil)
459
 (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|join|
460
  (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|graph| ?::?1
461
                                       (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
462
                                         (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
463
                                          <_:f1> <http://example.org/superpred1>
464
                                          ?::O)))
465
  (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
466
    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <http://example.org/subject>
467
                                          <http://example.org/predicate> ?::?1)))
468
 
469
 (macroexpand-bgp-phase :formula 
470
                        '((ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
471
                                                       <http://example.org/subject>
472
                                                       <http://example.org/predicate>
473
                                                       (spocq.a:|bgp|
474
                                                         (spocq.a:|triple| <_:f1> <http://example.org/superpred1> ?::o))))
475
                        nil)
476
 (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|join|
477
  (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|graph| ?::?1
478
                                       (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
479
                                         (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
480
                                          <_:f1> <http://example.org/superpred1>
481
                                          ?::O)))
482
  (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|bgp|
483
    (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| <http://example.org/subject>
484
                                          <http://example.org/predicate> ?::?1)))
485
 
486
 
487
 (macroexpand-bgp-phase :formula 
488
                        '((ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
489
                                                       <http://example.org/subject>
490
                                                       <http://example.org/predicate>
491
                                                       (spocq.a:|bgp|
492
                                                         (spocq.a:|triple| <_:f1>
493
                                                                           <http://example.org/subpred1>
494
                                                                           (spocq.a:|bgp|
495
                                                                             (spocq.a:|triple| <_:f1> <http://example.org/subpred2> 1))))))
496
                        nil)
497
 
498
 (pprint-sse
499
 (macroexpand-bgp-phase :formula 
500
                        '((ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple|
501
                                                       <http://example.org/subject>
502
                                                       <http://example.org/predicate>
503
                                                       (spocq.a:|bgp|
504
                                                         (spocq.a:|triple| <_:f1>
505
                                                                           <http://example.org/subpred1>
506
                                                                           (spocq.a:|bgp|
507
                                                                             (spocq.a:|triple| <_:f1> <http://example.org/subpred2> ?::o))))))
508
                        nil))
509
 (join
510
  (graph ??6
511
         (join
512
          (graph ??7
513
                 (bgp
514
                   {<_:f1> <http://example.org/subpred2> ?O}))
515
          (bgp
516
            {<_:f1> <http://example.org/subpred1> ??7})))
517
  (bgp
518
    {<http://example.org/subject> <http://example.org/predicate> ??6}))
519
 
520
 (expand-query "select *
521
 where {
522
  <http://example.org/subject> <http://example.org/predicate>
523
  {_:f1 <http://example.org/subpred1>
524
     { _:f2 <http://example.org/subpred2> ?o } }
525
 }"
526
               :repository-id "james/test"
527
               :agent (system-agent))
528
 <http://www.setf.de/#self> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://xmlns.com/foaf/0.1/Person> .
529
 <http://www.setf.de/#self> <http://xmlns.com/foaf/0.1/name> "James Anderson" .
530
 <http://www.setf.de/#self> <http://xmlns.com/foaf/0.1/homepage> <http://www.setf.de/> .
531
 <http://www.setf.de/#self> <http://xmlns.com/foaf/0.1/mbox> <mailto:anderson.james.1955@gmail.com> .
532
 <http://www.setf.de/#self> <http://xmlns.com/foaf/0.1/made> <https://github.com/lisp/> .
533
 <https://github.com/lisp/> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://usefulinc.com/ns/doap#Project> .
534
 <https://github.com/lisp/> <http://purl.org/dc/terms/creator> <http://www.setf.de/#self> .
535
 
536
 (test-sparql "
537
 select ?what
538
 from <urn:dydra:all>
539
 where
540
 { <http://www.setf.de/#self> <http://xmlns.com/foaf/0.1/made> 
541
   { <http://www.setf.de/#self> a ?what }
542
 }
543
 "
544
              :repository-id "test/test"
545
              :response-content-type mime:application/sparql-query-execution)
546
 
547
 (test-sparql "
548
 select ?what
549
 from <urn:dydra:all>
550
 where
551
 { <http://www.setf.de/#self> <http://xmlns.com/foaf/0.1/made> 
552
   { <http://www.setf.de/#self> a ?what }
553
 }
554
 "
555
              :repository-id "test/test"
556
              :response-content-type mime:application/sparql-query-algebra)
557
 
558
 (trace macroexpand-bgp-phase)
559
 (test-sparql "
560
 select *
561
 from <urn:dydra:all>
562
 where
563
 { <http://www.setf.de/#self> ?p ?o
564
 }
565
 "
566
              :repository-id "test/test"
567
              :response-content-type mime:application/sparql-query-execution)
568
 
569
 
570
 (expand-query "
571
 select ?mbox
572
 from <urn:dydra:all>
573
 where
574
 { <http://www.setf.de/#self> <http://xmlns.com/foaf/0.1/made> 
575
   { <http://www.setf.de/#self> a ?what }
576
 }
577
 "
578
              :repository-id "test/test"
579
              :agent (system-agent))
580
 
581
 )
582
 
583
 #|
584
 0. all combination operators choose a dominant argument, determine its dimensions
585
  and declare those as a source for the other one
586
 
587
 1. when a bgp is compiled, if it is in the scope of a source, it arranges to accept its field as
588
 initial constraints. give more than one source, the higest arity source is used
589
 
590
 2. if no source was available, the bgp executes immediately upon evaluation
591
 
592
 3. if a source is available, the bgp hangs until constraints are available. it is passed up throuh
593
 the chain of generators
594
 
595
 4. once it arrives at a combination which includes an argument which can provide a field of the requisite dimensions, 
596
 the bgp is grafted onto that argument's channel to provides its constraint field.
597
 
598
 
599
 (pprint (compute-nested-join
600
          (compute-pattern-partitions
601
           '((ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|siebelService|
602
                                                   <http://www.ontology-partners.com/is/is.owl#lineTag>
603
                                                   ?::|siebelLineTag|)
604
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|isCircuitsObject|
605
                                                   <http://www.ontology-partners.com/is/is.owl#lineTag>
606
                                                   ?::|iscLineTag|)
607
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|siebelCustomer|
608
                                                   <http://www.ontology-partners.com/sid/product.owl#partyRolePlays>
609
                                                   ?::|siebelParty|)
610
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|siebelCustomer|
611
                                                   <http://www.ontology-partners.com/sid/customer.owl#CustomerPosseses>
612
                                                   ?::|siebelAccount|)
613
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|siebelAccount|
614
                                                   <http://www.ontology-partners.com/sid/customer.owl#customerAccountId>
615
                                                   ?::|accountId|)
616
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|isCircuitsObject|
617
                                                   <http://www.w3.org/1999/02/22-rdf-syntax-ns#type>
618
                                                   <http://www.ontology-partners.com/is/is.owl#IsCircuitInfo>)
619
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|isCircuitsObject|
620
                                                   <http://www.ontology-partners.com/is/is.owl#describesCustomer>
621
                                                   ?::|iscCustomer|)
622
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|iscCustomer|
623
                                                   <http://www.ontology-partners.com/sid/customer.owl#CustomerPosseses>
624
                                                   ?::|iscAccount|)
625
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|iscAccount|
626
                                                   <http://www.ontology-partners.com/sid/customer.owl#customerAccountId>
627
                                                   ?::|accountId|)
628
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|siebelProduct|
629
                                                   <http://www.ontology-partners.com/sid/product.owl#productOfInterestTo>
630
                                                   ?::|siebelParty|)
631
             (ORG.DATAGRAPH.SPOCQ.ALGEBRA:|triple| ?::|siebelProduct|
632
                                                   <http://www.ontology-partners.com/sid/product.owl#productRealizedAsCFService>
633
                                                   ?::|siebelService|)))))
634
 
635
 
636
 (defun macroexpand-bgp (body env)
637
   "if the body should be split, do so, otherwise, just encapsulate the patterns in an agp."
638
   
639
   (multiple-value-bind (statements filters equivalents)
640
                        (reduce-pattern-expressions (remove-if-not #'bgp-statement-form-p body)
641
                                                    (remove-if-not #'filter-form-p body))
642
     (let ((slice (rest (assoc 'spocq.a:|slice| body)))
643
           (graph (second (assoc 'spocq.a:|graph| body)))
644
           (default-graph-term (assoc 'spocq.a::|from| body))
645
           (named-graph-term (assoc 'spocq.a::|from-named| body)))
646
       (labels ((construct-agp (patterns)
647
                (let ((pattern-dimensions (expression-dimensions patterns)))
648
                  (flet ((propagation-arity (declared-dimensions)
649
                           (length (intersection declared-dimensions pattern-dimensions))))
650
                    (declare (dynamic-extent #'propagation-arity))
651
                    (let* ((declarations (remove-if #'zerop (declaration-information 'spocq.e:base-dimensions env)
652
                                                    :key #'propagation-arity))
653
                           ;; select the possible source which contributes the most
654
                           (base-dimensions (first (if (rest declarations)
655
                                                     (sort (copy-list declarations) #'> :key #'propagation-arity)
656
                                                     declarations)))
657
                           (join-scope (declaration-information 'spocq.e::join-scope env))
658
                           (processing-mode (declaration-information 'spocq.e::processing-mode env))
659
                           (agp (apply #'make-agp :body `(,@(when graph `((spocq.a:|graph| ,graph)))
660
                                                          ,@(when default-graph-term (list default-graph-term))
661
                                                          ,@(when named-graph-term (list named-graph-term))
662
                                                          ,@patterns
663
                                                          ,@(when equivalents `((spocq.a::|equivalents| ,@equivalents))))
664
                                       :base-dimensions base-dimensions
665
                                       :join-scope join-scope
666
                                       (when processing-mode (list :processing-mode processing-mode)))))
667
                      `(agp-generator ,agp)))))
668
              (compute-nested-join (partitions)
669
                (let* ((dimensioned-partitions (loop for p in partitions collect (cons (expression-dimensions p)
670
                                                                                       (construct-agp p))))
671
                       (paired-dimensioned-partitions (loop for list on dimensioned-partitions
672
                                                            for first = (first list)
673
                                                            append (loop for second in (rest list)
674
                                                                         collect (list first second))))
675
                       (ordered-pdps (sort (copy-list paired-dimensioned-partitions)
676
                                           #'> :key #'(lambda (pair)
677
                                                        (destructuring-bind (dp1 dp2) pair
678
                                                          (length (intersection (first dp1) (first dp2))))))))
679
                  (destructuring-bind (((dl . left) (dr . right)) . others) ordered-pdps
680
                    (declare (ignore others))
681
                    (let* ((join-form `(spocq.a:|join| ,left ,right))
682
                           (form-variables (union dl dr)))
683
                      (setf dimensioned-partitions (remove left (remove right dimensioned-partitions :key #'rest) :key #'rest))
684
                      (loop (unless dimensioned-partitions (return join-form))
685
                            (when (rest dimensioned-partitions)
686
                              (setf dimensioned-partitions (sort dimensioned-partitions #'>
687
                                                                 :key #'(lambda (d.other) (length (intersection form-variables (first d.other)))))))
688
                            (destructuring-bind ((d . other) . others) dimensioned-partitions
689
                              (setf join-form `(spocq.a:|join| ,join-form ,other))
690
                              (setf form-variables (union form-variables d))
691
                              (setf  dimensioned-partitions others)))
692
                      join-form)))))
693
         (let ((partitions (when (> (length statements) 3)
694
                             (compute-pattern-partitions statements))))
695
           (if (rest partitions)
696
             ;; construct a reduction tree with the largest bgps at the leaves and the
697
             ;; natural joined preferes over cross joins
698
             (let ((form (compute-nested-join partitions)))
699
               (cond (filters
700
                      ;; if there are filters, wrap the form in a new filter. don't try to push now: if it fails
701
                      ;; the filter macro expansion will repeat the process
702
                      `(spocq.a:|filter| ,form
703
                                         ,(if (rest filters)
704
                                            `(spocq.a:|exprlist| ,@(mapcar #'second filters))
705
                                            (second (first filters)))
706
                                         ,@(when slice `(:offset ,(first slice) :count ,(second slice)))))
707
                     (slice
708
                      ;; ad the slice to the outermost join
709
                      (append form `(:offset ,(first slice) :count ,(second slice))))
710
                     (t
711
                      form)))
712
             ;; delay the eventual generator construction until reduction
713
             (construct-agp (append statements
714
                                    filters
715
                                    (when slice `((spocq.a:|slice| ,@slice)))
716
                                    (when equivalents `((spocq.a::|equivalents| ,@equivalents)))))))))))
717
          
718
 
719
 (defgeneric compute-inferred-bgp (library pattern method environment &key class)
720
   (:documentation "Rewrite a bgp form according to entailment rules.
721
    The default method does nothing.
722
    The implementations have complete control over the bgp implementation.
723
    A new form replaces the original.")
724
 
725
   (:method ((library t) (pattern list) (method t) (env t) &rest args)
726
     "The base method returns the pattern unchanged"
727
     (declare (ignore args))
728
     pattern)
729
   (:method ((library t) (pattern list) (methods list) (env t) &rest args)
730
     "A (possibly null) method sequence rewrites the pattern iteratively"
731
     (declare (dynamic-extent args))
732
     (loop for method in methods
733
       do (setf pattern (apply #'compute-inferred-bgp library pattern method env args)))
734
     pattern))
735
 
736
 
737
 |#