====== std.graphdb ====== In-Memory-Graphdatenbank mit Labels, typisierten Properties, f64-Vektoren und drei Indizes (temporal, typ-basiert, Vektor-Ähnlichkeit). Persistenz über ein kompaktes Binärformat (''LYXGDB''). Enthält eine Graph-RAG-Funktion für KI-gestützte Kontextsuche (Vektorsuche + BFS-Traversal). Einsatzbereiche: Wissensgraphen, semantische Suche, Empfehlungssysteme, temporale Ereignisgraphen, KI-Kontext (RAG). → [[lyx_-_programmiersprache:units|Standard Library]] · [[lyx_-_programmiersprache:units:db|std.db]] · [[lyx_-_programmiersprache:units:hash|std.hash]] · [[lyx_-_programmiersprache:units:alloc|std.alloc]] · [[lyx_-_programmiersprache:units:ml|std.ml]] ---- ===== Architektur ===== std.graphdb.core IDs, Timestamps │ ┌────┴────┐ node edge Knoten + Kanten mit TLV-Properties └────┬────┘ mem In-Memory-Store + Adjazenzliste │ index TemporalIndex · TypeIndex · VectorIndex │ ┌────┴────┐ query file High-Level Query-API · Datei-Persistenz Jedes Sub-Modul wird separat importiert: import std.graphdb.core; import std.graphdb.node; import std.graphdb.edge; import std.graphdb.mem; import std.graphdb.index; import std.graphdb.file; import std.graphdb.query; ---- ===== 1. Core — IDs und Timestamps ===== import std.graphdb.core; ^ Signatur ^ Beschreibung ^ | ''GraphIDNew(): int64'' | Neue eindeutige ID (Zeit XOR LCG, immer > 0) | | ''GraphIDFromStr(s: pchar, slen: int64): int64'' | Deterministische ID aus String (FNV-1a-64, immer > 0) | | ''GraphNow(): int64'' | Unix-Millisekunden via ''CLOCK_REALTIME'' | ''GRAPH_ID_INVALID = 0'' — ungültige/leere ID. ''GraphIDFromStr'' erzeugt immer denselben Wert für denselben String — geeignet für stabile Knoten-IDs aus externen Bezeichnern. ---- ===== 2. Nodes ===== import std.graphdb.node; Ein Node ist ein ''alloc(GNODE_SIZE)'' Puffer (80 Bytes). Der Caller verwaltet das Speicherlayout und setzt die ID manuell: var n: int64 := alloc(GNODE_SIZE); GraphNodeInit(n); poke64(n + GNODE_OFF_ID, GraphIDNew()); // ID muss explizit gesetzt werden ==== Init / Free ==== ^ Signatur ^ Beschreibung ^ | ''GraphNodeInit(n: int64)'' | Initialisiert alle Felder; alloziert Label- und Prop-Puffer | | ''GraphNodeFree(n: int64)'' | Gibt Label-Puffer, Prop-Puffer und Vektor-Puffer frei | ==== Labels ==== Labels sind kurze Typbezeichner (z.B. ''Person'', ''Article''). Intern ''\\0''-getrennt in einem wachsenden Puffer. ^ Signatur ^ Beschreibung ^ | ''GraphNodeAddLabel(n: int64, label: pchar, llen: int64)'' | Label hinzufügen | | ''GraphNodeHasLabel(n: int64, label: pchar, llen: int64): int64'' | 1 wenn Label vorhanden, sonst 0 | ==== Properties — Set ==== Properties sind typisierte Schlüssel-Wert-Paare, intern als TLV-Stream kodiert. ^ Signatur ^ Typ ^ Beschreibung ^ | ''GraphNodeSetInt(n, key, klen, val: int64)'' | int64 | Ganzzahl-Property setzen | | ''GraphNodeSetF64(n, key, klen, bits: int64)'' | f64 | Float-Property setzen (bits = IEEE-754-Bitmuster) | | ''GraphNodeSetBool(n, key, klen, val: int64)'' | bool | Bool-Property setzen (0 oder 1) | | ''GraphNodeSetStr(n, key, klen, val: pchar, vlen: int64)'' | pchar | String-Property setzen | Für ''GraphNodeSetF64'' muss der f64-Wert als int64-Bitmuster übergeben werden: var bits: int64 := 3.14 as int64; // IEEE-754-Bits von 3.14 GraphNodeSetF64(n, "score"c, 5, bits); ==== Properties — Get ==== ^ Signatur ^ Rückgabe ^ Beschreibung ^ | ''GraphNodeGetInt(n, key, klen): int64'' | Wert oder 0 | Ganzzahl-Property lesen | | ''GraphNodeGetF64(n, key, klen): int64'' | Bitmuster oder 0 | Float-Property lesen (als int64-Bitmuster) | | ''GraphNodeGetBool(n, key, klen): int64'' | 0 oder 1 | Bool-Property lesen | | ''GraphNodeGetStr(n, key, klen, outLen: int64): pchar'' | Pointer oder nil | String-Property lesen; outLen = Pointer auf int64 für Länge (0 = ignorieren) | ''GraphNodeGetStr'' gibt einen direkten Pointer in den internen Prop-Puffer zurück — gültig bis zum nächsten ''GraphNodeSetStr''-Aufruf für denselben Node. ==== Vektor (Embedding) ==== ^ Signatur ^ Beschreibung ^ | ''GraphNodeSetVec(n: int64, dims: int64, data: int64)'' | f64-Embedding-Vektor setzen (kopiiert ''dims × 8'' Bytes aus ''data'') | | ''GraphNodeGetVecDim(n: int64, i: int64): f64'' | Einzelne Dimension lesen | ''data'' muss ein Puffer mit ''dims × 8'' Bytes (f64-Array) sein. Vorhandener Vektor wird ersetzt. ==== Struct-Layout (GNODE_SIZE = 80 Bytes) ==== ^ Offset ^ Konstante ^ Inhalt ^ | 0 | ''GNODE_OFF_ID'' | Node-ID (int64) | | 8 | ''GNODE_OFF_LABELSBUF'' | Pointer auf Label-Puffer | | 16 | ''GNODE_OFF_LABELSLEN'' | Belegter Bereich (Bytes) | | 24 | ''GNODE_OFF_LABELSCAP'' | Kapazität (Bytes) | | 32 | ''GNODE_OFF_LABELSCOUNT'' | Anzahl Labels | | 40 | ''GNODE_OFF_PROPSBUF'' | Pointer auf TLV-Prop-Puffer | | 48 | ''GNODE_OFF_PROPSLEN'' | Belegter Bereich (Bytes) | | 56 | ''GNODE_OFF_PROPSCAP'' | Kapazität (Bytes) | | 64 | ''GNODE_OFF_VECBUF'' | Pointer auf f64-Vektor (0 = kein Vektor) | | 72 | ''GNODE_OFF_VECDIMS'' | Vektor-Dimensionen | ---- ===== 3. Edges ===== import std.graphdb.edge; Eine Kante verbindet zwei Nodes per ID und hat einen Typ-String sowie TLV-Properties. var e: int64 := alloc(GEDGE_SIZE); GraphEdgeInit(e); poke64(e + GEDGE_OFF_ID, GraphIDNew()); poke64(e + GEDGE_OFF_SOURCE, srcNodeId); poke64(e + GEDGE_OFF_TARGET, tgtNodeId); poke64(e + GEDGE_OFF_CREATEDAT, GraphNow()); // Pflicht vor AddEdge! GraphEdgeSetType(e, "KNOWS"c, 5); ==== Init / Free ==== ^ Signatur ^ Beschreibung ^ | ''GraphEdgeInit(e: int64)'' | Initialisiert alle Felder; alloziert Prop-Puffer | | ''GraphEdgeFree(e: int64)'' | Gibt Typ-Puffer und Prop-Puffer frei | ==== Typ ==== ^ Signatur ^ Beschreibung ^ | ''GraphEdgeSetType(e: int64, etype: pchar, elen: int64)'' | Kanten-Typ setzen (z.B. ''KNOWS'', ''AUTHORED'') | | ''GraphEdgeTypeEq(e: int64, etype: pchar, elen: int64): int64'' | 1 wenn Typ übereinstimmt, sonst 0 | ==== Properties ==== Identische Signaturstruktur wie bei Nodes: ^ Signatur ^ Beschreibung ^ | ''GraphEdgeSetInt(e, key, klen, val)'' | Ganzzahl-Property | | ''GraphEdgeSetF64(e, key, klen, bits)'' | Float-Property (IEEE-754-Bitmuster) | | ''GraphEdgeSetBool(e, key, klen, val)'' | Bool-Property | | ''GraphEdgeSetStr(e, key, klen, val, vlen)'' | String-Property | | ''GraphEdgeGetInt(e, key, klen)'' | Ganzzahl-Property lesen | | ''GraphEdgeGetF64(e, key, klen)'' | Float-Property lesen | | ''GraphEdgeGetBool(e, key, klen)'' | Bool-Property lesen | | ''GraphEdgeGetStr(e, key, klen, outLen)'' | String-Property lesen | ==== Struct-Layout (GEDGE_SIZE = 72 Bytes) ==== ^ Offset ^ Konstante ^ Inhalt ^ | 0 | ''GEDGE_OFF_ID'' | Kanten-ID (int64) | | 8 | ''GEDGE_OFF_SOURCE'' | Source-Node-ID | | 16 | ''GEDGE_OFF_TARGET'' | Target-Node-ID | | 24 | ''GEDGE_OFF_ETYPEBUF'' | Pointer auf Typ-String | | 32 | ''GEDGE_OFF_ETYPELEN'' | Typ-String-Länge | | 40 | ''GEDGE_OFF_CREATEDAT'' | Erstellungszeitpunkt (Unix-ms) | | 48 | ''GEDGE_OFF_PROPSBUF'' | Pointer auf TLV-Prop-Puffer | | 56 | ''GEDGE_OFF_PROPSLEN'' | Belegter Bereich (Bytes) | | 64 | ''GEDGE_OFF_PROPSCAP'' | Kapazität (Bytes) | ---- ===== 4. In-Memory Store ===== import std.graphdb.mem; Verwaltet Nodes und Kanten in parallelen ID/Pointer-Arrays und einer Adjazenzliste (source-ID → edge-ID). var s: int64 := alloc(GMEM_SIZE); GraphMemStoreInit(s); ==== Init / Free ==== ^ Signatur ^ Beschreibung ^ | ''GraphMemStoreInit(s: int64)'' | Alloziert alle internen Arrays (Node-IDs, Kanten-IDs, Adjazenz) | | ''GraphMemStoreFree(s: int64)'' | Gibt alle internen Arrays frei (Nodes/Edges selbst müssen separat freigegeben werden) | ==== Hinzufügen ==== ^ Signatur ^ Rückgabe ^ Beschreibung ^ | ''GraphMemStoreAddNode(s, n): int64'' | 1 = OK, 0 = Fehler | Node in Store aufnehmen. Schlägt fehl wenn ID = 0 oder bereits vorhanden | | ''GraphMemStoreAddEdge(s, e): int64'' | 1 = OK, 0 = Fehler | Kante in Store aufnehmen. Erfordert: ID ≠ 0, ''createdAt'' ≠ 0, source + target im Store vorhanden | > ''createdAt'' muss vor ''GraphMemStoreAddEdge'' gesetzt sein — der Store prüft ''peek64(e + GEDGE_OFF_CREATEDAT) != 0''. ==== Lookup ==== ^ Signatur ^ Rückgabe ^ Beschreibung ^ | ''GraphMemStoreGetNode(s, id): int64'' | Node-Pointer oder 0 | Node per ID suchen | | ''GraphMemStoreGetEdge(s, id): int64'' | Edge-Pointer oder 0 | Kante per ID suchen | ==== Traversal ==== ^ Signatur ^ Rückgabe ^ Beschreibung ^ | ''GraphMemStoreOutEdges(s, nodeId, outBuf, maxOut): int64'' | Anzahl | Kanten-IDs ausgehend von ''nodeId'' → int64-Array in ''outBuf'' | | ''GraphMemStoreNeighbors(s, nodeId, outBuf, maxOut): int64'' | Anzahl | Target-Node-IDs über ausgehende Kanten → int64-Array in ''outBuf'' | ''outBuf'' muss ''maxOut × 8'' Bytes groß sein. Zurückgegeben wird die tatsächliche Anzahl gefundener Einträge. ==== Struct-Layout (GMEM_SIZE = 88 Bytes) ==== ^ Offset ^ Konstante ^ Inhalt ^ | 0/8 | ''GMEM_OFF_NODEIDS / NODEPTRS'' | Parallel-Arrays: Node-IDs + Node-Pointer | | 16/24 | ''GMEM_OFF_NODECOUNT / NODECAP'' | Anzahl + Kapazität | | 32/40 | ''GMEM_OFF_EDGEIDS / EDGEPTRS'' | Parallel-Arrays: Kanten-IDs + Kanten-Pointer | | 48/56 | ''GMEM_OFF_EDGECOUNT / EDGECAP'' | Anzahl + Kapazität | | 64/72/80 | ''GMEM_OFF_ADJBUF / ADJCOUNT / ADJCAP'' | Adjazenzliste: [sourceId:8][edgeId:8] pro Eintrag | ---- ===== 5. Indizes ===== import std.graphdb.index; Drei unabhängige Indizes, die nach dem Befüllen des Stores mit ''*Build'' aufgebaut werden. ==== TemporalIndex — Kanten nach Zeit ==== Sortierter Index über ''createdAt''-Timestamps. Ermöglicht Zeitfenster-Abfragen. ^ Signatur ^ Beschreibung ^ | ''GraphTemporalIndexInit(idx: int64)'' | Index initialisieren (GTIDX_SIZE = 24 Bytes) | | ''GraphTemporalIndexFree(idx: int64)'' | Index freigeben | | ''GraphTemporalIndexBuild(idx, store: int64)'' | Index aus Store aufbauen (nach AddEdge aufrufen) | | ''GraphTemporalIndexQuery(idx, tsFrom, tsTo, outBuf, maxOut): int64'' | Kanten-IDs im Zeitfenster → int64-Array | ==== TypeIndex — Kanten nach Typ ==== Hash-basierter Index über den Kanten-Typ-String. ^ Signatur ^ Beschreibung ^ | ''GraphTypeIndexInit(idx: int64)'' | Index initialisieren (GXIDX_SIZE = 24 Bytes) | | ''GraphTypeIndexFree(idx: int64)'' | Index freigeben | | ''GraphTypeIndexBuild(idx, store: int64)'' | Index aus Store aufbauen | | ''GraphTypeIndexQuery(idx, etype, elen, outBuf, maxOut): int64'' | Kanten-IDs dieses Typs → int64-Array | ==== VectorIndex — Knoten nach Ähnlichkeit ==== Cosinus-Ähnlichkeitssuche über Node-Embedding-Vektoren. Nur Nodes mit Vektor (''GraphNodeSetVec'') werden indiziert. ^ Signatur ^ Beschreibung ^ | ''GraphVectorIndexInit(idx: int64, dims: int64)'' | Index initialisieren (GVIDX_SIZE = 32 Bytes); ''dims'' = Vektor-Dimensionen | | ''GraphVectorIndexFree(idx: int64)'' | Index freigeben | | ''GraphVectorIndexBuild(idx, store: int64)'' | Index aus Store aufbauen (nur Nodes mit passender Vektor-Dimension) | | ''GraphVectorIndexSearch(idx, queryVec, topK, outNodeIds, outScores): int64'' | Top-k ähnlichste Nodes; ''outScores'' = Cosinus-Score × 1 000 000 (absteigend sortiert) | ''queryVec'' ist ein ''dims × 8'' Byte großer int64-Puffer mit den f64-Rohdaten des Query-Vektors (als int64-Bitmuster). ''outNodeIds'' und ''outScores'' müssen je ''topK × 8'' Bytes groß sein. ---- ===== 6. Datei-Persistenz ===== import std.graphdb.file; Binäres Dateiformat mit Magic ''LYXGDB\x01\x00''. Speichert alle Nodes und Kanten inklusive Labels, Properties und Vektoren. ^ Signatur ^ Rückgabe ^ Beschreibung ^ | ''GraphFileSave(store, path: pchar, plen, compress: int64): int64'' | 1 = OK, 0 = Fehler | Store in Datei serialisieren; ''compress'' derzeit ignoriert (Flags = 0) | | ''GraphFileLoad(store, path: pchar, plen: int64): int64'' | 1 = OK, 0 = Fehler | Datei in Store laden; schlägt fehl bei falscher Magic | **Dateiformat:** [Magic: 8B "LYXGDB\x01\x00"][nodeCount:8][edgeCount:8][flags:8] pro Node: [id:8][labelsLen:8][labelsCount:8][propsLen:8][vecDims:8] + Daten pro Edge: [id:8][source:8][target:8][edgeTypeLen:8][createdAt:8][propsLen:8] + Daten > ''GraphFileLoad'' ruft intern ''GraphMemStoreAddNode'' und ''GraphMemStoreAddEdge'' auf — der Store muss vorher mit ''GraphMemStoreInit'' initialisiert sein. ---- ===== 7. Query-API ===== import std.graphdb.query; High-Level Query-Kontext kombiniert Store + Indizes. Ein ''GraphQueryCtx'' (GQCTX_SIZE = 32 Bytes) verweist auf alle Komponenten. ==== Kontext ==== var ctx: int64 := alloc(GQCTX_SIZE); GraphQueryCtxInit(ctx, store); GraphQueryCtxSetTemporalIdx(ctx, tidx); // optional GraphQueryCtxSetTypeIdx(ctx, typeidx); // optional GraphQueryCtxSetVectorIdx(ctx, vidx); // optional ^ Signatur ^ Beschreibung ^ | ''GraphQueryCtxInit(ctx, store: int64)'' | Kontext initialisieren; alle Indizes auf 0 (deaktiviert) | | ''GraphQueryCtxSetTemporalIdx(ctx, tidx: int64)'' | TemporalIndex einbinden | | ''GraphQueryCtxSetTypeIdx(ctx, typeidx: int64)'' | TypeIndex einbinden | | ''GraphQueryCtxSetVectorIdx(ctx, vidx: int64)'' | VectorIndex einbinden | ==== Abfragen ==== ^ Signatur ^ Rückgabe ^ Beschreibung ^ | ''GraphQueryEdgesInWindow(ctx, tsFrom, tsTo, outBuf, maxOut): int64'' | Anzahl Kanten-IDs | Zeitfenster-Abfrage (benötigt TemporalIndex) | | ''GraphQueryEdgesByType(ctx, etype, elen, outBuf, maxOut): int64'' | Anzahl Kanten-IDs | Typ-Abfrage (benötigt TypeIndex) | | ''GraphQueryPattern(ctx, pat, outBuf, maxOut): int64'' | Anzahl Target-Node-IDs | Pattern-Match: source → etype → target (optional: Zeitfilter) | ==== Pattern-Abfrage ==== Um die 7-Argument-Grenze des Compilers zu umgehen, werden Pattern-Parameter in einem ''GQPAT_SIZE''-Struct (32 Bytes) übergeben: var pat: int64 := alloc(GQPAT_SIZE); GraphQueryPatternInit(pat, srcNodeId, "KNOWS"c, 5); GraphQueryPatternSetTs(pat, GraphNow() - 86400000); // nur Kanten der letzten 24h (optional) var out: int64 := alloc(100 * 8); var found: int64 := GraphQueryPattern(ctx, pat, out, 100); ==== Graph-RAG ==== Kombiniert Vektorsuche mit BFS-Traversal für KI-Kontext-Retrieval: // topK ähnlichste Knoten finden + depth Hops Umfeld einsammeln var out: int64 := alloc(maxOut * 8); var cnt: int64 := GraphGetContextForAI(ctx, queryVec, topK, depth, out, maxOut); ^ Signatur ^ Beschreibung ^ | ''GraphGetContextForAI(ctx, queryVec, topK, depth, outBuf, maxOut): int64'' | Vektor-Ähnlichkeitssuche (topK Seeds) + BFS bis ''depth'' Hops; gibt alle Node-IDs zurück; benötigt VectorIndex | Ablauf intern: - ''GraphVectorIndexSearch'' → topK semantisch ähnliche Start-Nodes - BFS: für jeden aktuellen Node → ''GraphMemStoreNeighbors'' → Nachbarn einsammeln - Wiederholt ''depth'' Mal; bereits besuchte Nodes werden nicht doppelt ausgegeben ---- ===== Vollständiges Beispiel ===== import std.graphdb.core; import std.graphdb.node; import std.graphdb.edge; import std.graphdb.mem; import std.graphdb.index; import std.graphdb.file; import std.graphdb.query; import std.alloc; fn main(): int64 { // Store anlegen var s: int64 := alloc(GMEM_SIZE); GraphMemStoreInit(s); // Nodes anlegen var n1: int64 := alloc(GNODE_SIZE); GraphNodeInit(n1); poke64(n1 + GNODE_OFF_ID, GraphIDFromStr("alice"c, 5)); GraphNodeAddLabel(n1, "Person"c, 6); GraphNodeSetStr(n1, "name"c, 4, "Alice"c, 5); GraphNodeSetInt(n1, "age"c, 3, 30); GraphMemStoreAddNode(s, n1); var n2: int64 := alloc(GNODE_SIZE); GraphNodeInit(n2); poke64(n2 + GNODE_OFF_ID, GraphIDFromStr("bob"c, 3)); GraphNodeAddLabel(n2, "Person"c, 6); GraphNodeSetStr(n2, "name"c, 4, "Bob"c, 3); GraphMemStoreAddNode(s, n2); // Kante anlegen var e: int64 := alloc(GEDGE_SIZE); GraphEdgeInit(e); poke64(e + GEDGE_OFF_ID, GraphIDNew()); poke64(e + GEDGE_OFF_SOURCE, peek64(n1 + GNODE_OFF_ID)); poke64(e + GEDGE_OFF_TARGET, peek64(n2 + GNODE_OFF_ID)); poke64(e + GEDGE_OFF_CREATEDAT, GraphNow()); GraphEdgeSetType(e, "KNOWS"c, 5); GraphEdgeSetInt(e, "since"c, 5, 2020); GraphMemStoreAddEdge(s, e); // TypeIndex aufbauen und abfragen var tidx: int64 := alloc(GXIDX_SIZE); GraphTypeIndexInit(tidx); GraphTypeIndexBuild(tidx, s); var out: int64 := alloc(64 * 8); var found: int64 := GraphTypeIndexQuery(tidx, "KNOWS"c, 5, out, 64); // found = 1 (eine KNOWS-Kante) // Traversal: Nachbarn von n1 var nb: int64 := alloc(64 * 8); var ncnt: int64 := GraphMemStoreNeighbors(s, peek64(n1 + GNODE_OFF_ID), nb, 64); // ncnt = 1 (Bob) // Persistenz GraphFileSave(s, "graph.lyxgdb"c, 12, 0); // Aufräumen GraphTypeIndexFree(tidx); free(tidx, GXIDX_SIZE); GraphNodeFree(n1); free(n1, GNODE_SIZE); GraphNodeFree(n2); free(n2, GNODE_SIZE); GraphEdgeFree(e); free(e, GEDGE_SIZE); free(nb, 64 * 8); free(out, 64 * 8); GraphMemStoreFree(s); free(s, GMEM_SIZE); return 0; } ---- ===== Hinweise ===== * **Speicherverwaltung**: Alle Structs sind rohe ''alloc''-Puffer — kein automatisches GC. ''GraphNodeFree''/''GraphEdgeFree'' geben die internen Puffer frei; der Struct-Puffer selbst muss mit ''free(ptr, GNODE_SIZE)'' etc. separat freigegeben werden. ''GraphMemStoreFree'' gibt nur die internen Arrays frei, nicht die Nodes/Kanten selbst. * **f64-Properties**: ''GraphNodeSetF64'' und ''GraphEdgeSetF64'' erwarten IEEE-754-Bitmuster als int64. Konvertierung: ''var bits: int64 := myFloat as int64;'' * **TLV-Properties**: Schlüssellänge ist auf 255 Bytes begrenzt (1 Byte im TLV-Header). Für längere Schlüssel ist ''GraphNodeSetStr'' mit einem Hash-Key zu bevorzugen. * **Indizes sind nicht live**: ''GraphTemporalIndexBuild'', ''GraphTypeIndexBuild'' und ''GraphVectorIndexBuild'' erzeugen einen Snapshot. Nach weiteren ''AddNode''/''AddEdge''-Aufrufen muss der Index neu aufgebaut werden. * **VectorIndex-Score**: ''GraphVectorIndexSearch'' gibt Cosinus-Ähnlichkeit × 1 000 000 als int64 zurück (absteigend sortiert). Score 1 000 000 = identische Vektoren. * **Edge-Voraussetzungen**: Source- und Target-Node müssen beim ''GraphMemStoreAddEdge'' bereits im Store sein. ''createdAt'' muss ≠ 0 sein. Letzte Aktualisierung: 2026-06-14