Penyebab Nontermination pada Datalog API

Mengekspos mesin inferensi Datalog atau recursive graph query melalui API publik berisiko menimbulkan masalah nontermination. Query rekursif dapat terjebak dalam infinite loop atau alokasi memori tak terbatas akibat siklus data (cyclic graph), rekursi tanpa kondisi basis yang valid, atau interaksi antara rekursi dan negasi.

Datalog murni dengan evaluasi bottom-up (fixed-point iteration) menjamin terminasi pada domain terhingga (finite domains). Namun, nontermination kerap terjadi akibat tiga faktor utama:

  • Top-down evaluation (SLD-resolution): Engine yang mengevaluasi rule secara top-down tanpa memoization/tabling (mirip Prolog murni) akan loop tanpa akhir saat menelusuri edge graph berputar.
  • Unstratified Negation: Aturan rekursif yang memuat negasi langsung pada relasi yang saling bergantung memicu kontradiksi logis atau osilasi state.
  • Ukuran Graf Ekstrem: Evaluasi bottom-up tetap dapat memicu Denial of Service (DoS) via resource exhaustion jika intermediate result (delta set) membengkak tanpa kendali batas kedalaman traversal.

Stratified Negation untuk Mencegah Siklus Logika

Negasi dalam Datalog membutuhkan stratifikasi agar dependensi antar relasi terdefinisi jelas tanpa ambiguitas semantik. Rule tidak boleh bergantung pada negasi dari dirinya sendiri, baik secara langsung maupun transitif.

Definisikan graph dependensi predikat: node merepresentasikan predikat relasi, edge berarah merepresentasikan ketergantungan body ke head. Edge bertanda khusus (negative edge) menandai predikat yang dinegasi (not p(...)). Skema Datalog valid hanya jika tidak terdapat siklus yang memuat negative edge.

% CONTOH ILEGAL (Non-stratified - memicu paradox / osilasi)
reachable(X, Y) :- edge(X, Y).
reachable(X, Y) :- edge(X, Z), not reachable(Z, Y).

% CONTOH LEGAL (Stratified Negation)
% Strata 0: Evaluasi seluruh jalur transitif dasar
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

% Strata 1: Evaluasi negasi hanya pada strata di bawahnya yang telah fixed-point
unreachable(X, Y) :- node(X), node(Y), not path(X, Y).

Parsing engine harus memverifikasi strata predikat menggunakan Topological Sort pada Dependency Graph saat kompilasi query. Jika terdeteksi siklus dengan edge negasi, tolak query dengan kode status 422 Unprocessable Entity sebelum dieksekusi.

Deteksi Cyclic Dependency dan Tabling Engine

Untuk engine berbasis top-down (seperti Datalog engine dengan tabling atau resolution-based micro-engines), cyclic dependency pada data relasional harus ditangani via memoization atau path-tracking.

Alternatif implementasi bottom-up semi-naïve evaluation menjamin terminasi pada finite domain karena hanya memproses delta state baru: ΔR(i) = R(i) - R(i-1). Evaluasi berhenti saat ΔR == ∅ (fixed-point reached).

Jika menggunakan top-down traversal terdistribusi di memori API, sematkan visited set atau limit path tracker:

// Middleware traversal sederhana dengan cyclic check dan depth guard
type NodeID = string;

interface Edge {
  from: NodeID;
  to: NodeID;
}

function evaluateTransitiveClosure(
  start: NodeID,
  edges: Map<NodeID, NodeID[]>,
  maxDepth: number
): Set<NodeID> {
  const visited = new Set<NodeID>();
  const queue: [NodeID, number][] = [[start, 0]];

  while (queue.length > 0) {
    const [current, depth] = queue.shift()!;

    if (depth >= maxDepth) {
      throw new Error(`RecursionLimitExceeded: Kedalaman melebihi batas ${maxDepth}`);
    }

    const neighbors = edges.get(current) || [];
    for (const next of neighbors) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push([next, depth + 1]);
      }
    }
  }

  return visited;
}

Enforcement Query Timeout pada API Gateway

Mekanisme proteksi internal runtime Datalog tidak boleh menjadi satu-satunya pertahanan. Beban komputasi berlebih akibat input rekursif liar harus diputus secara deterministik oleh ingress layer untuk mencegah starvation pada thread pool worker.

  1. HTTP Context Cancellation: Pastikan engine mengecek status context.Context (Go) atau AbortSignal (Node.js) pada setiap iterasi loop fixed-point. Jika timeout tercapai, batalkan proses evaluasi dan rilis memori segera.
  2. Reverse Proxy / API Gateway Deadline: Tetapkan batas atas strict di Gateway (seperti Envoy atau NGINX) dengan response 504 Gateway Timeout.
# Konfigurasi timeout NGINX reverse-proxy untuk Datalog API endpoint
location /api/v1/query {
    proxy_pass http://datalog_backend;
    proxy_connect_timeout 2s;
    proxy_send_timeout 5s;
    proxy_read_timeout 5s;
    
    # Batasi ukuran payload query untuk mencegah injeksi rules berlebih
    client_max_body_size 64k;
}

Validasi Query Contract pada Request Boundary

Amankan API endpoint sebelum payload rule mencapai Datalog engine parser:

  • Stateless Rules Validation: Tolak rule dinamis dari client jika API hanya butuh parameterized query. Jangan izinkan client menyuntikkan arbitrary recursive rule ke engine kecuali dalam lingkungan isolated sandbox.
  • Recursion Depth Limit: Konfigurasikan engine parameter dengan batas fixed limit iterasi (misal: maksimum 256 iterasi fixed-point). Hentikan evaluasi dan kembalikan error jika limit tercapai sebelum convergence.
  • Memory Quota Allocation: Batasi intermediate relation table size. Alokasikan buffer maksimum per query (misal: 10 MB per tenant session) untuk menepis serangan DoS berbasis memory blowup.