Skip to content

aql_pattern_matching.md

Latest commit

 

History

History
244 lines (182 loc) · 5.84 KB

aql_pattern_matching.md

File metadata and controls

244 lines (182 loc) · 5.84 KB

🔎 AQL Pattern Matching - Implementation Guide

Category: 🔎 Advanced Queries
Version: v1.3.0
Status: 🚧 Design Complete
Datum: 22. Dezember 2025

📑 Inhaltsverzeichnis

📋 Übersicht

Design-Datum: 19. November 2025
Konzept: Pattern-Matching ohne neue Syntax

Philosophie: Cypher-ähnliche Pattern-Matching-Queries können vollständig mit existierender AQL-Syntax ausgedrückt werden durch:

  1. Verschachtelte FOR-Loops für Multi-Hop-Traversals
  2. FILTER auf Vertex/Edge-Properties
  3. TYPE keyword für Edge-Type-Matching

Vorteil: Keine Spezialsyntax, konsistent mit AQL-Prinzipien, wiederverwendet Graph-Infrastruktur.

Pattern-Matching-Beispiele

1. Einfaches Pattern: (a)-[:FOLLOWS]->(b)

Cypher-Style:

MATCH (a:Person)-[:FOLLOWS]->(b:Person)
WHERE a.name == "Alice"
RETURN b

AQL-Äquivalent:

FOR a IN persons
  FILTER a.name == "Alice"
  FOR e IN edges
    FILTER e._from == a._id AND e._type == "FOLLOWS"
    FOR b IN persons
      FILTER b._id == e._to
      RETURN b

Optimierte AQL (mit Graph-Traversal):

FOR b IN 1..1 OUTBOUND "persons/Alice" TYPE "FOLLOWS" GRAPH "social"
  RETURN b

2. Multi-Hop Pattern: (a)-[:FOLLOWS]->(b)-[:LIKES]->(c)

Cypher-Style:

MATCH (a:Person)-[:FOLLOWS]->(b:Person)-[:LIKES]->(c:Product)
WHERE a.name == "Alice" AND c.category == "Books"
RETURN b, c

AQL-Äquivalent (verschachtelte Traversals):

FOR b IN 1..1 OUTBOUND "persons/Alice" TYPE "FOLLOWS" GRAPH "social"
  FOR c IN 1..1 OUTBOUND b._id TYPE "LIKES" GRAPH "social"
    FILTER c.category == "Books"
    RETURN {person: b, product: c}

3. Variable Pfadlänge: (a)-[:KNOWS*1..3]->(b)

Cypher-Style:

MATCH (a:Person)-[:KNOWS*1..3]->(b:Person)
WHERE a.name == "Alice"
RETURN b

AQL:

FOR b IN 1..3 OUTBOUND "persons/Alice" TYPE "KNOWS" GRAPH "social"
  RETURN DISTINCT b

📚 Siehe auch

📝 Changelog

v1.3.0 - 22. Dezember 2025

  • ✅ Template-Update: Standardisierung auf v1.3.0 Dokumentationsformat
  • ✅ Struktur: 8-Abschnitte-Format mit Emojis und TOC

v1.0 - 19. November 2025

  • Design Complete: Pattern-Matching ohne neue Syntax
  • Cypher-Äquivalente mit existierender AQL-Syntax
MATCH (a:Person)-[r1:FOLLOWS]->(b:Person)-[r2:LIKES]->(c:Product)
WHERE a.name == "Alice" 
  AND r1.since > "2024-01-01"
  AND b.age > 25
  AND c.price < 100
RETURN b, c

AQL:

FOR v1, e1, p1 IN 1..1 OUTBOUND "persons/Alice" TYPE "FOLLOWS" GRAPH "social"
  FILTER e1.since > "2024-01-01"
  FILTER v1.age > 25
  FOR v2, e2, p2 IN 1..1 OUTBOUND v1._id TYPE "LIKES" GRAPH "social"
    FILTER v2.price < 100
    RETURN {person: v1, product: v2}

Implementierte Features (bereits vorhanden)

✅ Graph Traversal Syntax

  • FOR v, e, p IN min..max DIRECTION startVertex TYPE edgeType GRAPH graphName
  • Richtungen: OUTBOUND, INBOUND, ANY
  • Variable Tiefe: 1..3, 2..5, etc.

✅ Edge-Type-Filtering

  • TYPE "FOLLOWS" - filtert Kanten nach Typ während Traversal
  • Bereits im Parser: src/query/aql_parser.cpp:502

✅ Pfad-Variablen

  • v - Current Vertex
  • e - Current Edge (letzte Kante zum Vertex)
  • p - Full Path (vertices + edges)

✅ Property Filtering

  • FILTER v.age > 25 - Vertex-Properties
  • FILTER e.weight > 10 - Edge-Properties
  • FILTER p.vertices[0].name == "Alice" - Pfad-Zugriff

Fehlende Features (TODO)

⏳ PATH-Prädikate für Constraints

Ziel: Pfad-Constraints wie in Cypher:

FOR v, e, p IN 1..5 OUTBOUND 'user1' GRAPH 'social'
  FILTER ALL(edge IN p.edges WHERE edge.active == true)
  FILTER NONE(vertex IN p.vertices WHERE vertex.blocked == true)
  RETURN v

Implementation:

  • Neue Expression-Typen: PathPredicateExpr
  • Evaluierung in let_evaluator.cpp via Pfad-Iteration
  • Aufwand: 1 Tag

⏳ Shortest-Path-Syntax

Aktuell (umständlich):

FOR v, e, p IN 1..10 OUTBOUND 'A' GRAPH 'network'
  FILTER v._id == 'B'
  SORT LENGTH(p.edges) ASC
  LIMIT 1
  RETURN p

Geplant (Syntaxzucker):

FOR p IN SHORTEST_PATH 'A' TO 'B' GRAPH 'network'
  RETURN p

Implementation:

  • Parser-Erweiterung für SHORTEST_PATH keyword
  • Translator nutzt graphMgr_->dijkstra()
  • Aufwand: 0.5 Tage

Performance-Optimierungen

Edge-Type-Index

Problem: TYPE "FOLLOWS" erfordert derzeit Edge-Loading während Traversal.

Lösung: Separate Adjacency-Listen pro Edge-Type:

graph:out:<edgeType>:<fromPk>:<edgeId> -> <toPk>

Benefit: 10x schnelleres Pattern-Matching für type-spezifische Queries.

Aufwand: 0.5 Tage

Zusammenfassung

Status: Pattern-Matching ist bereits möglich mit existierender AQL-Syntax!

Kern-Features:

  • ✅ Multi-Hop Traversals (verschachtelte FOR)
  • ✅ Edge-Type-Filtering (TYPE keyword)
  • ✅ Property-Constraints (FILTER)
  • ✅ Variable Pfadlängen (min..max)

Empfohlene Erweiterungen:

  1. PATH-Prädikate (ALL/ANY/NONE) - 1 Tag
  2. SHORTEST_PATH Syntaxzucker - 0.5 Tage
  3. Edge-Type-Index - 0.5 Tage

Total: 2 Tage für vollständiges Cypher-Parity Pattern-Matching

Nächster Schritt: Dokumentation + Beispiele statt neue Syntax!