Uncertain Knowledge: Probabilistic Datalog, Fuzzy SPARQL, and Soft SHACL

pg_ripple v0.87.0 introduces the Uncertain Knowledge Engine — a suite of features for reasoning with imprecise, probabilistic, or fuzzy data.

Overview

Real-world knowledge graphs contain data of varying reliability. A fact extracted from a scientific paper has a different confidence level than one scraped from social media. pg_ripple now lets you:

1. Annotate Datalog rules with probability weights (@weight) so that inferred facts carry a confidence score.
2. Query confidence with SPARQL using the pg:confidence() extension function.
3. Traverse graphs with a fuzzy similarity filter using pg:confPath().
4. Match strings fuzzily with pg:fuzzy_match() and pg:token_set_ratio().
5. Score SHACL validation results with per-shape severity weights.
6. Export Turtle with RDF* confidence annotations.

Probabilistic Datalog (@weight)

Add a @weight(0.8) annotation to any Datalog rule to declare that derived facts have at most 0.8 confidence. The engine propagates confidence using noisy-OR combination:

parent(X, Y) :- father(X, Y).           @weight(1.0)
parent(X, Y) :- mother(X, Y).           @weight(1.0)
ancestor(X, Z) :- parent(X, Z).         @weight(0.9)
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z). @weight(0.85)

Enable with:

SET pg_ripple.probabilistic_datalog = on;

Confidence scores are stored in _pg_ripple.confidence:

SELECT statement_id, confidence, model
FROM   _pg_ripple.confidence
LIMIT  10;

GUCs for probabilistic evaluation

pg:confidence() — SPARQL confidence lookup

PREFIX pg: <http://pg-ripple.org/functions/>

SELECT ?s ?p ?o ?conf WHERE {
  ?s ?p ?o .
  BIND(pg:confidence(?s, ?p, ?o) AS ?conf)
  FILTER(?conf > 0.7)
}

Returns the maximum confidence across all models for the triple (?s, ?p, ?o). Returns 1.0 when no confidence row exists.

Fuzzy SPARQL functions

These require CREATE EXTENSION IF NOT EXISTS pg_trgm;.

pg:fuzzy_match(a, b)

Returns the trigram similarity (similarity()) between two string literals.

PREFIX pg: <http://pg-ripple.org/functions/>

SELECT ?label WHERE {
  ?entity rdfs:label ?label .
  FILTER(pg:fuzzy_match(?label, "Alice Smith") > 0.6)
}

pg:token_set_ratio(a, b)

Returns word-set similarity (word_similarity()) — better for substring matches.

FILTER(pg:token_set_ratio(?label, "Smith") > 0.5)

pg:confPath(predicate, threshold) — confidence property path

SELECT ?x WHERE {
  <http://example.org/alice> <pg:conf_path/http://example.org/knows/0.8> ?x
}

Traverses the knows predicate with a minimum confidence threshold of 0.8.

GUC

Soft SHACL scoring

Instead of a pass/fail validation, pg_ripple can compute a weighted data-quality score for a graph:

SELECT pg_ripple.shacl_score('http://example.org/data');
-- Returns a float8 in [0.0, 1.0], where 1.0 = fully compliant

Annotate shapes with sh:severityWeight to control their contribution:

ex:MyShape a sh:NodeShape ;
    sh:targetClass ex:Person ;
    sh:property [ sh:path ex:name ; sh:minCount 1 ] ;
    sh:severityWeight "2.0"^^xsd:decimal .

Extension note (STD-05, v0.92.0): sh:severityWeight is a pg_ripple-specific extension to the W3C SHACL Core specification. It is not defined by https://www.w3.org/TR/shacl/. A community submission to the W3C SHACL Community Group is being considered; see GitHub discussion for progress. The annotation is stable for the pg_ripple 1.x API line.

Score history is logged to _pg_ripple.shacl_score_log:

SELECT pg_ripple.log_shacl_score('http://example.org/data');
SELECT * FROM _pg_ripple.shacl_score_log ORDER BY measured_at DESC;

Loading triples with confidence

SELECT pg_ripple.load_triples_with_confidence(
    '<http://example.org/alice> <http://example.org/knows> <http://example.org/bob> .',
    confidence => 0.85,
    format => 'ntriples'
);

Exporting with confidence annotations (RDF*)

SET pg_ripple.export_confidence = on;
SELECT pg_ripple.export_turtle_with_confidence('http://example.org/data');

Returns Turtle with << s p o >> pg:confidence "0.85"^^xsd:float . annotations.

PROV-O confidence propagation

Set pg_ripple.prov_confidence = on to enable automatic confidence propagation from pg:sourceTrust predicates — triples derived from low-trust sources inherit lower confidence.

HTTP API (pg_ripple_http)

Garbage collection

Orphaned confidence rows (whose statement_id no longer exists in any VP table) are purged:

1. Automatically during each HTAP merge cycle.
2. On demand: SELECT pg_ripple.vacuum_confidence();

Convergence Guarantees for Cyclic Probabilistic Rules (v0.90.0)

When pg_ripple.prob_datalog_cyclic = on, pg_ripple iterates the noisy-OR composition to fixpoint. The noisy-OR operator is monotone on [0, 1] (adding more evidence can only increase confidence, never decrease it), which guarantees that the semi-naive iteration sequence is non-decreasing and bounded above by 1.0. Therefore, fixpoint convergence is guaranteed for any finite probabilistic Datalog program with noisy-OR semantics.

This result follows directly from Theorem 2 in De Raedt, Kimmig & Toivonen (2007), ProbLog: A Probabilistic Prolog and its Application in Link Discovery.

Extension note (STD-03, v0.91.0): pg_ripple's noisy-OR confidence composition is a pg_ripple-specific extension implementing probabilistic Datalog semantics. It is not defined by the W3C RDF or SPARQL specifications. The mathematical foundation is:

De Raedt, L., Kimmig, A., & Toivonen, H. (2007). ProbLog: A probabilistic Prolog and its application in link discovery. Proceedings of IJCAI 2007, pp. 2468–2473. https://ijcai.org/proceedings/2007/2

Convergence speed depends on cycle depth and confidence values; programs with near-1.0 confidence in cycles may converge slowly. The prob_datalog_max_iterations GUC (default 100) and prob_datalog_convergence_delta GUC (default 1e-6) control termination.

-- Tune convergence for deep cyclic programs
SET pg_ripple.prob_datalog_max_iterations = 500;
SET pg_ripple.prob_datalog_convergence_delta = 1e-8;

Formal Guarantee

Let $c_i^{(k)}$ denote the confidence of fact $i$ after $k$ iterations. Under noisy-OR semantics:

$$c_i^{(k+1)} = 1 - \prod_{j \in \text{parents}(i)} (1 - w_{ij} \cdot c_j^{(k)})$$

Since noisy-OR is monotone and the sequence ${c_i^{(k)}}$ is non-decreasing and bounded above by 1.0, by the Knaster–Tarski fixed-point theorem the iteration converges to the least fixed point of the probability propagation operator.

Further reading

• Blog: Probabilistic Datalog — noisy-OR, confidence propagation, and soft reasoning in pg_ripple
• Blog: Uncertain Knowledge — practical patterns for probabilistic reasoning