rdf.scm
| 1 | ;;;; Copyright (C) 2020 Julien Lepiller <julien@lepiller.eu> |
| 2 | ;;;; |
| 3 | ;;;; This library is free software; you can redistribute it and/or |
| 4 | ;;;; modify it under the terms of the GNU Lesser General Public |
| 5 | ;;;; License as published by the Free Software Foundation; either |
| 6 | ;;;; version 3 of the License, or (at your option) any later version. |
| 7 | ;;;; |
| 8 | ;;;; This library is distributed in the hope that it will be useful, |
| 9 | ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 10 | ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 11 | ;;;; Lesser General Public License for more details. |
| 12 | ;;;; |
| 13 | ;;;; You should have received a copy of the GNU Lesser General Public |
| 14 | ;;;; License along with this library; if not, write to the Free Software |
| 15 | ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
| 16 | ;;;; |
| 17 | |
| 18 | (define-module (rdf entailment rdf) |
| 19 | #:use-module (ice-9 match) |
| 20 | #:use-module (rdf rdf) |
| 21 | #:use-module ((rdf entailment d) #:prefix d:) |
| 22 | #:use-module (rdf utils) |
| 23 | #:use-module (srfi srfi-1) |
| 24 | #:export (consistent-graph? |
| 25 | entails?)) |
| 26 | |
| 27 | (define (rdf-iri name) |
| 28 | (string-append "http://www.w3.org/1999/02/22-rdf-syntax-ns#" name)) |
| 29 | |
| 30 | (define (consistent-graph? graph vocabulary) |
| 31 | (define (compatible? types) |
| 32 | (match (filter rdf-datatype? types) |
| 33 | (() #t) |
| 34 | ((_) #t) |
| 35 | ((a b ...) |
| 36 | (and (null? (filter |
| 37 | (lambda (t) |
| 38 | (not ((rdf-vocabulary-compatible? vocabulary) a t))) |
| 39 | b)) |
| 40 | (compatible? b))))) |
| 41 | |
| 42 | (define (compatible-types? graph) |
| 43 | (let loop ((graph graph) (type-mappings '())) |
| 44 | (if (null? graph) |
| 45 | (null? |
| 46 | (filter |
| 47 | (lambda (t) |
| 48 | (not (compatible? (cdr t)))) |
| 49 | type-mappings)) |
| 50 | (let* ((t (car graph))) |
| 51 | (if (equal? (rdf-triple-predicate t) (rdf-iri "type")) |
| 52 | (loop |
| 53 | (cdr graph) |
| 54 | (alist-set type-mappings (rdf-triple-subject t) |
| 55 | (cons (rdf-triple-object t) |
| 56 | (or |
| 57 | (assoc-ref type-mappings |
| 58 | (rdf-triple-subject t)) |
| 59 | '())))) |
| 60 | (loop (cdr graph) type-mappings)))))) |
| 61 | |
| 62 | (and (d:consistent-graph? graph vocabulary) |
| 63 | (compatible-types? (augment (recognize graph vocabulary) vocabulary)))) |
| 64 | |
| 65 | ;; G entails E if E has an instance (where blank nodes are replaced by literals |
| 66 | ;; or IRIs) that is a subgraph of G. |
| 67 | ;; |
| 68 | ;; We re-use similar procedures to verifying isomorphism of graphs, but this time |
| 69 | ;; blank nodes can also map to literals and IRIs. |
| 70 | |
| 71 | ;; We follow appendix A and use a subgraph comparison (like the simple:entails? |
| 72 | ;; procedure) after augmenting the graph with additional true triples. |
| 73 | |
| 74 | (define rdf-axioms |
| 75 | (list |
| 76 | (make-rdf-triple (rdf-iri "type") (rdf-iri "type") (rdf-iri "Property")) |
| 77 | (make-rdf-triple (rdf-iri "subject") (rdf-iri "type") (rdf-iri "Property")) |
| 78 | (make-rdf-triple (rdf-iri "predicate") (rdf-iri "type") (rdf-iri "Property")) |
| 79 | (make-rdf-triple (rdf-iri "object") (rdf-iri "type") (rdf-iri "Property")) |
| 80 | (make-rdf-triple (rdf-iri "first") (rdf-iri "type") (rdf-iri "Property")) |
| 81 | (make-rdf-triple (rdf-iri "rest") (rdf-iri "type") (rdf-iri "Property")) |
| 82 | (make-rdf-triple (rdf-iri "value") (rdf-iri "type") (rdf-iri "Property")) |
| 83 | (make-rdf-triple (rdf-iri "nil") (rdf-iri "type") (rdf-iri "List")))) |
| 84 | |
| 85 | (define (rdf-axioms-container container) |
| 86 | (list |
| 87 | (make-rdf-triple |
| 88 | container (rdf-iri "type") (rdf-iri "Property")))) |
| 89 | |
| 90 | (define (rdf-container-property? p) |
| 91 | (define rdf-container-property-base (rdf-iri "_")) |
| 92 | (and (string? p) |
| 93 | (> (string-length p) (string-length rdf-container-property-base)) |
| 94 | (equal? (substring p 0 (string-length rdf-container-property-base)) |
| 95 | rdf-container-property-base) |
| 96 | (string->number |
| 97 | (substring p (string-length rdf-container-property-base))))) |
| 98 | |
| 99 | (define (rdf-container-properties g) |
| 100 | (let loop ((answer '()) (g g)) |
| 101 | (match g |
| 102 | (() (if (null? answer) (list (rdf-iri "_1")) answer)) |
| 103 | ((($ rdf-triple subject predicate object) g ...) |
| 104 | (let* ((answer (if (and (rdf-container-property? subject) |
| 105 | (not (member subject answer))) |
| 106 | (cons subject answer) |
| 107 | answer)) |
| 108 | (answer (if (and (rdf-container-property? predicate) |
| 109 | (not (member predicate answer))) |
| 110 | (cons predicate answer) |
| 111 | answer)) |
| 112 | (answer (if (and (rdf-container-property? object) |
| 113 | (not (member object answer))) |
| 114 | (cons object answer) |
| 115 | answer))) |
| 116 | (loop answer g)))))) |
| 117 | |
| 118 | (define (augment g vocabulary) |
| 119 | (let* ((g (append rdf-axioms g)) |
| 120 | (g (append |
| 121 | (append-map rdf-axioms-container (rdf-container-properties g)) |
| 122 | g))) |
| 123 | (let loop ((g (recognize g vocabulary))) |
| 124 | (let ((augment-set |
| 125 | (let loop2 ((g2 g) (augment-set '())) |
| 126 | (match g2 |
| 127 | (() augment-set) |
| 128 | ((($ rdf-triple subject predicate object) g2 ...) |
| 129 | (let ((type-triple |
| 130 | (if (and (rdf-literal? object) |
| 131 | (rdf-datatype? (rdf-literal-type object))) |
| 132 | (make-rdf-triple object (rdf-iri "type") |
| 133 | (rdf-literal-type object)) |
| 134 | #f)) |
| 135 | (property-triple |
| 136 | (make-rdf-triple predicate (rdf-iri "type") |
| 137 | (rdf-iri "Property")))) |
| 138 | (loop2 |
| 139 | g2 |
| 140 | (append |
| 141 | (if (or (not type-triple) (member type-triple g) |
| 142 | (member type-triple augment-set)) |
| 143 | '() |
| 144 | (list type-triple)) |
| 145 | (if (or (member property-triple g) |
| 146 | (member type-triple augment-set)) |
| 147 | '() |
| 148 | (list property-triple)) |
| 149 | augment-set)))))))) |
| 150 | (if (null? augment-set) |
| 151 | g |
| 152 | (loop (append (recognize augment-set vocabulary) g))))))) |
| 153 | |
| 154 | (define (entails? g e vocabulary) |
| 155 | "Return true if g entails e" |
| 156 | (let* ((g (recognize g vocabulary)) |
| 157 | (g (augment g vocabulary)) |
| 158 | (e (recognize e vocabulary))) |
| 159 | (or (not (consistent-graph? g vocabulary)) |
| 160 | (d:entails? g e vocabulary)))) |
| 161 |