summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorpukkamustard <pukkamustard@posteo.net>2020-09-28 12:47:48 +0200
committerpukkamustard <pukkamustard@posteo.net>2020-09-28 12:47:48 +0200
commitec38672da556d692c44b97cb2f6dcfc77c9c0906 (patch)
tree0862c87648dc7364d3b19e3281cc03167d818717
parentd1c7ff331e86e3ef7f87bd91124c640bc71dbef9 (diff)
(datalog): naive -> semi-naive evaluation
-rw-r--r--datalog.scm56
1 files changed, 44 insertions, 12 deletions
diff --git a/datalog.scm b/datalog.scm
index 2441ed7..85308ef 100644
--- a/datalog.scm
+++ b/datalog.scm
@@ -309,21 +309,53 @@
edb
clauses))
-;; Algebraic Naive Evaluation (Section 9.1.1 of Logic Programming and Databases)
+(define (init-differentials clauses)
+ (fold
+ (lambda (clause result)
+ (let ((head (clause-head clause)))
+ (vhash-cons
+ (atom-predicate head)
+ (set)
+ (vhash-delete (atom-predicate head) result))))
+ vlist-null
+ clauses))
+
+;; Semi-Naive Evaluation (Section 9.1.2 of Logic Programming and Databases)
(define* (datalog-eval clauses #:key (edb vlist-null))
"Evaluate a Datalog program"
(let ((relational-exprs (clauses->relational-expr (sort-clauses clauses))))
- (let loop ((context (edb->evaluation-context edb clauses)))
- (let ((context+changes?
- (vhash-fold (λ (predicate relational-expr context+changes?)
- (let* ((new-values (ra:evaluate (car context+changes?) relational-expr))
- (changes? (< (set-size (vhash-ref predicate (car context+changes?)))
- (set-size new-values))))
- (cons (vhash-cons predicate new-values (vhash-delete predicate (car context+changes?)))
- (or changes? (cdr context+changes?)))))
- (cons context #f)
+ (let loop ((context (edb->evaluation-context edb clauses))
+ (differentials (init-differentials clauses)))
+
+ (let ((context+differentials+changes?
+ (vhash-fold (λ (predicate relational-expr context+differentials+changes?)
+
+ (let* ((context (car context+differentials+changes?))
+ (differentials (cadr context+differentials+changes?))
+ (old-changes? (cddr context+differentials+changes?))
+
+ ;; Create a context that uses the last differential at predicate currently being evaluated
+ (context-with-differential
+ (vhash-cons predicate (vhash-ref predicate differentials #:default (set)) (vhash-delete predicate context)))
+
+ ;; evaluate the relational expression
+ (evaluated (ra:evaluate context-with-differential relational-expr))
+
+ (new-differential (set-difference evaluated (vhash-ref predicate context)))
+
+ (new-values (set-union (vhash-ref predicate context) new-differential))
+
+ (changes? (not (set-empty? new-differential))))
+
+
+ (cons (vhash-cons predicate new-values (vhash-delete predicate context))
+ (cons (vhash-cons predicate new-differential differentials) (or changes? old-changes?)))))
+
+ (cons context (cons differentials #f))
relational-exprs)))
- (if (cdr context+changes?)
- (loop (car context+changes?))
+
+ (if (cddr context+differentials+changes?)
+ (loop (car context+differentials+changes?)
+ (cadr context+differentials+changes?))
context)))))