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

KindCoveredAll%
expression31140 22.1
branch08 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; -*-
2
 
3
 (in-package :org.datagraph.spocq.implementation)
4
 
5
 (:documentation "This file defines general operators for abstract sparql query (sse) s-expressions for
6
  the 'org.datagraph.spocq' RDF engine."
7
 
8
  (copyright
9
   "Copyright 2010 [james anderson](mailto:james.anderson@setf.de) All Rights Reserved.")
10
 
11
  (long-description
12
   "The core of each query is an operation and an sse-encoded query expression.[0],[1],[2]
13
  The same sse may appear in a request in combination with different operations:
14
 
15
     {cast, spocq, query, [ask, [], [leftjoin, [bgp, {triple, {?, s}, {?, p}, {?, o}}]]]}
16
     {cast, spocq, query, [construct, [{triple, {?, s}, {?, p}, {?, o}}], [leftjoin, [bgp, {triple, {?, s}, {?, p}, {?, o}}]]]}
17
     {cast, spocq, query, [describe, [{?, s}], [leftjoin, [bgp, {triple, {?, s}, {?, p}, {?, o}}]]]}
18
     {cast, spocq, query, [select, [{?, s}, {?, p}, {?, o}], [leftjoin, [bgp, {triple, {?, s}, {?, p}, {?, o}}]]]}
19
 
20
  in order for compile-query to isolate the stages of a query in order that they run asynchronously, it must 
21
  abstract the sse over the bgp forms. abstract-query-expression walks the sse, identifies the bgp forms,
22
  replaces them with variables and returns the abstract expression and the binding environment to
23
  compile-query for it to construct asynchronous functions.
24
  and constructs a lambda which binds the respective arguments to keyword parameters. These are
25
  supplied subsequently as each bdg store request completes. Once all are resolved, the query is
26
  'runnable' to produce a result and generate a response.
27
 
28
  The store request includes also any from clauses as optional arguments, which are passed
29
  to the store in addition to the bgp expression. Depending on the account status, the
30
  store may ignore them.
31
 
32
  The algebra function is computed by abstracting the sse over the bgp operations.
33
  Thare are frmoved, to be passed to the store for asynchronous retrieveal and integration.
34
  When the results return, they are marked with a unique variable, which corresponds to the
35
  abstracted term in the transformed sse. The query object collected them and applies the
36
  algebra function one all have been resolved.
37
 
38
  The sse perators remain unchanged in the abstract expression.
39
  For each operator a spocq.a macro rewrites the abstract query form to the proper argument and
40
  control structure for the respective spocq.e exaluation function.
41
 
42
  ---
43
  [0] : http://openjena.org/wiki/SSE
44
  [1] : http://jena.sourceforge.net/ARQ/algebra.html
45
  [2] : http://www.openjena.org/wiki/ARQ/Manipulating_SPARQL_using_ARQ "))
46
 
47
 
48
 (defun canonicalize-algebra-arguments (&key limit (count limit) end offset start test 
49
                                             distinct reduced slice)
50
   (flet ((clamp (argument)
51
            (typecase argument
52
              (number (max argument 0))
53
              (t argument))))
54
     (append (cond (count
55
                    (cond (start `(:start ,(clamp start) :end ,(clamp (+ start count))))
56
                          (offset `(:start ,(clamp offset) :end ,(clamp (+ offset count))))
57
                          (t `(:start 0 :end ,(clamp count)))))
58
                   (end
59
                    (cond (start
60
                           `(:start ,(clamp start) :end ,(clamp end)))
61
                          (offset
62
                           `(:start ,(clamp offset) :end ,(clamp end)))
63
                          (t `(:start 0 :end ,(clamp end)))))
64
                   (offset
65
                    `(:start ,(clamp offset)))
66
                 (start
67
                  `(:start ,(clamp start)))
68
                 (slice
69
                  (destructuring-bind (offset count) slice
70
                    `(:start ,(clamp offset) :end ,(clamp (+ offset count))))))
71
             (when test `(:test ,test))
72
             ;; distinct and reduced for query text generation
73
             (when distinct `(:distinct ,distinct))
74
             (when reduced `(:reduced ,reduced)))))
75
 
76
 (defparameter *order-slice-limit* 100000)
77
 
78
 (defgeneric compute-expression-slice (expression &key)
79
   (:documentation "Rewrite a given operation expression to push a slice specification into the
80
  operator's arguments. The effect is limited to
81
  - operators which support the arguments, eg join, project, and select
82
  - a default bgp
83
  - a bgp in a graph scope
84
 
85
  If the operator does not permit the arguments, return nil.
86
  the result always reduces slice arguments to start/end and bgp elements to offset/count")
87
 
88
   (:method ((expression cons) &rest args &key start end offset count)
89
     (declare (ignore start end offset count))
90
     (when args
91
       (destructuring-bind (&key start end) (setf args (apply #'canonicalize-algebra-arguments args))
92
         ;; only start and end belong in a a slice
93
         (case (first expression)
94
           ((spocq.a:|distinct| spocq.a:|slice| spocq.a:|join| spocq.a:|extend|
95
                     spocq.a:|leftjoin| spocq.a:|project| spocq.a:|reduced|
96
                     spocq.a:|union| spocq.a:|select|)
97
            `(let ((*channel-size-limit* *channel-sliced-size-limit*)
98
                   (*field-page-length* *field-sliced-page-length*)) (,@expression ,@args)))
99
           (spocq.a:|bgp|
100
                    `(let ((*channel-size-limit* *channel-sliced-size-limit*)
101
                           (*field-page-length* *field-sliced-page-length*))
102
                       (spocq.a:|bgp|
103
                                ,@(when start `((spocq.a:|slice| ,start ,(when end (- end start)))))
104
                                ,@(rest expression))))
105
           (spocq.a:|graph|
106
                    (destructuring-bind (name group-graph-pattern) (rest expression)
107
                      (when (bgp-form-p group-graph-pattern)
108
                        `(let ((*channel-size-limit* *channel-sliced-size-limit*)
109
                               (*field-page-length* *field-sliced-page-length*))
110
                           (spocq.a:|graph| ,name
111
                                    (,(first group-graph-pattern)
112
                                     ,@(when start `((spocq.a:|slice| ,start ,(when end (- end start)))))
113
                                     ,@(rest group-graph-pattern)))))))
114
           (spocq.a:|order|
115
             (when (and start end (<= (- end start) *order-slice-limit*))
116
               ` (,@expression ,@args)))
117
           (t nil)))))
118
 
119
   (:method ((expression t) &key &allow-other-keys)
120
     nil))
121
     
122
 (defun abstract-query-expression (sse-expression)
123
   "Given an SSE, compute an operator to issue any BGP requests to a store, an operator to combine the
124
  results, and a list of the binding names."
125
   (let* ((bgp-bindings '())
126
          (sse-variables '())
127
          (abstracted-expression nil))
128
     (flet ((abstract-sse-node (node)
129
              (cond ((or (bgp-form-p node) (graph-form-p node))
130
                     ;; replace graph or bgp exressions with a variable to be bound
131
                     ;; to the delegated query result
132
                     (setf sse-variables (union sse-variables (expression-variables node)))
133
                     (let ((variable (cons-uuid-symbol )))
134
                       (setf bgp-bindings (acons variable node bgp-bindings))
135
                       variable))
136
                    ((variable-p node)
137
                     (pushnew node sse-variables)
138
                     node)
139
                    (t
140
                     node))))
141
       (setf abstracted-expression
142
             (map-tree #'abstract-sse-node sse-expression))
143
       (values abstracted-expression
144
               bgp-bindings
145
               sse-variables))))
146
 
147
 
148
 #+(or)
149
 (progn
150
   (in-package :ORG.DATAGRAPH.SPOCQ.IMPLEMENTATION)
151
   (subst-map-if #'(lambda (x) (1- x)) #'(lambda (n) (and (numberp n) (oddp n))) '((1 2 (3 (4 . 5)))))
152
 
153
   (compute-query-lambda (spocq.a:graph :g1
154
                                        (spocq.a:bgp (spocq.a:triple ?x ?p ?v))))
155
 
156
   (compute-query-lambda (spocq.a:project (?s ?v1 ?v2)
157
                                          (spocq.a:leftjoin
158
                                           (spocq.a:bgp (spocq.a:triple ?s :p1 ?v1))
159
                                           (spocq.a:bgp (spocq.a:triple ?s :p2 ?v2))
160
                                           (< ?v1 3))))
161
 
162
   (compute-query-lambda (spocq.a:project (?name)
163
                                          (spocq.a:order (?name (desc ?x))
164
                                                         (spocq.a:bgp (spocq.a:triple ?x :name ?name)))))
165
   )
166
 
167
 #|
168
 ;; canonical parses:
169
 bin/qparse --print=op "PREFIX : <http://example/>
170
  SELECT * 
171
  {
172
    GRAPH :g1 { ?x ?p ?v }
173
  }"
174
 
175
 bin/qparse --print=op "PREFIX : <http://example/>
176
  SELECT ?s ?v1 ?v2 { ?s :p1 ?v1 OPTIONAL {?s :p2 ?v2 FILTER(?v1<3) } }"
177
 
178
 bin/qparse --print=op "PREFIX foaf:    <http://xmlns.com/foaf/0.1/>
179
 
180
  SELECT ?name
181
  WHERE { ?x foaf:name ?name }
182
  ORDER BY ?name DESC(?x)"
183
 
184
 |#