themis docs features features_path_constraints

Graph Traversal Path Constraints

Version: 1.0 Draft
Datum: 28. Oktober 2025
Status: Konzept – Noch nicht implementiert

---

Motivation

Aktuell werden FILTER-Ausdrücke in Traversals nur am letzten Level vor dem Enqueue angewendet (konservatives Pruning). Dies ist sicher, aber lässt Optimierungspotenzial auf Zwischenebenen ungenutzt.

Pfad-Constraints ermöglichen aggressiveres Pruning auf allen Tiefen, indem Prädikate entlang des gesamten Pfads gelten.

---

Problem: Naive Anwendung ist unsicher

Beispiel: Unsicheres Edge-Pruning

Query:

FOR v IN 1..3 OUTBOUND 'user1' GRAPH 'social'
  FILTER e.type == 'follows'
  RETURN v

Naive (falsche) Interpretation:

• "Schneide alle Kanten ab, bei denen e.type != 'follows'"
• Problem: Bei depth=1 ist e die Kante von user1 → v1, aber bei depth=2 ist e die Kante zum aktuellen Knoten (v2), nicht die gesamte Pfadhistorie.

Ergebnis: Zu viele Pfade abgeschnitten, die über alternative Routen erreichbar wären.

---

Lösung: Pfad-Constraints explizit definieren

1. Constraint-Typen

1.1 Last-Edge Constraint (bereits implementiert)

Semantik: FILTER gilt nur für die eingehende Kante zur aktuellen Zeile (depth).

Syntax:

FILTER e.type == 'follows'  -- nur am letzten Level sicher

Anwendung:

• Am letzten Level vor Enqueue prüfen (✅ implementiert)
• Auf Zwischenebenen: nicht prunen (würde Pfade abschneiden)

---

1.2 All-Edges Constraint (Pfad-weites Prädikat)

Semantik: FILTER gilt für alle Kanten entlang des Pfads von Start bis aktueller Zeile.

Syntax (zukünftig):

FILTER PATH.ALL(e, e.type == 'follows')

Bedeutung:

• Prüfe bei jedem Expand: Ist die neue Kante ein follows?
• Wenn nein: Pfad ist ungültig → nicht enqueuen
• Sicher auf allen Tiefen!

Implementierung:

• Beim Enqueue: Prüfe a.edgeId gegen Constraint
• Tracking: Optional Pfad-Historie (Liste der edgeIds) mitführen, falls Constraints auf "vorherige Kante" prüfen

---

1.3 Any-Edge Constraint

Semantik: Mindestens eine Kante entlang des Pfads erfüllt Prädikat.

Syntax (zukünftig):

FILTER PATH.ANY(e, e.weight > 10)

Implementierung:

• Pfad-State: Boolean Flag hasSeenHeavyEdge
• Beim Enqueue: Update Flag
• Bei Result-Zeile: Prüfe Flag

---

1.4 No-Vertex Constraint (Blockierte Knoten)

Semantik: Kein Vertex entlang des Pfads darf Prädikat verletzen.

Syntax (zukünftig):

FILTER PATH.NONE(v, v.blocked == true)

Implementierung:

• Beim Enqueue: Prüfe neuen Vertex nb gegen Constraint
• Wenn nb.blocked == true: Nicht enqueuen
• Sicher auf allen Tiefen!

---

2. Sichere Pruning-Regeln

Constraint-Typ	Anwendungstiefe	Implementierung
Last-Edge (e.field OP value)	Nur letztes Level	✅ Implementiert (evalSingleE)
Last-Vertex (v.field OP value)	Nur letztes Level	✅ Implementiert (evalSingleV)
PATH.ALL(e, ...)	Alle Tiefen	🔜 Geplant (Expand-Zeit-Check)
PATH.NONE(v, ...)	Alle Tiefen	🔜 Geplant (Expand-Zeit-Check)
PATH.ANY(e, ...)	Alle Tiefen (State)	🔜 Geplant (Flag-basiert)

---

3. AST-Erweiterungen (Parser)

3.1 Neue Expression-Typen

struct PathConstraintExpr : Expression {
    enum class Type { All, Any, None };
    Type type;
    char varName;  // 'e' oder 'v'
    std::unique_ptr<Expression> predicate;
};

Parser-Syntax:

PATH.ALL(e, e.type == 'follows')
PATH.NONE(v, v.blocked == true)
PATH.ANY(e, e.weight > 10)

---

3.2 AST-Classifier (Filter-Analyse)

struct FilterClassification {
    std::vector<Expression*> lastEdgeOnly;
    std::vector<Expression*> lastVertexOnly;
    std::vector<Expression*> pathAllEdge;
    std::vector<Expression*> pathNoneVertex;
    std::vector<Expression*> pathAnyEdge;
    std::vector<Expression*> mixed;  // AND/OR kombiniert, keine einfache Klassifikation
};

FilterClassification classifyFilters(const std::vector<std::unique_ptr<FilterClause>>& filters);

---

4. BFS-Anpassungen

4.1 Expand-Zeit-Checks (PATH.ALL/NONE)

auto enqueueOut = [&](const std::vector<AdjacencyInfo>& adj) {
    for (const auto& a : adj) {
        // PATH.ALL(e, e.type == 'follows')
        for (const auto& pathAllE : pathAllEdgeConstraints) {
            if (!evalEdgeConstraint(a.edgeId, pathAllE)) {
                prunedAllDepths++;
                continue;  // sicher auf allen Tiefen!
            }
        }
        
        // PATH.NONE(v, v.blocked == true)
        for (const auto& pathNoneV : pathNoneVertexConstraints) {
            if (evalVertexConstraint(a.targetPk, pathNoneV)) {
                prunedAllDepths++;
                continue;  // blockierter Vertex → skip
            }
        }
        
        // Konservative Prüfungen (nur letztes Level)
        if (depth + 1 == t.maxDepth) {
            // ... (wie bisher)
        }
        
        if (visited.insert(a.targetPk).second) {
            parent[a.targetPk] = {node, a.edgeId};
            qnodes.push({a.targetPk, depth + 1});
            enqueuedPerDepth[depth + 1]++;
        }
    }
};

---

4.2 State-basierte Constraints (PATH.ANY)

struct PathState {
    bool hasSeenHeavyEdge = false;
    // weitere Flags je Constraint
};

std::unordered_map<std::string, PathState> pathStates;

// Beim Enqueue:
PathState newState = pathStates[node];
if (checkEdgeWeight(a.edgeId) > 10) newState.hasSeenHeavyEdge = true;
pathStates[a.targetPk] = newState;

// Bei Result-Zeile:
if (pathAnyEdgeConstraints.hasHeavyEdge && !pathStates[node].hasSeenHeavyEdge) {
    pass = false;  // PATH.ANY nicht erfüllt
}

---

5. Performance-Implikationen

Vorteile

• Frontier-Reduktion: Aggressives Pruning auf allen Tiefen
• Frühzeitiger Abbruch: Ungültige Pfade werden sofort verworfen
• Weniger Entity-Loads: Nur validierte Pfade landen in Result-Set

Kosten

• Expand-Zeit-Overhead: Jede Kante wird gegen PATH.ALL/NONE geprüft
• Memory: PathState für PATH.ANY (HashMap, kleine Keys)

Faustregel:

• Nutzen > Kosten, wenn Constraints selektiv sind (z. B. nur 10% der Kanten sind follows)

---

6. Implementierungs-Roadmap

1. Phase 1: Parser-Erweiterung (PATH.ALL/NONE/ANY Syntax)
2. Phase 2: AST-Classifier (Filter-Typen erkennen)
3. Phase 3: BFS Expand-Zeit-Checks (PATH.ALL/NONE)
4. Phase 4: State-Tracking (PATH.ANY)
5. Phase 5: Metriken (pruned_all_depths, path_state_size)
6. Phase 6: Tests & Benchmarks (Vergleich mit/ohne Constraints)

---

7. Beispiel-Queries

Nur follows-Kanten erlauben

FOR v IN 1..3 OUTBOUND 'user1' GRAPH 'social'
  FILTER PATH.ALL(e, e.type == 'follows')
  RETURN v

Effekt: BFS expandiert nur über follows-Kanten, alle anderen werden auf allen Tiefen gedroppt.

---

Keine blockierten Vertices im Pfad

FOR v IN 1..5 OUTBOUND 'user1' GRAPH 'social'
  FILTER PATH.NONE(v, v.blocked == true)
  RETURN v

Effekt: Pfade, die einen blockierten Vertex passieren, werden sofort verworfen.

---

Mindestens eine starke Beziehung

FOR v IN 1..4 OUTBOUND 'user1' GRAPH 'social'
  FILTER PATH.ANY(e, e.weight > 10)
  RETURN v

Effekt: Nur Pfade mit mindestens einer starken Kante (weight > 10) landen im Result.

---

Zusammenfassung

Aktuelle Implementierung	Pfad-Constraints (geplant)
Pruning nur am letzten Level	Pruning auf allen Tiefen
Unsicher für Zwischenebenen	Sichere Semantik durch PATH.ALL/NONE
Einfach (kein State)	State-Tracking für PATH.ANY
Konservativ (viele False Positives)	Aggressiv (nur valide Pfade expandiert)

Empfehlung:

• Phase 1-3 implementieren (PATH.ALL/NONE) für sofortigen Nutzen
• Phase 4 (PATH.ANY) optional, falls Use-Cases existieren
• Metriken sammeln: pruned_all_depths vs. pruned_last_level Vergleich

---

Siehe auch:

• AQL EXPLAIN & PROFILE
• BFS Pruning (aktuell)