Skip to main content

RDF Storage

The construction is described in the paper "Hypergraph Based Query Optimization", which we will use by translating the logic to OT circuits, starting with decryption into the circuit using the extended decryption process of the address content. We adopt their term definitions in this section, Query Planner, and Query Evaluator. their definitions provided here roughly verbatim for convenience:

Notation:
  1. RDF Graph – G = (V, E) where V = {v|v ∈ S ∪ O} and E = {e1, e2, ...}∃e = {u, v} where u, v ∈ V.
  2. Edge Labeling Function – le(S, O) = P.
  3. Node Labeling Function – lv(vt) = t where t ∈ (S ∪ O) and S = Subject(URI ∪ BLANKS), P = Predicate(URI), O = Object(URI ∪ BLANKS ∪ LIT).
  4. Hypergraph – H(G) = (V, E) where node V = {v1, ..., vn} and E = {e1, ..., en} where V = {v|v ∈ S ∪ O ∪ P} and each edge E is a non-empty set of V . ∀P, ∃e|(Si, Oi) ∈ H(G) where 1 ≤ i ≤ n.
  5. Overlapping Hyperedge – (hi(G) ⊑ hi+1(G)) where h1(G) = (S1, P1, O1) and h2(G) = (S2, P2, O2), (h1(G) ⊑ h2(G)) iff ∀s1 ∈ S1 ∈ h1(G)∃s2 ∈ S2 ∈ h2(G)∨∀o1 ∈ O1 ∈ h1(G)∃o2 ∈ O2 ∈ h2(G)∨∀p1 ∈ P1 ∈ h1(G)∃p2 ∈ P2 ∈ h2(G).
  6. Predicate-Based Index – I(G) = (V, E) where V = {v|v ∈ Pi ∈ hi ∧ δ} and E = (vi, vj) where vi, vj ∈ V and 1 ≤ i ≤ n − 1, 1 ≤ j ≤ n for δ ∈ V ∃e = (δ, v). δ is the root of the index.
  7. SPARQL Query – QR contains <Qq, Qs, Qp > where Qq is the query form and Qp is the match pattern if ?x ∈ var(Qq) then ?x ∈ var(Qp) and Qs contains constraints like FILTER, OPTIONAL.
  8. Query Graph – QG = (V, E), V ← {var ∈ Qpi} and E ← {P ∈ Qpi ∧ (var ∈ Qpi, var ∈ Qpi+1)} where 1 ≤ i ≤ n, n is the number of predicates, P is the predicate.
  9. Query Path – Qpath∃Qpath, δ → Pi ∈ I(G)|Pi. size = minsize ∧ (Pi → Pi+1) ∈ I(G) if ∃var ∈ Qpi == var ∈ Qpi+1.
  10. Data Insertion – Given QR and Qp then check ∃Pi ∈ Qp ∈ I(G), if true then check Pi ∈ H(G) ∨ create hi ∈ Pi ∧ update H(G) with hi. Check if ∃var ∈ Qp ∈ H(G), if true then overlap hi with var’s h ∨ update hi with var ∈ Qp.
  11. Data Deletion – Given QR and Qp then check ∃Pi ∈ Qp ∈ I(G) ∧ Pi ∈ var, if true then check |hi| == 0, if true then remove var ∈ Qp ∈ H(G) ∨ copy of Pi exists.

Given these definitions, their paper proposes algorithms to perform the whole of the queries for this database:

Create Hypergraph:
  1. Given an RDF graph G as triple (S, O, P).
  2. V ← ∅, E ← ∅, ei ← ∅
  3. ∀(S, O, P) ∈ G, V ← V ∪ V ∈ (S ∪ O ∪ P).
  4. ∀Pi|1 ≤ i ≤ n, 1 ≤ j ≤ n, ei ← {Pi, {Sj , Oj}}, E ← ei.
  5. H(G) = (V, E).
Create Predicate-Based Index:
  1. Given a hypergraph H(G).
  2. Sort hyperedges by size.
  3. ∀hi|1 ≤ i ≤ n − 1, if MIN(size(hi)) then I(G) = I(G) ∪ δ ↓ Pi, ∀j|i + 1 ≤ j ≤ n, if (hi(G) ⊑ hj(G)) ∧ (size(Pi) == size(Pj)) then I(G) = I(G) ∪ Pi ↔ Pj else I(G) = I(G) ∪ Pi → Pj.