summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorpukkamustard <pukkamustard@posteo.net>2020-09-04 07:45:58 +0200
committerpukkamustard <pukkamustard@posteo.net>2020-09-04 07:46:32 +0200
commit34ca11f116140409be7210ef7af4ff1c45698f29 (patch)
treeb12cb15a0f0ea99bec9e6b6cd4e124a09752c9f7
parent9fa92884d020ece6030056c9ecd46b65da4833fb (diff)
(schemantic graph vhash): a vhash index based in-memory graph
-rw-r--r--README.org16
-rw-r--r--hall.scm11
-rw-r--r--schemantic/graph/vhash.scm36
-rw-r--r--schemantic/graph/vhash/index.scm92
-rw-r--r--schemantic/iri.scm7
-rw-r--r--schemantic/literal.scm9
-rw-r--r--schemantic/rdf.scm65
-rw-r--r--tests/schemantic/graph/vhash.scm60
8 files changed, 287 insertions, 9 deletions
diff --git a/README.org b/README.org
index 7b991db..273c1ef 100644
--- a/README.org
+++ b/README.org
@@ -4,15 +4,31 @@
A [[https://www.gnu.org/software/guile/][Guile]] library for the Semantic Web. Implements the Resource Description Framework (RDF).
+* Caveats
+
+** No Blank Nodes
+
+Instead there is a ~<lvar>~ that can be used as a local existential variable. ~<lvar>~ can not be serialized.
+
+** GOOPS
+
Guile Schemantic uses GOOPS, the object oriented extension to Guile. This is an
experiment to improve developer ergonomics. For a Guile RDF library that does
not use GOOPS see the excellent [[https://framagit.org/tyreunom/guile-rdf][guile-rdf]].
+** Experimental
+
+Things will break...🧪💥
+
* Inspiration
** [[https://rdf-elixir.dev/][RDF.ex]]
An Elixir RDF library from which we take much inspiration.
+** [[http://rdf.js.org/data-model-spec/][RDF/JS: Data model specification]]
+
+An abstract specification of an RDF data model for interoperability between Javascript libraries. We use some ideas from the specification. In particular the fact that ~<iri>~, ~<literal>~ and ~<lvar>~ extend the ~<term>~ class.
+
** [[https://github.com/cordawyn/schemantic-web][Schemantic Web]]
A collection of tools related to the Semantic Web for Scheme48 (mostly portable). We stole the cool name from them...
diff --git a/hall.scm b/hall.scm
index ac03afa..03d9123 100644
--- a/hall.scm
+++ b/hall.scm
@@ -15,7 +15,12 @@
((scheme-file "schemantic")
(directory
"schemantic"
- ((scheme-file "iri")
+ ((directory
+ "graph"
+ ((directory "vhash" ((scheme-file "index")))
+ (scheme-file "vhash")))
+ (directory "rdf" ((scheme-file "lang-string")))
+ (scheme-file "iri")
(scheme-file "xsd")
(scheme-file "rdf")
(scheme-file "literal")
@@ -24,8 +29,8 @@
"tests"
((directory
"schemantic"
- ((scheme-file "iri")
- (log-file "iri")
+ ((directory "graph" ((scheme-file "vhash")))
+ (scheme-file "iri")
(scheme-file "literal")))))))
(programs ((directory "scripts" ())))
(documentation
diff --git a/schemantic/graph/vhash.scm b/schemantic/graph/vhash.scm
new file mode 100644
index 0000000..fa6550a
--- /dev/null
+++ b/schemantic/graph/vhash.scm
@@ -0,0 +1,36 @@
+; SPDX-FileCopyrightText: 2020 pukkamustard <pukkamustard@posteo.net>
+;
+; SPDX-License-Identifier: GPL-3.0-or-later
+
+(define-module (schemantic graph vhash)
+ #:use-module (oop goops)
+ #:use-module (oop goops describe)
+
+ #:use-module (schemantic rdf)
+ #:use-module (schemantic graph vhash index)
+
+ #:use-module (ice-9 vlist)
+ #:use-module (ice-9 match)
+
+ #:export (<vhash-graph>))
+
+(define-class <vhash-graph> (<graph>)
+ ;; NOTE more indices (ops and pso) could be added to increase performance of certain queries
+ (spo #:accessor spo))
+
+(define-method (initialize (g <vhash-graph>) initargs)
+ (set! (spo g) vlist-null))
+
+(define-method (graph-add (g <vhash-graph>) (t <triple>))
+ (let ((s (triple-subject t))
+ (p (triple-predicate t))
+ (o (triple-object t)))
+ ;; add to spo index
+ (set! (spo g) (index-add (spo g) (list s p o)))
+ ;; return graph to allow chaining of multiple adds
+ g))
+
+(define-method (graph-match (g <vhash-graph>) (s <term>) (p <term>) (o <term>))
+ (map (match-lambda ((s p o) (make-triple s p o))) ; transform result when querying the index to a triple
+ (index-match (spo g) (list s p o))))
+
diff --git a/schemantic/graph/vhash/index.scm b/schemantic/graph/vhash/index.scm
new file mode 100644
index 0000000..a43e2ee
--- /dev/null
+++ b/schemantic/graph/vhash/index.scm
@@ -0,0 +1,92 @@
+; SPDX-FileCopyrightText: 2020 pukkamustard <pukkamustard@posteo.net>
+;
+; SPDX-License-Identifier: GPL-3.0-or-later
+
+(define-module (schemantic graph vhash index)
+ #:use-module (srfi srfi-1)
+ #:use-module (ice-9 vlist)
+ #:use-module (ice-9 match)
+ #:use-module ((schemantic rdf) #:select (lvar?))
+ #:export (index-add
+ index-match
+ index->list))
+
+;; VHash based nested index.
+;; Useful for defining indices for graph like structures
+
+(define (vhash-ref index key default)
+ (if (vhash-assoc key index)
+ (cdr (vhash-assoc key index))
+ default))
+
+(define (index-add* index entries)
+ (fold
+ (lambda (entry index) (index-add index entry))
+ index
+ entries))
+
+(define (index-add index entry)
+ (match entry
+
+ (() index)
+
+ ((key)
+ (vhash-cons key #t
+ (vhash-delete key index)))
+
+ ((key . rest)
+ (vhash-cons key
+ (index-add
+ (vhash-ref index key vlist-null) rest)
+ (vhash-delete key index)))))
+
+(define (index-ref index key)
+ (match key
+ (() index)
+ ((key)
+ (vhash-ref index key vlist-null))
+ ((key . rest)
+ (index-ref
+ (vhash-ref index key vlist-null)
+ rest))))
+
+(define (index-match index key)
+ (match key
+ (() (index->list index))
+
+ ((k . rest)
+ (if (lvar? k)
+
+ ;; iterate over all keys in index, match and concat the result
+ (vhash-fold
+ (lambda (ki sub-index result)
+ (append (index-match index (cons ki rest)) result))
+ '()
+ index)
+
+ ;; k is concrete, match rest of key and add k to front of results
+ (map (lambda (r) (cons k r))
+ (index-match (vhash-ref index k vlist-null) rest))))))
+
+;; (index-match
+;; (index-add* vlist-null '((1 2) (1 3) (2 2)))
+;; `(,(lvar) 3))
+
+(define (index->list index)
+ (cond
+ ;; enumerate all elements in index
+ ((vlist? index) (vlist-fold
+ (lambda (el lst)
+ (match el
+ ((key . ()) (cons (list key) lst))
+
+ ((key . sub-index)
+ (apply append
+ (map (lambda (sub-values) (cons key sub-values))
+ (index->list sub-index))
+ (list lst)))))
+ '()
+ index))
+
+ ;; if index is not a vlist this indicates the end of a single path. Return '(()) so that path can be reconstructed.
+ (else '(()))))
diff --git a/schemantic/iri.scm b/schemantic/iri.scm
index c8580dd..7a9a3dd 100644
--- a/schemantic/iri.scm
+++ b/schemantic/iri.scm
@@ -11,13 +11,16 @@
#:use-module (ice-9 optargs)
#:use-module (ice-9 exceptions)
- #:export (<iri>
+ #:export (<term>
+ <iri>
make-iri
iri?
iri-value
define-namespace))
-(define-class <iri> ()
+(define-class <term> ())
+
+(define-class <iri> (<term>)
(value #:init-keyword #:value #:getter iri-value))
(define-method (equal? (x <iri>) (y <iri>))
diff --git a/schemantic/literal.scm b/schemantic/literal.scm
index cbac7fc..1733cdf 100644
--- a/schemantic/literal.scm
+++ b/schemantic/literal.scm
@@ -17,7 +17,7 @@
literal-datatype
literal-language))
-(define-class <literal> ()
+(define-class <literal> (<term>)
(value #:init-keyword #:value #:getter literal-value))
(define-method (write (self <literal>) port)
@@ -32,10 +32,15 @@
(define-generic literal-lexical)
(define-generic literal-canonical)
(define-generic literal-datatype)
-(define-generic literal-language)
+(define-generic literal-language)
(define-method (literal-language (l <literal>)) #f)
+(define-method (equal? (x <literal>) (y <literal>))
+ (and (equal? (literal-value x) (literal-value y))
+ (equal? (literal-datatype x) (literal-datatype y))
+ (equal? (literal-language x) (literal-language y))))
+
;; Generic literal
(define-class <generic-literal> (<literal>)
diff --git a/schemantic/rdf.scm b/schemantic/rdf.scm
index cee9fb6..f3a2e0d 100644
--- a/schemantic/rdf.scm
+++ b/schemantic/rdf.scm
@@ -15,9 +15,26 @@
triple?
triple-subject
triple-predicate
- triple-object)
+ triple-object
- #:re-export (<iri>
+ <lvar>
+ lvar
+ lvar?
+
+ <graph>
+ graph?
+ graph-add
+ graph-match
+
+ <description>
+ description?
+ description-subject
+
+ rdf-ref)
+
+ #:re-export (<term>
+
+ <iri>
make-iri
iri?
iri-value
@@ -40,6 +57,17 @@
(predicate #:init-keyword #:p #:getter triple-predicate)
(object #:init-keyword '#:o #:getter triple-object))
+(define-method (write (self <triple>) port)
+ (format port "<triple ~a ~a ~a>"
+ (triple-subject self)
+ (triple-predicate self)
+ (triple-object self)))
+
+(define-method (equal? (x <triple>) (y <triple>))
+ (and (equal? (triple-subject x) (triple-subject y))
+ (equal? (triple-object x) (triple-object y))
+ (equal? (triple-predicate x) (triple-predicate y))))
+
(define-method (initialize (t <triple>) initargs)
(next-method))
@@ -49,3 +77,36 @@
(define (triple? x)
(is-a? x <triple>))
+
+;; Variable
+
+(define-class <lvar> (<term>))
+
+(define (lvar)
+ (make <lvar>))
+
+(define (lvar? x)
+ (is-a? x <lvar>))
+
+;; Graph
+
+;; A graph is an arbirtary container of triples. It can be an in-memory structure or a connection to a database.
+
+(define-class <graph> ())
+
+(define (graph? x)
+ (is-a? x <graph>))
+
+(define-generic graph-add)
+(define-generic graph-match)
+
+(define-method (graph-match (g <graph>) (t <triple>))
+ (graph-match g (triple-subject t) (triple-predicate t) (triple-object t)))
+
+;; Description
+
+;; A description is a pointer to a subject in a graph. It is also a container of triples and thus also a graph.
+
+(define-class <description> (<graph>))
+
+(define-generic description-subject)
diff --git a/tests/schemantic/graph/vhash.scm b/tests/schemantic/graph/vhash.scm
new file mode 100644
index 0000000..110be14
--- /dev/null
+++ b/tests/schemantic/graph/vhash.scm
@@ -0,0 +1,60 @@
+; SPDX-FileCopyrightText: 2020 pukkamustard <pukkamustard@posteo.net>
+;
+; SPDX-License-Identifier: GPL-3.0-or-later
+
+(define-module (tests schemantic graph vhash)
+ #:use-module (oop goops)
+ #:use-module (schemantic rdf)
+ #:use-module (schemantic graph vhash)
+ #:use-module ((schemantic ns) #:select (rdf))
+
+ #:use-module (srfi srfi-64))
+
+(define-namespace ex "http://example.com/#")
+
+(test-begin "graph vhash")
+
+(define g (make <vhash-graph>))
+
+(test-assert "vhash-graph is a graph" (graph? g))
+
+
+;; add an initial triple
+(define t1
+ (make-triple (ex "foo") (rdf "type") (ex "something")))
+
+(graph-add g t1)
+
+(test-assert "can match single triple"
+ (equal? (list t1)
+ (graph-match g (lvar) (lvar) (lvar))))
+
+(test-assert "can match single triple by s"
+ (equal? (list t1)
+ (graph-match g (triple-subject t1) (lvar) (lvar))))
+
+(test-assert "can match single triple by p"
+ (equal? (list t1)
+ (graph-match g (lvar) (triple-predicate t1) (lvar))))
+
+(test-assert "can match single triple by o"
+ (equal? (list t1)
+ (graph-match g (lvar) (lvar) (triple-object t1))))
+
+(test-assert "no match"
+ (nil? (graph-match g (ex "not-in-graph") (lvar) (lvar))))
+
+;; add another triple
+(define t2
+ (make-triple (ex "foo") (ex "bar") (make-literal 42)))
+
+(graph-add g t2)
+
+(test-assert "can match second triple"
+ (equal? (list t2)
+ (graph-match g (ex "foo") (ex "bar") (lvar))))
+
+(test-assert "can match both triples"
+ (equal? 2 (length (graph-match g (lvar) (lvar) (lvar)))))
+
+(test-end "graph vhash")