Class: RDF::N3::Algebra::Formula

Inherits:
SPARQL::Algebra::Operator show all
Includes:
Enumerable, Builtin, Term, SPARQL::Algebra::Query, SPARQL::Algebra::Update
Defined in:
lib/rdf/n3/algebra/formula.rb

Overview

A Notation3 Formula combines a graph with a BGP query.

Constant Summary collapse

NAME = 
:formula

Instance Attribute Summary collapse

Attributes included from Enumerable

#existentials, #universals

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Builtin

#input_operand, #rank

Methods included from Term

#as_datetime, #as_number, #sameTerm?

Methods inherited from SPARQL::Algebra::Operator

#formulae, #operands=

Instance Attribute Details

#query ⇒ RDF::Query

Query to run against a queryable to determine if the formula matches the queryable.

Returns:



17
18
19
 
# File 'lib/rdf/n3/algebra/formula.rb', line 17

def query
  @query
end

Class Method Details

.from_enumerable(enumerable, **options) ⇒ RDF::N3::Algebra::Formula

Create a formula from an RDF::Enumerable (such as RDF::N3::Repository)

Parameters:

  • enumerable (RDF::Enumerable)
  • options (Hash{Symbol => Object}) —

    any additional keyword options

Returns:



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/rdf/n3/algebra/formula.rb', line 28

def self.from_enumerable(enumerable, **options)
  # SPARQL used for SSE and algebra functionality
  require 'sparql' unless defined?(:SPARQL)

  # Create formulae from statement graph_names
  formulae = {}
  enumerable.graph_names.unshift(nil).each do |graph_name|
    formulae[graph_name] = Formula.new(graph_name: graph_name, formulae: formulae, **options)
  end

  # Add patterns to appropiate formula based on graph_name,
  # and replace subject and object bnodes which identify
  # named graphs with those formula
  enumerable.each_statement do |statement|
    # A graph name indicates a formula.
    graph_name = statement.graph_name
    form = formulae[graph_name]

    # Map statement components to formulae, if necessary.
    statement = RDF::Statement.from(statement.to_a.map do |term|
      case term
      when RDF::Node
        term = if formulae[term]
          # Transform blank nodes denoting formulae into those formulae
          formulae[term]
        elsif graph_name
          # If we're in a quoted graph, transform blank nodes into undistinguished existential variables.
          term.to_ndvar(graph_name)
        else
          term
        end
      when RDF::N3::List
        # Transform blank nodes denoting formulae into those formulae
        term = term.transform {|t| t.node? ? formulae.fetch(t, t) : t}

        # If we're in a quoted graph, transform blank node components into existential variables
        if graph_name && term.has_nodes?
          term = term.to_ndvar(graph_name)
        end
      end
      term
    end)

    pattern = statement.variable? ? RDF::Query::Pattern.from(statement) : statement

    # Formulae may be the subject or object of a known operator
    if klass = RDF::N3::Algebra.for(pattern.predicate)
      form.operands << klass.new(pattern.subject,
                                 pattern.object,
                                 formulae: formulae,
                                 parent: form,
                                 predicate: pattern.predicate,
                                 **options)
    else
      pattern.graph_name = nil
      form.operands << pattern
    end
  end

  # Formula is that without a graph name
  this = formulae[nil]

  # If assigned a graph name, add it here
  this.graph_name = options[:graph_name] if options[:graph_name]
  this
end

Instance Method Details

#deep_dup ⇒ RDF::N3::Algebra::Formula

Duplicate this formula, recursively, renaming graph names using hash function.

Returns:



99
100
101
102
103
104
105
106
107
 
# File 'lib/rdf/n3/algebra/formula.rb', line 99

def deep_dup
  #new_ops = operands.map(&:dup)
  new_ops = operands.map do |op|
    op.deep_dup
  end
  graph_name = RDF::Node.intern(new_ops.hash)
  log_debug("formula") {"dup: #{self.graph_name} to #{graph_name}"}
  self.class.new(*new_ops, **@options.merge(graph_name: graph_name, formulae: formulae))
end

#distinguished_vars ⇒ Array<RDF::Query::Variable]

Distinguished vars in this formula

Returns:



402
403
404
 
# File 'lib/rdf/n3/algebra/formula.rb', line 402

def distinguished_vars
  @distinguished ||= vars.vars.select(&:distinguished?)
end

#each(solutions: RDF::Query::Solutions(RDF::Query::Solution.new)) {|statement| ... } ⇒ Object

Yields each statement from this formula bound to previously determined solutions.

Yields:

  • (statement) —

    each matching statement

Yield Parameters:

Yield Returns:

  • (void) —

    ignored



236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
 
# File 'lib/rdf/n3/algebra/formula.rb', line 236

def each(solutions: RDF::Query::Solutions(RDF::Query::Solution.new), &block)
  log_debug("(formula each)") {SXP::Generator.string([self, solutions].to_sxp_bin)}

  # Yield statements by binding variables
  solutions.each do |solution|
    # Bind blank nodes to the solution when it doesn't contain a solution for an existential variable
    existential_vars.each do |var|
      solution[var.name] ||= RDF::Node.intern(var.name.to_s.sub(/^\$+/, ''))
    end

    log_debug("(formula apply)") {solution.to_sxp}
    # Yield each variable statement which is constant after applying solution
    log_depth do
      n3statements.each do |statement|
        terms = {}
        [:subject, :predicate, :object].each do |part|
          terms[part] = case o = statement.send(part)
          when RDF::Query::Variable
            if solution[o] && solution[o].formula?
              log_info("(formula from var form)") {solution[o].graph_name.to_sxp}
              form_statements(solution[o], solution: solution, &block)
            else
              solution[o] || o
            end
          when RDF::N3::List
            o.variable? ? o.evaluate(solution.bindings, formulae: formulae) : o
          when RDF::N3::Algebra::Formula
            # uses the graph_name of the formula, and yields statements from the formula. No solutions are passed in.
            log_info("(formula from form)") {o.graph_name.to_sxp}
            form_statements(o, solution: solution, &block)
          else
            o
          end
        end

        statement = RDF::Statement.from(terms)
        log_debug("(formula add)") {statement.to_sxp}

        block.call(statement)
      end

      # statements from sub-operands
      sub_ops.each do |op|
        log_debug("(formula sub_op)") {SXP::Generator.string [op, solution].to_sxp_bin}
        op.each(solutions: RDF::Query::Solutions(solution)) do |stmt|
          log_debug("(formula add from sub_op)") {stmt.to_sxp}
          block.call(stmt)
          # Add statements for any term which is a formula
          stmt.to_a.select(&:node?).map {|n| formulae[n]}.compact.each do |ef|
            log_debug("(formula from form)") {ef.graph_name.to_sxp}
            form_statements(ef, solution: solution, &block)              
          end
        end
      end
    end
  end
end

#each_pattern {|pattern| ... } ⇒ Object

Yields each pattern which is not a builtin

Yields:

  • (pattern) —

    each matching pattern

Yield Parameters:

Yield Returns:

  • (void) —

    ignored



301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
 
# File 'lib/rdf/n3/algebra/formula.rb', line 301

def each_pattern(&block)
  n3statements.each do |statement|
    terms = {}
    [:subject, :predicate, :object].each do |part|
      terms[part] = case o = statement.send(part)
      when RDF::N3::Algebra::Formula
        form_statements(o, solution: RDF::Query::Solution.new(), &block)
      else
        o
      end
    end

    pattern = RDF::Query::Pattern.from(terms)
    block.call(pattern)
  end
end

#evaluate(bindings, formulae:, **options) ⇒ RDF::N3::List

Evaluates the formula using the given variable ‘bindings` by cloning the formula replacing variables with their bindings recursively.

Parameters:

  • bindings (Hash{Symbol => RDF::Term}) —

    a query solution containing zero or more variable bindings

  • options (Hash{Symbol => Object}) —

    ({}) options passed from query

Returns:

See Also:

  • SPARQL::Algebra::Expression.evaluate


200
201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/rdf/n3/algebra/formula.rb', line 200

def evaluate(bindings, formulae:, **options)
  return self if bindings.empty?
  this = dup
  # Maintain formula relationships
  formulae {|k, v| this.formulae[k] ||= v}

  # Replace operands with bound operands
  this.operands = operands.map do |op|
    op.evaluate(bindings, formulae: formulae, **options)
  end
  this
end

#execute(queryable, solutions: RDF::Query::Solutions(RDF::Query::Solution.new), **options) ⇒ RDF::Solutions

Yields solutions from patterns and other operands. Solutions are created by evaluating each pattern and other sub-operand against ‘queryable`.

When executing, blank nodes are turned into non-distinguished existential variables, noted with ‘$$`. These variables are removed from the returned solutions, as they can’t be bound outside of the formula.

Parameters:

  • queryable (RDF::Queryable) —

    the graph or repository to query

  • solutions (RDF::Query::Solutions) (defaults to: RDF::Query::Solutions(RDF::Query::Solution.new)) —

    initial solutions for chained queries (RDF::Query::Solutions(RDF::Query::Solution.new))

  • options (Hash{Symbol => Object}) —

    any additional keyword options

Returns:

  • (RDF::Solutions) —

    distinct solutions



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
# File 'lib/rdf/n3/algebra/formula.rb', line 121

def execute(queryable, solutions: RDF::Query::Solutions(RDF::Query::Solution.new), **options)
  log_info("formula #{graph_name}") {SXP::Generator.string operands.to_sxp_bin}
  log_debug("(formula bindings)") { SXP::Generator.string solutions.to_sxp_bin}

  @query ||= RDF::Query.new(patterns).optimize!
  log_info("(formula query)") { SXP::Generator.string(@query.to_sxp_bin)}

  solutions = if @query.empty?
    solutions
  else
    these_solutions = queryable.query(@query, solutions: solutions, **options)
    if these_solutions.empty?
      # Pattern doesn't match, so there can be no solutions
      log_debug("(formula query solutions)") { SXP::Generator.string([].to_sxp_bin)}
      RDF::Query::Solutions.new
    else
      these_solutions.map! do |solution|
        RDF::Query::Solution.new(solution.to_h.inject({}) do |memo, (name, value)|
          # Replace blank node bindings with lists and formula references with formula, where those blank nodes are associated with lists.
          value = formulae.fetch(value, value) if value.node?
          l = RDF::N3::List.try_list(value, queryable)
          value = l if l.constant?
          memo.merge(name => value)
        end)
      end
      log_debug("(formula query solutions)") { SXP::Generator.string(these_solutions.to_sxp_bin)}
      solutions.merge(these_solutions)
    end
  end

  return solutions if solutions.empty?

  # Reject solutions which include variables as values
  solutions.filter! {|s| s.enum_value.none?(&:variable?)}

  # Use our solutions for sub-ops
  # Join solutions from other operands
  #
  # * Order operands by those having inputs which are constant or bound.
  # * Run built-ins with indeterminant inputs (two-way) until any produces non-empty solutions, and then run remaining built-ins until exhasted or finished.
  # * Re-calculate inputs with bound inputs after each built-in is run.
  log_depth do
    # Iterate over sub_ops using evaluation heuristic
    ops = sub_ops.sort_by {|op| op.rank(solutions)}
    while !ops.empty?
      last_op = nil
      ops.each do |op|
        log_debug("(formula built-in)") {SXP::Generator.string op.to_sxp_bin}
        these_solutions = op.execute(queryable, solutions: solutions)
        # If there are no solutions, try the next one, until we either run out of operations, or we have solutions
        next if these_solutions.empty?
        last_op = op
        solutions = RDF::Query::Solutions(these_solutions)
        break
      end

      # If there is no last_op, there are no solutions.
      unless last_op
        solutions = RDF::Query::Solutions.new
        break
      end

      # Remove op from list, and re-order remaining ops.
      ops = (ops - [last_op]).sort_by {|op| op.rank(solutions)}
    end
  end
  log_info("(formula sub-op solutions)") {SXP::Generator.string solutions.to_sxp_bin}
  solutions
end

#existential_vars ⇒ Array<RDF::Query::Variable]

Existential vars in this formula

Returns:



395
396
397
 
# File 'lib/rdf/n3/algebra/formula.rb', line 395

def existential_vars
  @existentials ||= vars.select(&:existential?)
end

#formula? ⇒ Boolean

Returns ‘true` if `self` is a RDF::N3::Algebra::Formula.

Returns:

  • (Boolean) 


217
218
219
 
# File 'lib/rdf/n3/algebra/formula.rb', line 217

def formula?
  true
end

#graph_name ⇒ RDF::Resource Also known as: to_uri

Graph name associated with this formula

Returns:

  • (RDF::Resource) 


320
 
# File 'lib/rdf/n3/algebra/formula.rb', line 320

def graph_name; @options[:graph_name]; end

#graph_name=(name) ⇒ RDF::Resource

Assign a graph name to this formula

Parameters:

  • name (RDF::Resource)

Returns:

  • (RDF::Resource) 


330
331
332
333
 
# File 'lib/rdf/n3/algebra/formula.rb', line 330

def graph_name=(name)
  formulae[name] = self
  @options[:graph_name] = name
end

#hash ⇒ Object

The formula hash is the hash of it’s operands and graph_name.

See Also:

  • Value#hash


225
226
227
 
# File 'lib/rdf/n3/algebra/formula.rb', line 225

def hash
  ([graph_name] + operands).hash
end

#inspect ⇒ Object 



426
427
428
 
# File 'lib/rdf/n3/algebra/formula.rb', line 426

def inspect
  sprintf("#<%s:%s(%d)>", self.class.name, self.graph_name, self.operands.count)
end

#n3statements ⇒ Object

Statements memoizer, from the operands which are statements.

Statements may include embedded formulae.



339
340
341
342
343
344
345
346
 
# File 'lib/rdf/n3/algebra/formula.rb', line 339

def n3statements
  # BNodes in statements are existential variables.
  @n3statements ||= begin
    # Operations/Builtins are not statements.
    operands.
      select {|op| op.is_a?(RDF::Statement)}
  end
end

#patterns ⇒ Object

Patterns memoizer, from the operands which are statements and not builtins.

Expands statements containing formulae into their statements.



352
353
354
355
 
# File 'lib/rdf/n3/algebra/formula.rb', line 352

def patterns
  # BNodes in statements are existential variables.
  @patterns ||= enum_for(:each_pattern).to_a
end

#sub_ops ⇒ Object

Non-statement operands memoizer



359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
 
# File 'lib/rdf/n3/algebra/formula.rb', line 359

def sub_ops
  # operands that aren't statements, ordered by their graph_name
  @sub_ops ||= operands.reject {|op| op.is_a?(RDF::Statement)}.map do |op|
    # Substitute nodes for existential variables in operator operands
    op.operands.map! do |o|
      case o
      when RDF::N3::List
        # Substitute blank node members with existential variables, recusively.
        graph_name && o.has_nodes? ? o.to_ndvar(graph_name) : o
      when RDF::Node
        graph_name ? o.to_ndvar(graph_name) : o
      else
        o
      end
    end
    op
  end
end

#to_base ⇒ Object 



422
423
424
 
# File 'lib/rdf/n3/algebra/formula.rb', line 422

def to_base
  inspect
end

#to_s ⇒ Object 



413
414
415
 
# File 'lib/rdf/n3/algebra/formula.rb', line 413

def to_s
  to_sxp
end

#to_sxp_bin ⇒ Object 



417
418
419
420
 
# File 'lib/rdf/n3/algebra/formula.rb', line 417

def to_sxp_bin
  [:formula, graph_name].compact +
  operands.map(&:to_sxp_bin)
end

#undistinguished_vars ⇒ Array<RDF::Query::Variable]

Undistinguished vars in this formula

Returns:



409
410
411
 
# File 'lib/rdf/n3/algebra/formula.rb', line 409

def undistinguished_vars
  @undistinguished ||= vars.vars.reject(&:distinguished?)
end

#universal_vars ⇒ Array<RDF::Query::Variable]

Universal vars in this formula and sub-formulae

Returns:



388
389
390
 
# File 'lib/rdf/n3/algebra/formula.rb', line 388

def universal_vars
  @universals ||= vars.reject(&:existential?).uniq
end

#vars ⇒ Array<RDF::Query::Variable>

Return the variables contained within this formula

Returns:



381
382
383
 
# File 'lib/rdf/n3/algebra/formula.rb', line 381

def vars
  operands.vars.flatten.compact
end