recursive_path_queries

Recursive Path Queries & Multi-Hop Reasoning

Status: MVP Complete (31. Oktober 2025)
Feature Set: Rekursive Pfadabfragen, Multi-Hop Traversal, Temporale Graph-Queries

---

Überblick

Das Themis Query-Engine-Modul unterstützt jetzt rekursive Pfadabfragen für Graph-Traversals mit variabler Tiefe und optionaler zeitlicher Filterung.

Hauptfunktionen

• Recursive Path Queries: Variable Tiefe ohne festes Limit (1..max_depth)
• Multi-Hop Traversal: Automatische Pfadfindung über mehrere Knoten
• Temporal Graph Support: Zeitabhängige Kanten mit valid_from/valid_to
• Shortest Path: Dijkstra-Algorithmus für kürzeste Pfade
• Breadth-First Search: Alle erreichbaren Knoten bis zu einer bestimmten Tiefe

---

API-Referenz

RecursivePathQuery Struktur

struct RecursivePathQuery {
    std::string start_node;              // Start-Knoten (erforderlich)
    std::string end_node;                // Ziel-Knoten (optional, leer = BFS)
    std::string edge_type;               // Kanten-Typ-Filter (reserviert)
    size_t max_depth = 5;                // Maximale Traversal-Tiefe
    std::optional<std::string> valid_from;  // Zeitfenster Start (ms)
    std::optional<std::string> valid_to;    // Zeitfenster Ende (ms)
};

QueryEngine Methode

std::pair<Status, std::vector<std::vector<std::string>>> 
executeRecursivePathQuery(const RecursivePathQuery& q) const;

Rückgabe:

• Status: OK oder Fehlermeldung
• vector<vector<string>>: Liste von Pfaden (jeder Pfad ist eine Sequenz von Knoten-IDs)

---

Verwendungsbeispiele

Beispiel 1: Kürzester Pfad (Single Target)

#include "query/query_engine.h"
#include "index/graph_index.h"

// Setup
RocksDBWrapper db;
db.open("data/mydb");
SecondaryIndexManager secIdx(db);
GraphIndexManager graphIdx(db);
QueryEngine engine(db, secIdx, graphIdx);

// Query: Finde kürzesten Pfad von A nach D
RecursivePathQuery q;
q.start_node = "A";
q.end_node = "D";
q.max_depth = 10;

auto [st, paths] = engine.executeRecursivePathQuery(q);
if (st.ok && !paths.empty()) {
    // paths[0] = ["A", "B", "C", "D"]
    for (const auto& node : paths[0]) {
        std::cout << node << " -> ";
    }
}

Beispiel 2: BFS - Alle erreichbaren Knoten

// Query: Finde alle Knoten erreichbar von A (max Tiefe 3)
RecursivePathQuery q;
q.start_node = "A";
// Kein end_node = BFS-Modus
q.max_depth = 3;

auto [st, paths] = engine.executeRecursivePathQuery(q);
if (st.ok) {
    std::cout << "Erreichbare Knoten: " << paths.size() << std::endl;
    for (const auto& path : paths) {
        std::cout << "  " << path.back() << std::endl; // Ziel-Knoten
    }
}

Beispiel 3: Temporale Pfadabfrage

// Query: Finde Pfad, der zur Zeit 1600ms gültig war
RecursivePathQuery q;
q.start_node = "A";
q.end_node = "C";
q.max_depth = 5;
q.valid_from = "1600";  // Zeitstempel in Millisekunden

auto [st, paths] = engine.executeRecursivePathQuery(q);
// Nur Kanten, die bei valid_from <= 1600 <= valid_to sind, werden traversiert

Beispiel 4: Zeitfenster-Query

// Query: Finde Pfad im Zeitfenster [1000, 2000]
RecursivePathQuery q;
q.start_node = "A";
q.end_node = "D";
q.max_depth = 10;
q.valid_from = "1000";
q.valid_to = "2000";

auto [st, paths] = engine.executeRecursivePathQuery(q);
// Verwendet Mittelpunkt des Zeitfensters (1500ms) als Query-Zeitstempel

---

Graphen-Schema

Knoten-Entity

BaseEntity node("nodes", "node_id");
node.set("name", "Node Name");
node.set("type", "Person");
// ... weitere Attribute
db.putEntity(node);

Kanten-Entity (Standardgraph)

BaseEntity edge("edges", "edge_id");
edge.set("_from", "node_a");  // Erforderlich
edge.set("_to", "node_b");    // Erforderlich
edge.set("_weight", 1.5);     // Optional für gewichtete Pfade
db.putEntity(edge);
graphIdx.addEdge(edge);

Kanten-Entity (Temporaler Graph)

BaseEntity edge("edges", "edge_id");
edge.set("_from", "node_a");
edge.set("_to", "node_b");
edge.set("valid_from", 1000);  // Millisekunden seit Epoch
edge.set("valid_to", 2000);    // Millisekunden seit Epoch
db.putEntity(edge);
graphIdx.addEdge(edge);

Zeitfenster-Semantik:

• valid_from = null → gültig seit Anbeginn der Zeit
• valid_to = null → gültig bis in alle Ewigkeit
• Query-Zeitstempel t muss in [valid_from, valid_to] liegen

---

Interne Algorithmen

Shortest Path (end_node angegeben)

Verwendet Dijkstra-Algorithmus:

• Zeit-Komplexität: O((V + E) log V)
• Gewichtete Graphen unterstützt (Feld _weight)
• Temporal variant: dijkstraAtTime() filtert Kanten nach Zeitstempel

BFS (kein end_node)

Verwendet Breadth-First Search:

• Zeit-Komplexität: O(V + E)
• Findet alle Knoten bis zu max_depth
• Temporal variant: bfsAtTime() filtert Kanten nach Zeitstempel

Temporal Filtering

TemporalFilter filter = TemporalFilter::at(timestamp_ms);

// Für jede Kante:
bool isValid = filter.isValid(edge.valid_from, edge.valid_to);

---

Performance-Charakteristiken

Operation	Time Complexity	Space Complexity	Notes
Shortest Path (Dijkstra)	O((V + E) log V)	O(V)	Mit Priority Queue
BFS Traversal	O(V + E)	O(V)	Breadth-First
Temporal Filter Check	O(1)	O(1)	Per Edge
Path Reconstruction	O(depth)	O(depth)	Linear in Tiefe

Skalierung:

• In-Memory Graph Topology: O(1) Nachbarschaftsabfragen
• RocksDB Fallback: O(log N) bei kalten Kanten
• Empfohlenes Limit: max_depth <= 10 für interaktive Queries

---

Tests

Unit-Tests (test_recursive_path_query.cpp)

• ✅ SimplePathQuery: Kürzester Pfad A → D in linearem Graph
• ✅ PathNotFound: Kein Pfad in Gegenrichtung (gerichteter Graph)
• ✅ BFSReachableNodes: BFS findet alle erreichbaren Knoten
• ✅ TemporalPathQuery_ValidTime: Pfad zur Zeit 1600ms
• ✅ TemporalPathQuery_InvalidTime: Kein Pfad zur Zeit 500ms
• ✅ MaxDepthLimit: Respektiert max_depth Grenze
• ✅ EmptyStartNode: Fehlerbehandlung für leeren Start
• ✅ NoGraphIndexManager: Fehlerbehandlung ohne Graph-Index

Test-Ausführung:

cd build
.\Release\themis_tests.exe --gtest_filter="RecursivePathQueryTest.*"

---

Einschränkungen & TODOs

MVP Scope (Aktuell)

• ✅ Single shortest path (Dijkstra)
• ✅ BFS für erreichbare Knoten
• ✅ Temporale Filterung (valid_from/valid_to)
• ✅ Max-Tiefe-Limit

Zukünftige Erweiterungen

• All Paths Enumeration: Nicht nur kürzester, sondern alle Pfade
• Path Constraints: Filter auf Kanten-Attributen (z.B. edge_type)
• Variable-Length Patterns: Cypher-Style [:KNOWS*1..5]
• Recursive CTEs: SQL-ähnliche WITH RECURSIVE Syntax
• Weighted Temporal Paths: Kombination von Zeitfenster und Gewichtung
• Bidirectional Search: Schnellere Pfadsuche für große Graphen
• Graph Projection: Virtuelle Subgraphen für spezielle Queries

---

AQL-Integration (Geplant)

Zukünftige AQL-Syntax

// Kürzester Pfad
FOR v, e, p IN 1..5 OUTBOUND 'nodes/A' GRAPH 'my_graph'
    FILTER p.vertices[*]._key == 'D'
    LIMIT 1
    RETURN p

// Temporale Pfadabfrage
FOR v, e, p IN 1..3 OUTBOUND 'nodes/A' GRAPH 'my_graph'
    FILTER e.valid_from <= @timestamp AND e.valid_to >= @timestamp
    FILTER p.vertices[-1]._key == 'D'
    RETURN p

// Alle erreichbaren Knoten
FOR v IN 1..3 OUTBOUND 'nodes/A' GRAPH 'my_graph'
    RETURN DISTINCT v

---

Siehe auch

• docs/architecture.md - System-Architektur-Übersicht
• include/index/graph_index.h - Graph-Index API
• include/index/temporal_graph.h - Temporal-Filter Design
• tests/test_graph_index.cpp - Graph-Index Unit-Tests
• tests/test_temporal_graph.cpp - Temporal-Graph Tests

---

Letzte Aktualisierung: 31. Oktober 2025
Version: 1.0.0 (MVP)
Status: ✅ Production Ready