Chapter 13: Graph Modeling

In many databases, "graph" is a specialized mode or a separate engine. In Datalevin, graph-shaped data is part of the normal fact model. Every :db.type/ref you define is a directed edge between two nodes (entities).

Graph cost follows fan-out

Because Datalevin maintains EAV and AVE indexes, both forward and reverse navigation have indexed access paths. Actual cost still depends on fan-out, selectivity, and result size: an indexed edge that reaches millions of neighbors still returns millions of candidates.

This chapter shows how to use Datalevin for graph-shaped data, focusing on navigation, recursive patterns, and modeling complex relationships.

1. Entities as Nodes, Refs as Edges

Figure 13.1 depicts a graph model as a network of interconnected entities.

Nodes: Entities with their properties (attributes).
Edges: Reference attributes (:db.type/ref) that point from one entity to another.

Refs as directed edges: alice and cara follow bob, and bob follows dave, via :user/follows. Forward navigation starts from a known entity position and follows the reference to the value position using the EAV index; reverse navigation starts from a known value position and finds matching entities using the AVE index

Datalevin allows you to traverse relationships in both directions without any additional indexing. The query planner chooses the right index for navigation:

Forward: Starting from the known entity position and following a reference attribute to the value position using the EAV index.
- Pattern: [?bound-eid :user/follows ?unknown-eid]
Reverse: Starting from a known value position and finding entities whose reference attribute has that value using the AVE index.
- Pattern: [?unknown-eid :user/follows ?bound-eid]

This works well because most queries in a well-designed data model know the attribute they are traversing.

2. Modeling Complex Edges (Join Entities)

In a simple graph, an edge can be a direct reference such as :user/follows. When the edge itself has facts, promote the edge to an entity. Property-graph literature models this as an edge with properties. In Datalevin, model it as a join entity: ordinary entities connected by ordinary ref attributes.

Reifying an edge into a join entity: a simple user A :user/follows user B edge becomes a Follow entity that references user A as :follow/follower and user B as :follow/following, and carries properties such as created-at and strength on the relationship itself

In Figure 13.2, the direct edge A -> B becomes a Follow entity with two refs, :follow/follower and :follow/following, plus facts such as :follow/created-at or :follow/strength. This gives you property-graph-style modeling [1] while keeping Datalevin's normalized fact representation [2]. Chapter 12 shows the same move in ER examples such as memberships, line items, and enrollments.

3. Graph Traversal Patterns

Graph queries range from fixed-depth joins to recursive reachability, branching path shapes, and exclusions. Datalevin uses ordinary Datalog joins for fixed-depth traversals, recursive rules for paths of arbitrary length, and or-join or not-join when graph shapes branch or exclude one another.

Fixed-depth traversals are ordinary joins. To find people followed by the people you follow:

(d/q '[:find ?suggestion-eid
       :in $ ?user-eid
       :where
       [?user-eid :user/follows ?intermediate-eid]
       [?intermediate-eid :user/follows ?suggestion-eid]
       [(not= ?user-eid ?suggestion-eid)]]
     db user-eid)

Object suggestions = conn.query(
    "[:find ?suggestion-eid " +
    " :in $ ?user-eid " +
    " :where [?user-eid :user/follows ?intermediate-eid] " +
    "        [?intermediate-eid :user/follows ?suggestion-eid] " +
    "        [(not= ?user-eid ?suggestion-eid)]]",
    userEid);

suggestions = conn.query(
    '[:find ?suggestion-eid '
    ' :in $ ?user-eid '
    ' :where [?user-eid :user/follows ?intermediate-eid] '
    '        [?intermediate-eid :user/follows ?suggestion-eid] '
    '        [(not= ?user-eid ?suggestion-eid)]]',
    user_eid)

const suggestions = await conn.query(
  "[:find ?suggestion-eid " +
  " :in $ ?user-eid " +
  " :where [?user-eid :user/follows ?intermediate-eid] " +
  "        [?intermediate-eid :user/follows ?suggestion-eid] " +
  "        [(not= ?user-eid ?suggestion-eid)]]",
  userEid);

3.1 Deep Traversal: Transitive Closure

Transitive closure means the full set of nodes reachable by following the same edge relation one or more times. Add a reflexive base case when the start node should also count as reachable from itself. In practical terms, transitive closure is how you find connections at any distance, such as all reachable nodes in a network. Use recursive rules for transitive closure:

(def reachability-rules
  '[[(reachable ?start-eid ?end-eid)
     [?start-eid :link/to ?end-eid]]

    [(reachable ?start-eid ?end-eid)
     [?start-eid :link/to ?mid-eid]
     (reachable ?mid-eid ?end-eid)]])

Object reachabilityRules = Datalevin.edn(
    "[[(reachable ?start-eid ?end-eid) " +
    "  [?start-eid :link/to ?end-eid]] " +
    " [(reachable ?start-eid ?end-eid) " +
    "  [?start-eid :link/to ?mid-eid] " +
    "  (reachable ?mid-eid ?end-eid)]]");

reachability_rules = interop().read_edn(
    '[[(reachable ?start-eid ?end-eid) '
    '  [?start-eid :link/to ?end-eid]] '
    ' [(reachable ?start-eid ?end-eid) '
    '  [?start-eid :link/to ?mid-eid] '
    '  (reachable ?mid-eid ?end-eid)]]')

const reachabilityRules = await interop().readEdn(
  "[[(reachable ?start-eid ?end-eid) " +
  "  [?start-eid :link/to ?end-eid]] " +
  " [(reachable ?start-eid ?end-eid) " +
  "  [?start-eid :link/to ?mid-eid] " +
  "  (reachable ?mid-eid ?end-eid)]]");

Datalevin evaluates recursive rules to a fixpoint: the point where another round of rule evaluation produces no new result tuples. That means cyclic data does not create a recursive call-stack loop. A fixpoint can still contain many derived tuples, so constrain broad traversals with selective starting facts, bounded rules, or application-level limits when the graph can fan out widely.

3.2 Hierarchies and Taxonomies

Recursive rules are also a natural fit for tree-like graph structures. The same pattern works for place hierarchies, product categories, organization charts, and tag taxonomies. A city belongs to a country through :place/isPartOf, and a tag class belongs to a broader class through :tagclass/isSubclassOf.

(def place-country-rules
  '[[(place-country ?place-eid ?country-eid)
     [?place-eid :place/type "Country"]
     [(ground ?place-eid) ?country-eid]]

    [(place-country ?place-eid ?country-eid)
     [?place-eid :place/isPartOf ?parent-eid]
     (place-country ?parent-eid ?country-eid)]])

(d/q '[:find ?country-name
       :in $ % ?place-name
       :where
       [?place-eid :place/name ?place-name]
       (place-country ?place-eid ?country-eid)
       [?country-eid :place/name ?country-name]]
     db place-country-rules "Paris")

Object placeCountryRules = Datalevin.edn(
    "[[(place-country ?place-eid ?country-eid) " +
    "  [?place-eid :place/type \"Country\"] " +
    "  [(ground ?place-eid) ?country-eid]] " +
    " [(place-country ?place-eid ?country-eid) " +
    "  [?place-eid :place/isPartOf ?parent-eid] " +
    "  (place-country ?parent-eid ?country-eid)]]");

Object result = conn.query("[:find ?country-name " +
    ":in $ % ?place-name " +
    ":where [?place-eid :place/name ?place-name] " +
    "       (place-country ?place-eid ?country-eid) " +
    "       [?country-eid :place/name ?country-name]]",
    placeCountryRules, "Paris");

place_country_rules = interop().read_edn(
    '[[(place-country ?place-eid ?country-eid) '
    '  [?place-eid :place/type "Country"] '
    '  [(ground ?place-eid) ?country-eid]] '
    ' [(place-country ?place-eid ?country-eid) '
    '  [?place-eid :place/isPartOf ?parent-eid] '
    '  (place-country ?parent-eid ?country-eid)]]')

result = conn.query('[:find ?country-name '
    ':in $ % ?place-name '
    ':where [?place-eid :place/name ?place-name] '
    '       (place-country ?place-eid ?country-eid) '
    '       [?country-eid :place/name ?country-name]]',
    place_country_rules, 'Paris')

const placeCountryRules = await interop().readEdn(
  '[[(place-country ?place-eid ?country-eid) ' +
  '  [?place-eid :place/type "Country"] ' +
  '  [(ground ?place-eid) ?country-eid]] ' +
  ' [(place-country ?place-eid ?country-eid) ' +
  '  [?place-eid :place/isPartOf ?parent-eid] ' +
  '  (place-country ?parent-eid ?country-eid)]]');

const result = await conn.query('[:find ?country-name ' +
  ':in $ % ?place-name ' +
  ':where [?place-eid :place/name ?place-name] ' +
  '       (place-country ?place-eid ?country-eid) ' +
  '       [?country-eid :place/name ?country-name]]',
  placeCountryRules, 'Paris');

The base case uses [(ground ?place-eid) ?country-eid] as an identity binding: after ?place-eid is known to be a country, the rule copies that entity id into ?country-eid. In other words, a country is its own country for the purpose of this rule, while non-country places recurse through :place/isPartOf.

This rule works for both direct and indirect containment. If Paris is part of France, and France is part of Europe, the rule stops at the first ancestor whose :place/type is "Country".

3.3 Bounded Neighborhoods with Distance

Some graph queries should not traverse arbitrarily far. They ask for neighbors within a fixed radius, while preserving the distance so the final result can be ordered or aggregated.

Listing 13.1 shows one bounded-neighborhood pattern: unroll the fixed distances into separate rule bodies and bind the distance explicitly.

In this example, friendship is a join entity with two reference attributes, :knows/person1 and :knows/person2, following the Section 2 pattern. This is also how LDBC-SNB models friendship. The queries treat the edge as directional from :knows/person1 to :knows/person2; for mutual friendship, store both orientations or query both orientations.

(def friends-3-rules
  '[[(friends-3 ?start-eid ?friend-eid ?dist)
     [?knows-eid :knows/person1 ?start-eid]
     [?knows-eid :knows/person2 ?friend-eid]
     [(ground 1) ?dist]]

    [(friends-3 ?start-eid ?friend-eid ?dist)
     [?knows1-eid :knows/person1 ?start-eid]
     [?knows1-eid :knows/person2 ?mid-eid]
     [?knows2-eid :knows/person1 ?mid-eid]
     [?knows2-eid :knows/person2 ?friend-eid]
     [(not= ?friend-eid ?start-eid)]
     [(ground 2) ?dist]]

    [(friends-3 ?start-eid ?friend-eid ?dist)
     [?knows1-eid :knows/person1 ?start-eid]
     [?knows1-eid :knows/person2 ?mid1-eid]
     [?knows2-eid :knows/person1 ?mid1-eid]
     [?knows2-eid :knows/person2 ?mid2-eid]
     [(not= ?mid2-eid ?start-eid)]
     [?knows3-eid :knows/person1 ?mid2-eid]
     [?knows3-eid :knows/person2 ?friend-eid]
     [(not= ?friend-eid ?start-eid)]
     [(not= ?friend-eid ?mid1-eid)]
     [(ground 3) ?dist]]])

(d/q '[:find (min ?dist) ?friend-id
       :in $ % ?person-id
       :where
       [?start-eid :person/id ?person-id]
       (friends-3 ?start-eid ?friend-eid ?dist)
       [?friend-eid :person/id ?friend-id]]
     db friends-3-rules person-id)

Object friends3Rules = Datalevin.edn(
    "[[(friends-3 ?start-eid ?friend-eid ?dist) " +
    "  [?knows-eid :knows/person1 ?start-eid] " +
    "  [?knows-eid :knows/person2 ?friend-eid] " +
    "  [(ground 1) ?dist]] " +
    " [(friends-3 ?start-eid ?friend-eid ?dist) " +
    "  [?knows1-eid :knows/person1 ?start-eid] " +
    "  [?knows1-eid :knows/person2 ?mid-eid] " +
    "  [?knows2-eid :knows/person1 ?mid-eid] " +
    "  [?knows2-eid :knows/person2 ?friend-eid] " +
    "  [(not= ?friend-eid ?start-eid)] " +
    "  [(ground 2) ?dist]] " +
    " [(friends-3 ?start-eid ?friend-eid ?dist) " +
    "  [?knows1-eid :knows/person1 ?start-eid] " +
    "  [?knows1-eid :knows/person2 ?mid1-eid] " +
    "  [?knows2-eid :knows/person1 ?mid1-eid] " +
    "  [?knows2-eid :knows/person2 ?mid2-eid] " +
    "  [(not= ?mid2-eid ?start-eid)] " +
    "  [?knows3-eid :knows/person1 ?mid2-eid] " +
    "  [?knows3-eid :knows/person2 ?friend-eid] " +
    "  [(not= ?friend-eid ?start-eid)] " +
    "  [(not= ?friend-eid ?mid1-eid)] " +
    "  [(ground 3) ?dist]]]");

Object result = conn.query("[:find (min ?dist) ?friend-id " +
    ":in $ % ?person-id " +
    ":where [?start-eid :person/id ?person-id] " +
    "       (friends-3 ?start-eid ?friend-eid ?dist) " +
    "       [?friend-eid :person/id ?friend-id]]",
    friends3Rules, personId);

friends_3_rules = interop().read_edn(
    '[[(friends-3 ?start-eid ?friend-eid ?dist) '
    '  [?knows-eid :knows/person1 ?start-eid] '
    '  [?knows-eid :knows/person2 ?friend-eid] '
    '  [(ground 1) ?dist]] '
    ' [(friends-3 ?start-eid ?friend-eid ?dist) '
    '  [?knows1-eid :knows/person1 ?start-eid] '
    '  [?knows1-eid :knows/person2 ?mid-eid] '
    '  [?knows2-eid :knows/person1 ?mid-eid] '
    '  [?knows2-eid :knows/person2 ?friend-eid] '
    '  [(not= ?friend-eid ?start-eid)] '
    '  [(ground 2) ?dist]] '
    ' [(friends-3 ?start-eid ?friend-eid ?dist) '
    '  [?knows1-eid :knows/person1 ?start-eid] '
    '  [?knows1-eid :knows/person2 ?mid1-eid] '
    '  [?knows2-eid :knows/person1 ?mid1-eid] '
    '  [?knows2-eid :knows/person2 ?mid2-eid] '
    '  [(not= ?mid2-eid ?start-eid)] '
    '  [?knows3-eid :knows/person1 ?mid2-eid] '
    '  [?knows3-eid :knows/person2 ?friend-eid] '
    '  [(not= ?friend-eid ?start-eid)] '
    '  [(not= ?friend-eid ?mid1-eid)] '
    '  [(ground 3) ?dist]]]')

result = conn.query('[:find (min ?dist) ?friend-id '
    ':in $ % ?person-id '
    ':where [?start-eid :person/id ?person-id] '
    '       (friends-3 ?start-eid ?friend-eid ?dist) '
    '       [?friend-eid :person/id ?friend-id]]',
    friends_3_rules, person_id)

const friends3Rules = await interop().readEdn(
  '[[(friends-3 ?start-eid ?friend-eid ?dist) ' +
  '  [?knows-eid :knows/person1 ?start-eid] ' +
  '  [?knows-eid :knows/person2 ?friend-eid] ' +
  '  [(ground 1) ?dist]] ' +
  ' [(friends-3 ?start-eid ?friend-eid ?dist) ' +
  '  [?knows1-eid :knows/person1 ?start-eid] ' +
  '  [?knows1-eid :knows/person2 ?mid-eid] ' +
  '  [?knows2-eid :knows/person1 ?mid-eid] ' +
  '  [?knows2-eid :knows/person2 ?friend-eid] ' +
  '  [(not= ?friend-eid ?start-eid)] ' +
  '  [(ground 2) ?dist]] ' +
  ' [(friends-3 ?start-eid ?friend-eid ?dist) ' +
  '  [?knows1-eid :knows/person1 ?start-eid] ' +
  '  [?knows1-eid :knows/person2 ?mid1-eid] ' +
  '  [?knows2-eid :knows/person1 ?mid1-eid] ' +
  '  [?knows2-eid :knows/person2 ?mid2-eid] ' +
  '  [(not= ?mid2-eid ?start-eid)] ' +
  '  [?knows3-eid :knows/person1 ?mid2-eid] ' +
  '  [?knows3-eid :knows/person2 ?friend-eid] ' +
  '  [(not= ?friend-eid ?start-eid)] ' +
  '  [(not= ?friend-eid ?mid1-eid)] ' +
  '  [(ground 3) ?dist]]]');

const result = await conn.query('[:find (min ?dist) ?friend-id ' +
  ':in $ % ?person-id ' +
  ':where [?start-eid :person/id ?person-id] ' +
  '       (friends-3 ?start-eid ?friend-eid ?dist) ' +
  '       [?friend-eid :person/id ?friend-id]]',
  friends3Rules, personId);

The rule emits one row for each path shape. The query uses (min ?dist) to keep the shortest distance for each reachable person.

3.4 Mutual Recursion: Alternating Edge Types

Some graph traversals are not a single repeated edge. Datalevin's rule engine also supports mutually recursive rules, where two or more rules call each other until the result reaches a fixpoint. This pattern is useful for alternating path semantics.

For example, suppose a graph has two edge types, :edge/a and :edge/b, and you want to find paths that end with an :edge/a step after alternating between the two edge types:

(def alternating-rules
  '[[(path-a ?from-eid ?to-eid)
     [?from-eid :edge/a ?to-eid]]

    [(path-a ?from-eid ?to-eid)
     [?mid-eid :edge/a ?to-eid]
     (path-b ?from-eid ?mid-eid)]

    [(path-b ?from-eid ?to-eid)
     [?from-eid :edge/b ?to-eid]]

    [(path-b ?from-eid ?to-eid)
     [?mid-eid :edge/b ?to-eid]
     (path-a ?from-eid ?mid-eid)]])

(d/q '[:find ?to-eid
       :in $ % ?from-eid
       :where
       (path-a ?from-eid ?to-eid)]
     db alternating-rules start-eid)

Object alternatingRules = Datalevin.edn(
    "[[(path-a ?from-eid ?to-eid) " +
    "  [?from-eid :edge/a ?to-eid]] " +
    " [(path-a ?from-eid ?to-eid) " +
    "  [?mid-eid :edge/a ?to-eid] " +
    "  (path-b ?from-eid ?mid-eid)] " +
    " [(path-b ?from-eid ?to-eid) " +
    "  [?from-eid :edge/b ?to-eid]] " +
    " [(path-b ?from-eid ?to-eid) " +
    "  [?mid-eid :edge/b ?to-eid] " +
    "  (path-a ?from-eid ?mid-eid)]]");

Object result = conn.query(
    "[:find ?to-eid " +
    " :in $ % ?from-eid " +
    " :where (path-a ?from-eid ?to-eid)]",
    alternatingRules,
    startEid);

alternating_rules = interop().read_edn(
    '[[(path-a ?from-eid ?to-eid) '
    '  [?from-eid :edge/a ?to-eid]] '
    ' [(path-a ?from-eid ?to-eid) '
    '  [?mid-eid :edge/a ?to-eid] '
    '  (path-b ?from-eid ?mid-eid)] '
    ' [(path-b ?from-eid ?to-eid) '
    '  [?from-eid :edge/b ?to-eid]] '
    ' [(path-b ?from-eid ?to-eid) '
    '  [?mid-eid :edge/b ?to-eid] '
    '  (path-a ?from-eid ?mid-eid)]]')

result = conn.query(
    '[:find ?to-eid '
    ' :in $ % ?from-eid '
    ' :where (path-a ?from-eid ?to-eid)]',
    alternating_rules,
    start_eid)

const alternatingRules = await interop().readEdn(
  "[[(path-a ?from-eid ?to-eid) " +
  "  [?from-eid :edge/a ?to-eid]] " +
  " [(path-a ?from-eid ?to-eid) " +
  "  [?mid-eid :edge/a ?to-eid] " +
  "  (path-b ?from-eid ?mid-eid)] " +
  " [(path-b ?from-eid ?to-eid) " +
  "  [?from-eid :edge/b ?to-eid]] " +
  " [(path-b ?from-eid ?to-eid) " +
  "  [?mid-eid :edge/b ?to-eid] " +
  "  (path-a ?from-eid ?mid-eid)]]");

const result = await conn.query(
  "[:find ?to-eid " +
  " :in $ % ?from-eid " +
  " :where (path-a ?from-eid ?to-eid)]",
  alternatingRules,
  startEid);

path-a depends on path-b, and path-b depends on path-a. Datalevin evaluates these rules together, rather than expanding one call stack top-down. That is what allows mutually recursive graph definitions to remain practical.

3.5 Branching Traversals with `or-join`

Complex queries often need to combine several graph shapes into one logical binding. For graph neighborhoods such as "people within two hops" from a start person, where a person can be reached either directly or through one intermediate friend, or-join can be used to cover the alternatives:

(d/q '[:find ?person-eid
       :in $ ?person-id
       :where
       [?start-eid :person/id ?person-id]
       (or-join [?start-eid ?person-eid]
                ;; one hop
                (and [?knows-eid :knows/person1 ?start-eid]
                     [?knows-eid :knows/person2 ?person-eid])

                ;; two hops
                (and [?knows1-eid :knows/person1 ?start-eid]
                     [?knows1-eid :knows/person2 ?mid-eid]
                     [?knows2-eid :knows/person1 ?mid-eid]
                     [?knows2-eid :knows/person2 ?person-eid]
                     [(not= ?person-eid ?start-eid)]))]
     db person-id)

Object result = conn.query(
    "[:find ?person-eid " +
    " :in $ ?person-id " +
    " :where [?start-eid :person/id ?person-id] " +
    "        (or-join [?start-eid ?person-eid] " +
    "          (and [?knows-eid :knows/person1 ?start-eid] " +
    "               [?knows-eid :knows/person2 ?person-eid]) " +
    "          (and [?knows1-eid :knows/person1 ?start-eid] " +
    "               [?knows1-eid :knows/person2 ?mid-eid] " +
    "               [?knows2-eid :knows/person1 ?mid-eid] " +
    "               [?knows2-eid :knows/person2 ?person-eid] " +
    "               [(not= ?person-eid ?start-eid)]))]",
    personId);

result = conn.query(
    '[:find ?person-eid '
    ' :in $ ?person-id '
    ' :where [?start-eid :person/id ?person-id] '
    '        (or-join [?start-eid ?person-eid] '
    '          (and [?knows-eid :knows/person1 ?start-eid] '
    '               [?knows-eid :knows/person2 ?person-eid]) '
    '          (and [?knows1-eid :knows/person1 ?start-eid] '
    '               [?knows1-eid :knows/person2 ?mid-eid] '
    '               [?knows2-eid :knows/person1 ?mid-eid] '
    '               [?knows2-eid :knows/person2 ?person-eid] '
    '               [(not= ?person-eid ?start-eid)]))]',
    person_id)

const result = await conn.query(
  "[:find ?person-eid " +
  " :in $ ?person-id " +
  " :where [?start-eid :person/id ?person-id] " +
  "        (or-join [?start-eid ?person-eid] " +
  "          (and [?knows-eid :knows/person1 ?start-eid] " +
  "               [?knows-eid :knows/person2 ?person-eid]) " +
  "          (and [?knows1-eid :knows/person1 ?start-eid] " +
  "               [?knows1-eid :knows/person2 ?mid-eid] " +
  "               [?knows2-eid :knows/person1 ?mid-eid] " +
  "               [?knows2-eid :knows/person2 ?person-eid] " +
  "               [(not= ?person-eid ?start-eid)]))]",
  personId);

Use or-join when the alternatives bind the same logical result through different graph patterns. The join variables, here ?start-eid and ?person-eid, tell the query engine which values must be shared between the branch and the rest of the query. Each or-join branch that contains more than one clause is wrapped in (and ...), because the branch itself must be one syntactic alternative. This is especially useful before aggregating over messages, forums, tags, or memberships reached through several allowed path shapes.

3.6 Excluding Graph Shapes with `not-join`

Recommendation queries often need an anti-join: keep candidates from one pattern only when no matching fact exists in another pattern. In graph terms, this means finding nodes reachable by one path, but excluding nodes reachable by another path. A common example is friends-of-friends who are not already direct friends.

(d/q '[:find ?person-id
       :in $ ?start-person-id
       :where
       [?start-eid :person/id ?start-person-id]

       ;; exactly two hops
       [?knows1-eid :knows/person1 ?start-eid]
       [?knows1-eid :knows/person2 ?mid-eid]
       [?knows2-eid :knows/person1 ?mid-eid]
       [?knows2-eid :knows/person2 ?person-eid]
       [(not= ?person-eid ?start-eid)]

       ;; exclude direct friends
       (not-join [?start-eid ?person-eid]
                 [?knows-eid :knows/person1 ?start-eid]
                 [?knows-eid :knows/person2 ?person-eid])

       [?person-eid :person/id ?person-id]]
     db start-person-id)

Object result = conn.query("[:find ?person-id " +
    ":in $ ?start-person-id " +
    ":where [?start-eid :person/id ?start-person-id] " +
    "       [?knows1-eid :knows/person1 ?start-eid] " +
    "       [?knows1-eid :knows/person2 ?mid-eid] " +
    "       [?knows2-eid :knows/person1 ?mid-eid] " +
    "       [?knows2-eid :knows/person2 ?person-eid] " +
    "       [(not= ?person-eid ?start-eid)] " +
    "       (not-join [?start-eid ?person-eid] " +
    "                 [?knows-eid :knows/person1 ?start-eid] " +
    "                 [?knows-eid :knows/person2 ?person-eid]) " +
    "       [?person-eid :person/id ?person-id]]",
    startPersonId);

result = conn.query('[:find ?person-id '
    ':in $ ?start-person-id '
    ':where [?start-eid :person/id ?start-person-id] '
    '       [?knows1-eid :knows/person1 ?start-eid] '
    '       [?knows1-eid :knows/person2 ?mid-eid] '
    '       [?knows2-eid :knows/person1 ?mid-eid] '
    '       [?knows2-eid :knows/person2 ?person-eid] '
    '       [(not= ?person-eid ?start-eid)] '
    '       (not-join [?start-eid ?person-eid] '
    '                 [?knows-eid :knows/person1 ?start-eid] '
    '                 [?knows-eid :knows/person2 ?person-eid]) '
    '       [?person-eid :person/id ?person-id]]',
    start_person_id)

const result = await conn.query('[:find ?person-id ' +
  ':in $ ?start-person-id ' +
  ':where [?start-eid :person/id ?start-person-id] ' +
  '       [?knows1-eid :knows/person1 ?start-eid] ' +
  '       [?knows1-eid :knows/person2 ?mid-eid] ' +
  '       [?knows2-eid :knows/person1 ?mid-eid] ' +
  '       [?knows2-eid :knows/person2 ?person-eid] ' +
  '       [(not= ?person-eid ?start-eid)] ' +
  '       (not-join [?start-eid ?person-eid] ' +
  '                 [?knows-eid :knows/person1 ?start-eid] ' +
  '                 [?knows-eid :knows/person2 ?person-eid]) ' +
  '       [?person-eid :person/id ?person-id]]',
  startPersonId);

Use not-join when the negated graph pattern depends on a specific set of outer variables. Here the exclusion is about the pair ?start-eid and ?person-eid; it should not depend on unrelated variables that happen to appear elsewhere in the query.

4. More Graph Problem Shapes

The previous examples cover social networks and hierarchies, but the same modeling tools apply to many graph problems. The important step is to identify what the nodes are, what the edges mean, and whether the edge needs its own facts.

4.1 Co-Appearance and Degrees of Separation

The "six degrees of Kevin Bacon" problem, depicted in Figure 13.3, is a useful graph example because it is not a tree. It is a dense bipartite graph: two kinds of nodes, people and movies, with many connections between the two sets. People connect to movies through credits, and two people are adjacent if they worked on the same movie. Andrew Dennis used this problem to show both Datalog joins and application-level breadth-first search over database facts [3]. The same idea applies naturally to Datalevin.

Co-appearance as a bipartite graph: people (Kevin Bacon, John Belushi, Tom Hanks) and movies (Animal House, Apollo 13) connected through Credit entities, projected to a person-to-person acted-with graph where Bacon links to Belushi via Animal House and to Hanks via Apollo 13, while Belushi and Hanks share no movie

Model co-appearance through relationship nodes

Model the credit as an entity, not as redundant lists on both actors and movies. The credit is the durable fact that connects a person to a movie and can carry role, billing, source, or time facts later.

(def movie-schema
  {:person/name   {:db/valueType :db.type/string
                   :db/unique    :db.unique/identity}
   :movie/title   {:db/valueType :db.type/string
                   :db/unique    :db.unique/identity}
   :movie/year    {:db/valueType :db.type/long}
   :credit/person {:db/valueType :db.type/ref}
   :credit/movie  {:db/valueType :db.type/ref}
   :credit/role   {:db/valueType :db.type/keyword}})

Schema movieSchema = Datalevin.schema()
    .attr(":person/name", Schema.attribute()
        .valueType(Schema.ValueType.STRING)
        .unique(Schema.Unique.IDENTITY))
    .attr(":movie/title", Schema.attribute()
        .valueType(Schema.ValueType.STRING)
        .unique(Schema.Unique.IDENTITY))
    .attr(":movie/year", Schema.attribute()
        .valueType(Schema.ValueType.LONG))
    .attr(":credit/person", Schema.attribute()
        .valueType(Schema.ValueType.REF))
    .attr(":credit/movie", Schema.attribute()
        .valueType(Schema.ValueType.REF))
    .attr(":credit/role", Schema.attribute()
        .valueType(Schema.ValueType.KEYWORD));

movie_schema = {
    ":person/name": {":db/valueType": ":db.type/string",
                     ":db/unique": ":db.unique/identity"},
    ":movie/title": {":db/valueType": ":db.type/string",
                     ":db/unique": ":db.unique/identity"},
    ":movie/year": {":db/valueType": ":db.type/long"},
    ":credit/person": {":db/valueType": ":db.type/ref"},
    ":credit/movie": {":db/valueType": ":db.type/ref"},
    ":credit/role": {":db/valueType": ":db.type/keyword"}}

const movieSchema = {
  ":person/name": {":db/valueType": ":db.type/string",
                   ":db/unique": ":db.unique/identity"},
  ":movie/title": {":db/valueType": ":db.type/string",
                   ":db/unique": ":db.unique/identity"},
  ":movie/year": {":db/valueType": ":db.type/long"},
  ":credit/person": {":db/valueType": ":db.type/ref"},
  ":credit/movie": {":db/valueType": ":db.type/ref"},
  ":credit/role": {":db/valueType": ":db.type/keyword"}
};

A direct co-appearance query is a join through :credit/movie:

(d/q '[:find ?movie-title
       :in $ ?name-1 ?name-2
       :where
       [?person1-eid :person/name ?name-1]
       [?person2-eid :person/name ?name-2]
       [?credit1-eid :credit/person ?person1-eid]
       [?credit1-eid :credit/movie ?movie-eid]
       [?credit2-eid :credit/person ?person2-eid]
       [?credit2-eid :credit/movie ?movie-eid]
       [(not= ?person1-eid ?person2-eid)]
       [?movie-eid :movie/title ?movie-title]]
     db
     "Kevin Bacon"
     "John Belushi")

Object movies = conn.query(
    "[:find ?movie-title " +
    " :in $ ?name-1 ?name-2 " +
    " :where [?person1-eid :person/name ?name-1] " +
    "        [?person2-eid :person/name ?name-2] " +
    "        [?credit1-eid :credit/person ?person1-eid] " +
    "        [?credit1-eid :credit/movie ?movie-eid] " +
    "        [?credit2-eid :credit/person ?person2-eid] " +
    "        [?credit2-eid :credit/movie ?movie-eid] " +
    "        [(not= ?person1-eid ?person2-eid)] " +
    "        [?movie-eid :movie/title ?movie-title]]",
    "Kevin Bacon",
    "John Belushi");

movies = conn.query(
    '[:find ?movie-title '
    ' :in $ ?name-1 ?name-2 '
    ' :where [?person1-eid :person/name ?name-1] '
    '        [?person2-eid :person/name ?name-2] '
    '        [?credit1-eid :credit/person ?person1-eid] '
    '        [?credit1-eid :credit/movie ?movie-eid] '
    '        [?credit2-eid :credit/person ?person2-eid] '
    '        [?credit2-eid :credit/movie ?movie-eid] '
    '        [(not= ?person1-eid ?person2-eid)] '
    '        [?movie-eid :movie/title ?movie-title]]',
    "Kevin Bacon",
    "John Belushi")

const movies = await conn.query(
  "[:find ?movie-title " +
  " :in $ ?name-1 ?name-2 " +
  " :where [?person1-eid :person/name ?name-1] " +
  "        [?person2-eid :person/name ?name-2] " +
  "        [?credit1-eid :credit/person ?person1-eid] " +
  "        [?credit1-eid :credit/movie ?movie-eid] " +
  "        [?credit2-eid :credit/person ?person2-eid] " +
  "        [?credit2-eid :credit/movie ?movie-eid] " +
  "        [(not= ?person1-eid ?person2-eid)] " +
  "        [?movie-eid :movie/title ?movie-title]]",
  "Kevin Bacon",
  "John Belushi");

That answers "Bacon number 1" questions. For a fixed small radius, you can add more joins or generate bounded rules, as shown earlier in this chapter. For an unknown shortest path, use the database to supply neighbors and run a standard graph algorithm in the application. Datalevin makes this practical because the same current database snapshot can be queried repeatedly and refs are indexed.

(defn acted-with
  "Return [other-eid movie-eid] pairs adjacent to actor-eid."
  [db actor-eid]
  (d/q '[:find ?other-eid ?movie-eid
         :in $ ?actor-eid
         :where
         [?credit1-eid :credit/person ?actor-eid]
         [?credit1-eid :credit/movie ?movie-eid]
         [?credit2-eid :credit/movie ?movie-eid]
         [?credit2-eid :credit/person ?other-eid]
         [(not= ?actor-eid ?other-eid)]]
       db actor-eid))

(defn entity-label [db eid]
  (let [m (d/pull db '[:person/name :movie/title] eid)]
    (or (:person/name m)
        (:movie/title m))))

(defn bacon-path
  "Return one shortest alternating [actor movie actor ...] path."
  [db start-name target-name]
  (let [start-eid  (d/q '[:find ?person-eid .
                          :in $ ?name
                          :where [?person-eid :person/name ?name]]
                        db start-name)
        target-eid (d/q '[:find ?person-eid .
                          :in $ ?name
                          :where [?person-eid :person/name ?name]]
                        db target-name)
        edges  (memoize #(acted-with db %))]
    (loop [queue (conj clojure.lang.PersistentQueue/EMPTY [start-eid])
           seen  #{start-eid}]
      (when-let [path (peek queue)]
        (let [actor-eid (peek path)]
          (if (= actor-eid target-eid)
            (mapv (partial entity-label db) path)
            (let [next-edges (remove #(seen (first %)) (edges actor-eid))]
              (recur
                (into (pop queue)
                      (map (fn [[other-eid movie-eid]]
                             (conj path movie-eid other-eid))
                           next-edges))
                (into seen (map first next-edges))))))))))

record CreditEdge(Object otherEid, Object movieEid) {}

static List<CreditEdge> actedWith(Connection conn, Object actorEid) {
    List<?> rows = (List<?>) conn.query(
        "[:find ?other-eid ?movie-eid " +
        " :in $ ?actor-eid " +
        " :where [?credit1-eid :credit/person ?actor-eid] " +
        "        [?credit1-eid :credit/movie ?movie-eid] " +
        "        [?credit2-eid :credit/movie ?movie-eid] " +
        "        [?credit2-eid :credit/person ?other-eid] " +
        "        [(not= ?actor-eid ?other-eid)]]",
        actorEid);
    return rows.stream()
        .map(row -> (List<?>) row)
        .map(row -> new CreditEdge(row.get(0), row.get(1)))
        .toList();
}

static String entityLabel(Connection conn, Object eid) {
    Map<?, ?> entity = conn.pull("[:person/name :movie/title]", eid);
    Object person = entity.get(Datalevin.kw(":person/name"));
    Object movie = entity.get(Datalevin.kw(":movie/title"));
    return String.valueOf(person != null ? person : movie);
}

static List<String> baconPath(Connection conn,
                              String startName,
                              String targetName) {
    Object startEid = conn.query(
        "[:find ?person-eid . :in $ ?name :where [?person-eid :person/name ?name]]",
        startName);
    Object targetEid = conn.query(
        "[:find ?person-eid . :in $ ?name :where [?person-eid :person/name ?name]]",
        targetName);

    Queue<List<Object>> queue = new ArrayDeque<>();
    Set<Object> seen = new HashSet<>();
    queue.add(List.of(startEid));
    seen.add(startEid);

    while (!queue.isEmpty()) {
        List<Object> path = queue.remove();
        Object actorEid = path.get(path.size() - 1);
        if (actorEid.equals(targetEid)) {
            return path.stream()
                .map(eid -> entityLabel(conn, eid))
                .toList();
        }
        for (CreditEdge edge : actedWith(conn, actorEid)) {
            if (seen.add(edge.otherEid())) {
                ArrayList<Object> next = new ArrayList<>(path);
                next.add(edge.movieEid());
                next.add(edge.otherEid());
                queue.add(next);
            }
        }
    }
    return List.of();
}

from collections import deque

def acted_with(conn, actor_eid):
    return conn.query("""
[:find ?other-eid ?movie-eid
 :in $ ?actor-eid
 :where
 [?credit1-eid :credit/person ?actor-eid]
 [?credit1-eid :credit/movie ?movie-eid]
 [?credit2-eid :credit/movie ?movie-eid]
 [?credit2-eid :credit/person ?other-eid]
 [(not= ?actor-eid ?other-eid)]]
""", actor_eid)

def entity_label(conn, eid):
    entity = conn.pull("[:person/name :movie/title]", eid)
    return entity.get(":person/name") or entity.get(":movie/title")

def bacon_path(conn, start_name, target_name):
    start_eid = conn.query(
        "[:find ?person-eid . :in $ ?name :where [?person-eid :person/name ?name]]",
        start_name)
    target_eid = conn.query(
        "[:find ?person-eid . :in $ ?name :where [?person-eid :person/name ?name]]",
        target_name)

    queue = deque([[start_eid]])
    seen = {start_eid}

    while queue:
        path = queue.popleft()
        actor_eid = path[-1]
        if actor_eid == target_eid:
            return [entity_label(conn, eid) for eid in path]
        for other_eid, movie_eid in acted_with(conn, actor_eid):
            if other_eid not in seen:
                seen.add(other_eid)
                queue.append([*path, movie_eid, other_eid])
    return []

async function actedWith(conn, actorEid) {
  return await conn.query(
    `[:find ?other-eid ?movie-eid
      :in $ ?actor-eid
      :where
      [?credit1-eid :credit/person ?actor-eid]
      [?credit1-eid :credit/movie ?movie-eid]
      [?credit2-eid :credit/movie ?movie-eid]
      [?credit2-eid :credit/person ?other-eid]
      [(not= ?actor-eid ?other-eid)]]`,
    actorEid);
}

async function entityLabel(conn, eid) {
  const entity = await conn.pull("[:person/name :movie/title]", eid);
  return entity[":person/name"] ?? entity[":movie/title"];
}

async function baconPath(conn, startName, targetName) {
  const startEid = await conn.query(
    "[:find ?person-eid . :in $ ?name :where [?person-eid :person/name ?name]]",
    startName);
  const targetEid = await conn.query(
    "[:find ?person-eid . :in $ ?name :where [?person-eid :person/name ?name]]",
    targetName);

  const queue = [[startEid]];
  const seen = new Set([startEid]);

  while (queue.length > 0) {
    const path = queue.shift();
    const actorEid = path[path.length - 1];
    if (actorEid === targetEid) {
      return await Promise.all(path.map((eid) => entityLabel(conn, eid)));
    }
    for (const [otherEid, movieEid] of await actedWith(conn, actorEid)) {
      if (!seen.has(otherEid)) {
        seen.add(otherEid);
        queue.push([...path, movieEid, otherEid]);
      }
    }
  }
  return [];
}

Listing 13.2 treats Datalevin as the graph store and keeps shortest-path policy in ordinary code. That is often a practical split: use Datalog for the local neighborhood relation, and use a graph algorithm when the query needs a global search strategy.

4.2 Dependency and Impact Analysis

Package managers, build systems, data pipelines, and microservice deployments often need the reverse of a dependency graph question. If core changes, what must be rebuilt? If a table changes, which reports are affected?

Model each dependency as an edge from the dependent item to the thing it uses:

{:component/name {:db/valueType :db.type/string
                  :db/unique    :db.unique/identity}
 :component/uses {:db/valueType :db.type/ref}}

Schema componentSchema = Datalevin.schema()
    .attr(":component/name", Schema.attribute()
        .valueType(Schema.ValueType.STRING)
        .unique(Schema.Unique.IDENTITY))
    .attr(":component/uses", Schema.attribute()
        .valueType(Schema.ValueType.REF));

component_schema = {
    ":component/name": {":db/valueType": ":db.type/string",
                        ":db/unique": ":db.unique/identity"},
    ":component/uses": {":db/valueType": ":db.type/ref"}}

const componentSchema = {
  ":component/name": {":db/valueType": ":db.type/string",
                      ":db/unique": ":db.unique/identity"},
  ":component/uses": {":db/valueType": ":db.type/ref"}
};

Then define reachability over :component/uses:

(def dependency-rules
  '[[(depends-on ?component-eid ?dependency-eid)
     [?component-eid :component/uses ?dependency-eid]]

    [(depends-on ?component-eid ?dependency-eid)
     [?component-eid :component/uses ?direct-eid]
     (depends-on ?direct-eid ?dependency-eid)]])

Object dependencyRules = Datalevin.edn(
    "[[(depends-on ?component-eid ?dependency-eid) " +
    "  [?component-eid :component/uses ?dependency-eid]] " +
    " [(depends-on ?component-eid ?dependency-eid) " +
    "  [?component-eid :component/uses ?direct-eid] " +
    "  (depends-on ?direct-eid ?dependency-eid)]]");

dependency_rules = interop().read_edn(
    '[[(depends-on ?component-eid ?dependency-eid) '
    '  [?component-eid :component/uses ?dependency-eid]] '
    ' [(depends-on ?component-eid ?dependency-eid) '
    '  [?component-eid :component/uses ?direct-eid] '
    '  (depends-on ?direct-eid ?dependency-eid)]]')

const dependencyRules = await interop().readEdn(
  "[[(depends-on ?component-eid ?dependency-eid) " +
  "  [?component-eid :component/uses ?dependency-eid]] " +
  " [(depends-on ?component-eid ?dependency-eid) " +
  "  [?component-eid :component/uses ?direct-eid] " +
  "  (depends-on ?direct-eid ?dependency-eid)]]");

To find everything impacted by a changed component, bind the dependency side and ask which components depend on it:

(d/q '[:find ?impacted-name
       :in $ % ?changed-name
       :where
       [?changed-eid :component/name ?changed-name]
       (depends-on ?impacted-eid ?changed-eid)
       [?impacted-eid :component/name ?impacted-name]]
     db dependency-rules "core")

Object impacted = conn.query(
    "[:find ?impacted-name " +
    " :in $ % ?changed-name " +
    " :where [?changed-eid :component/name ?changed-name] " +
    "        (depends-on ?impacted-eid ?changed-eid) " +
    "        [?impacted-eid :component/name ?impacted-name]]",
    dependencyRules,
    "core");

impacted = conn.query(
    '[:find ?impacted-name '
    ' :in $ % ?changed-name '
    ' :where [?changed-eid :component/name ?changed-name] '
    '        (depends-on ?impacted-eid ?changed-eid) '
    '        [?impacted-eid :component/name ?impacted-name]]',
    dependency_rules,
    "core")

const impacted = await conn.query(
  "[:find ?impacted-name " +
  " :in $ % ?changed-name " +
  " :where [?changed-eid :component/name ?changed-name] " +
  "        (depends-on ?impacted-eid ?changed-eid) " +
  "        [?impacted-eid :component/name ?impacted-name]]",
  dependencyRules,
  "core");

The same pattern works for "which policies inherit this rule?", "which dashboards read from this dataset?", and "which generated files depend on this source file?"

4.3 Weighted Paths and Route Search

Some graph questions are about reachability; others are about optimal paths. Route planning, network latency, risk propagation, and cost-based dependency planning all attach weights to edges.

Model a weighted edge as an entity:

{:route/from {:db/valueType :db.type/ref}
 :route/to   {:db/valueType :db.type/ref}
 :route/km   {:db/valueType :db.type/double}}

Schema routeSchema = Datalevin.schema()
    .attr(":route/from", Schema.attribute()
        .valueType(Schema.ValueType.REF))
    .attr(":route/to", Schema.attribute()
        .valueType(Schema.ValueType.REF))
    .attr(":route/km", Schema.attribute()
        .valueType(Schema.ValueType.DOUBLE));

route_schema = {
    ":route/from": {":db/valueType": ":db.type/ref"},
    ":route/to": {":db/valueType": ":db.type/ref"},
    ":route/km": {":db/valueType": ":db.type/double"}}

const routeSchema = {
  ":route/from": {":db/valueType": ":db.type/ref"},
  ":route/to": {":db/valueType": ":db.type/ref"},
  ":route/km": {":db/valueType": ":db.type/double"}
};

Datalog can enumerate bounded path shapes and sum their weights when the bound is small:

(d/q '[:find ?mid-name ?km
       :in $ ?from-name ?to-name
       :where
       [?from-eid :place/name ?from-name]
       [?to-eid :place/name ?to-name]
       [?route1-eid :route/from ?from-eid]
       [?route1-eid :route/to ?mid-eid]
       [?route1-eid :route/km ?km1]
       [?route2-eid :route/from ?mid-eid]
       [?route2-eid :route/to ?to-eid]
       [?route2-eid :route/km ?km2]
       [(+ ?km1 ?km2) ?km]
       [?mid-eid :place/name ?mid-name]]
     db "Paris" "Berlin")

Object routes = conn.query(
    "[:find ?mid-name ?km " +
    " :in $ ?from-name ?to-name " +
    " :where [?from-eid :place/name ?from-name] " +
    "        [?to-eid :place/name ?to-name] " +
    "        [?route1-eid :route/from ?from-eid] " +
    "        [?route1-eid :route/to ?mid-eid] " +
    "        [?route1-eid :route/km ?km1] " +
    "        [?route2-eid :route/from ?mid-eid] " +
    "        [?route2-eid :route/to ?to-eid] " +
    "        [?route2-eid :route/km ?km2] " +
    "        [(+ ?km1 ?km2) ?km] " +
    "        [?mid-eid :place/name ?mid-name]]",
    "Paris",
    "Berlin");

routes = conn.query(
    '[:find ?mid-name ?km '
    ' :in $ ?from-name ?to-name '
    ' :where [?from-eid :place/name ?from-name] '
    '        [?to-eid :place/name ?to-name] '
    '        [?route1-eid :route/from ?from-eid] '
    '        [?route1-eid :route/to ?mid-eid] '
    '        [?route1-eid :route/km ?km1] '
    '        [?route2-eid :route/from ?mid-eid] '
    '        [?route2-eid :route/to ?to-eid] '
    '        [?route2-eid :route/km ?km2] '
    '        [(+ ?km1 ?km2) ?km] '
    '        [?mid-eid :place/name ?mid-name]]',
    "Paris",
    "Berlin")

const routes = await conn.query(
  "[:find ?mid-name ?km " +
  " :in $ ?from-name ?to-name " +
  " :where [?from-eid :place/name ?from-name] " +
  "        [?to-eid :place/name ?to-name] " +
  "        [?route1-eid :route/from ?from-eid] " +
  "        [?route1-eid :route/to ?mid-eid] " +
  "        [?route1-eid :route/km ?km1] " +
  "        [?route2-eid :route/from ?mid-eid] " +
  "        [?route2-eid :route/to ?to-eid] " +
  "        [?route2-eid :route/km ?km2] " +
  "        [(+ ?km1 ?km2) ?km] " +
  "        [?mid-eid :place/name ?mid-name]]",
  "Paris",
  "Berlin");

Use algorithms for global path search

For unbounded weighted shortest path, use Dijkstra, A*, or another application algorithm. Let Datalevin answer the indexed neighbor query, but let the algorithm own the priority queue and stopping condition. That keeps the database model clear and avoids forcing every graph algorithm into one Datalog query.

4.4 Lineage Through Relationship Nodes

Some graphs are not stored as one obvious edge. For example, doctoral student advisor lineage is traced through dissertations: a person advises a dissertation, and the dissertation points to the student who authored it [4]. The logical edge "advisor advised student" is therefore a derived relation, not a stored attribute.

{:person/name        {:db/valueType :db.type/string}
 :person/advised     {:db/valueType   :db.type/ref
                      :db/cardinality :db.cardinality/many}
 :dissertation/cid   {:db/valueType :db.type/ref}
 :dissertation/univ  {:db/valueType :db.type/string}
 :dissertation/area  {:db/valueType :db.type/string}
 :dissertation/title {:db/valueType :db.type/string}}

Schema academicSchema = Datalevin.schema()
    .attr(":person/name", Schema.attribute()
        .valueType(Schema.ValueType.STRING))
    .attr(":person/advised", Schema.attribute()
        .valueType(Schema.ValueType.REF)
        .cardinality(Schema.Cardinality.MANY))
    .attr(":dissertation/cid", Schema.attribute()
        .valueType(Schema.ValueType.REF))
    .attr(":dissertation/univ", Schema.attribute()
        .valueType(Schema.ValueType.STRING))
    .attr(":dissertation/area", Schema.attribute()
        .valueType(Schema.ValueType.STRING))
    .attr(":dissertation/title", Schema.attribute()
        .valueType(Schema.ValueType.STRING));

academic_schema = {
    ":person/name": {":db/valueType": ":db.type/string"},
    ":person/advised": {":db/valueType": ":db.type/ref",
                        ":db/cardinality": ":db.cardinality/many"},
    ":dissertation/cid": {":db/valueType": ":db.type/ref"},
    ":dissertation/univ": {":db/valueType": ":db.type/string"},
    ":dissertation/area": {":db/valueType": ":db.type/string"},
    ":dissertation/title": {":db/valueType": ":db.type/string"}}

const academicSchema = {
  ":person/name": {":db/valueType": ":db.type/string"},
  ":person/advised": {":db/valueType": ":db.type/ref",
                      ":db/cardinality": ":db.cardinality/many"},
  ":dissertation/cid": {":db/valueType": ":db.type/ref"},
  ":dissertation/univ": {":db/valueType": ":db.type/string"},
  ":dissertation/area": {":db/valueType": ":db.type/string"},
  ":dissertation/title": {":db/valueType": ":db.type/string"}
};

Rules give names to the useful graph relations:

(def academic-rules
  '[[(author ?dissertation-eid ?person-eid)
     [?dissertation-eid :dissertation/cid ?person-eid]]

    [(advised ?advisor-eid ?student-eid)
     [?advisor-eid :person/advised ?dissertation-eid]
     (author ?dissertation-eid ?student-eid)]

    [(academic-ancestor ?ancestor-eid ?student-eid)
     (advised ?ancestor-eid ?student-eid)]

    [(academic-ancestor ?ancestor-eid ?student-eid)
     (advised ?ancestor-eid ?middle-eid)
     (academic-ancestor ?middle-eid ?student-eid)]])

Object academicRules = Datalevin.edn(
    "[[(author ?dissertation-eid ?person-eid) " +
    "  [?dissertation-eid :dissertation/cid ?person-eid]] " +
    " [(advised ?advisor-eid ?student-eid) " +
    "  [?advisor-eid :person/advised ?dissertation-eid] " +
    "  (author ?dissertation-eid ?student-eid)] " +
    " [(academic-ancestor ?ancestor-eid ?student-eid) " +
    "  (advised ?ancestor-eid ?student-eid)] " +
    " [(academic-ancestor ?ancestor-eid ?student-eid) " +
    "  (advised ?ancestor-eid ?middle-eid) " +
    "  (academic-ancestor ?middle-eid ?student-eid)]]");

academic_rules = interop().read_edn(
    '[[(author ?dissertation-eid ?person-eid) '
    '  [?dissertation-eid :dissertation/cid ?person-eid]] '
    ' [(advised ?advisor-eid ?student-eid) '
    '  [?advisor-eid :person/advised ?dissertation-eid] '
    '  (author ?dissertation-eid ?student-eid)] '
    ' [(academic-ancestor ?ancestor-eid ?student-eid) '
    '  (advised ?ancestor-eid ?student-eid)] '
    ' [(academic-ancestor ?ancestor-eid ?student-eid) '
    '  (advised ?ancestor-eid ?middle-eid) '
    '  (academic-ancestor ?middle-eid ?student-eid)]]')

const academicRules = await interop().readEdn(
  "[[(author ?dissertation-eid ?person-eid) " +
  "  [?dissertation-eid :dissertation/cid ?person-eid]] " +
  " [(advised ?advisor-eid ?student-eid) " +
  "  [?advisor-eid :person/advised ?dissertation-eid] " +
  "  (author ?dissertation-eid ?student-eid)] " +
  " [(academic-ancestor ?ancestor-eid ?student-eid) " +
  "  (advised ?ancestor-eid ?student-eid)] " +
  " [(academic-ancestor ?ancestor-eid ?student-eid) " +
  "  (advised ?ancestor-eid ?middle-eid) " +
  "  (academic-ancestor ?middle-eid ?student-eid)]]");

Now "find all academic ancestors of a person" is a graph traversal over a relation that was assembled from several attributes:

(d/q '[:find ?ancestor-name
       :in $ % ?student-name
       :where
       [?student-eid :person/name ?student-name]
       (academic-ancestor ?ancestor-eid ?student-eid)
       [?ancestor-eid :person/name ?ancestor-name]]
     db academic-rules "David Scott Warren")

Object ancestors = conn.query(
    "[:find ?ancestor-name " +
    " :in $ % ?student-name " +
    " :where [?student-eid :person/name ?student-name] " +
    "        (academic-ancestor ?ancestor-eid ?student-eid) " +
    "        [?ancestor-eid :person/name ?ancestor-name]]",
    academicRules,
    "David Scott Warren");

ancestors = conn.query(
    '[:find ?ancestor-name '
    ' :in $ % ?student-name '
    ' :where [?student-eid :person/name ?student-name] '
    '        (academic-ancestor ?ancestor-eid ?student-eid) '
    '        [?ancestor-eid :person/name ?ancestor-name]]',
    academic_rules,
    "David Scott Warren")

const ancestors = await conn.query(
  "[:find ?ancestor-name " +
  " :in $ % ?student-name " +
  " :where [?student-eid :person/name ?student-name] " +
  "        (academic-ancestor ?ancestor-eid ?student-eid) " +
  "        [?ancestor-eid :person/name ?ancestor-name]]",
  academicRules,
  "David Scott Warren");

This is a good pattern when the edge has a first-class domain object behind it. The dissertation is not merely a join artifact; it has title, institution, area, and year facts of its own. Keeping that node visible preserves domain meaning while rules recover the convenient graph relation.

4.5 Type Graphs and Class Derivation

Graph reasoning is not limited to social links or dependency chains. In some cases, entities have concrete :type facts, and rules derive membership in broader classes such as :Student, :Faculty, and :Person [5].

The attributes in this section and the next follow the compact OpenRuleBench/LUBM-style benchmark schemas, so they use names such as :type, :advisor, :par, and :sib. In application schemas, prefer the namespacing convention from Chapter 5, for example :university/type, :student/advisor, :person/parent, or :person/sibling.

(def university-type-rules
  '[[(is-a ?x-eid ?class)
     [?x-eid :type :GraduateStudent]
     [(ground :Student) ?class]]
    [(is-a ?x-eid ?class)
     [?x-eid :type :UndergraduateStudent]
     [(ground :Student) ?class]]
    [(is-a ?x-eid ?class)
     (is-a ?x-eid ?student-class)
     [(= ?student-class :Student)]
     [(ground :Person) ?class]]

    [(is-a ?x-eid ?class)
     [?x-eid :type :FullProfessor]
     [(ground :Professor) ?class]]
    [(is-a ?x-eid ?class)
     [?x-eid :type :AssociateProfessor]
     [(ground :Professor) ?class]]
    [(is-a ?x-eid ?class)
     (is-a ?x-eid ?professor-class)
     [(= ?professor-class :Professor)]
     [(ground :Faculty) ?class]]
    [(is-a ?x-eid ?class)
     (is-a ?x-eid ?faculty-class)
     [(= ?faculty-class :Faculty)]
     [(ground :Person) ?class]]])

Object universityTypeRules = Datalevin.edn(
    "[[(is-a ?x-eid ?class) " +
    "  [?x-eid :type :GraduateStudent] " +
    "  [(ground :Student) ?class]] " +
    " [(is-a ?x-eid ?class) " +
    "  [?x-eid :type :UndergraduateStudent] " +
    "  [(ground :Student) ?class]] " +
    " [(is-a ?x-eid ?class) " +
    "  (is-a ?x-eid ?student-class) " +
    "  [(= ?student-class :Student)] " +
    "  [(ground :Person) ?class]] " +
    " [(is-a ?x-eid ?class) " +
    "  [?x-eid :type :FullProfessor] " +
    "  [(ground :Professor) ?class]] " +
    " [(is-a ?x-eid ?class) " +
    "  [?x-eid :type :AssociateProfessor] " +
    "  [(ground :Professor) ?class]] " +
    " [(is-a ?x-eid ?class) " +
    "  (is-a ?x-eid ?professor-class) " +
    "  [(= ?professor-class :Professor)] " +
    "  [(ground :Faculty) ?class]] " +
    " [(is-a ?x-eid ?class) " +
    "  (is-a ?x-eid ?faculty-class) " +
    "  [(= ?faculty-class :Faculty)] " +
    "  [(ground :Person) ?class]]]");

university_type_rules = interop().read_edn(
    '[[(is-a ?x-eid ?class) '
    '  [?x-eid :type :GraduateStudent] '
    '  [(ground :Student) ?class]] '
    ' [(is-a ?x-eid ?class) '
    '  [?x-eid :type :UndergraduateStudent] '
    '  [(ground :Student) ?class]] '
    ' [(is-a ?x-eid ?class) '
    '  (is-a ?x-eid ?student-class) '
    '  [(= ?student-class :Student)] '
    '  [(ground :Person) ?class]] '
    ' [(is-a ?x-eid ?class) '
    '  [?x-eid :type :FullProfessor] '
    '  [(ground :Professor) ?class]] '
    ' [(is-a ?x-eid ?class) '
    '  [?x-eid :type :AssociateProfessor] '
    '  [(ground :Professor) ?class]] '
    ' [(is-a ?x-eid ?class) '
    '  (is-a ?x-eid ?professor-class) '
    '  [(= ?professor-class :Professor)] '
    '  [(ground :Faculty) ?class]] '
    ' [(is-a ?x-eid ?class) '
    '  (is-a ?x-eid ?faculty-class) '
    '  [(= ?faculty-class :Faculty)] '
    '  [(ground :Person) ?class]]]')

const universityTypeRules = await interop().readEdn(
  "[[(is-a ?x-eid ?class) " +
  "  [?x-eid :type :GraduateStudent] " +
  "  [(ground :Student) ?class]] " +
  " [(is-a ?x-eid ?class) " +
  "  [?x-eid :type :UndergraduateStudent] " +
  "  [(ground :Student) ?class]] " +
  " [(is-a ?x-eid ?class) " +
  "  (is-a ?x-eid ?student-class) " +
  "  [(= ?student-class :Student)] " +
  "  [(ground :Person) ?class]] " +
  " [(is-a ?x-eid ?class) " +
  "  [?x-eid :type :FullProfessor] " +
  "  [(ground :Professor) ?class]] " +
  " [(is-a ?x-eid ?class) " +
  "  [?x-eid :type :AssociateProfessor] " +
  "  [(ground :Professor) ?class]] " +
  " [(is-a ?x-eid ?class) " +
  "  (is-a ?x-eid ?professor-class) " +
  "  [(= ?professor-class :Professor)] " +
  "  [(ground :Faculty) ?class]] " +
  " [(is-a ?x-eid ?class) " +
  "  (is-a ?x-eid ?faculty-class) " +
  "  [(= ?faculty-class :Faculty)] " +
  "  [(ground :Person) ?class]]]");

A query can then ask at the semantic level it cares about:

(d/q '[:find ?student-eid ?advisor-eid
       :in $ %
       :where
       (is-a ?student-eid ?class)
       [(= ?class :Student)]
       [?student-eid :advisor ?advisor-eid]]
     db university-type-rules)

Object advisors = conn.query(
    "[:find ?student-eid ?advisor-eid " +
    " :in $ % " +
    " :where (is-a ?student-eid ?class) " +
    "        [(= ?class :Student)] " +
    "        [?student-eid :advisor ?advisor-eid]]",
    universityTypeRules);

advisors = conn.query(
    '[:find ?student-eid ?advisor-eid '
    ' :in $ % '
    ' :where (is-a ?student-eid ?class) '
    '        [(= ?class :Student)] '
    '        [?student-eid :advisor ?advisor-eid]]',
    university_type_rules)

const advisors = await conn.query(
  "[:find ?student-eid ?advisor-eid " +
  " :in $ % " +
  " :where (is-a ?student-eid ?class) " +
  "        [(= ?class :Student)] " +
  "        [?student-eid :advisor ?advisor-eid]]",
  universityTypeRules);

This does not require Datalevin attributes themselves to become an ontology. The class graph is ordinary application data, and the rules describe how that application wants to interpret it.

4.6 Same-Generation Relations

A second OpenRuleBench-style derived relation is same generation over :par and :sib base relations. This is different from reachability: it derives a relation between pairs of nodes that occupy the same structural level.

(def same-generation-rules
  '[[(same-generation ?x-eid ?y-eid)
     [?x-eid :sib ?y-eid]]
    [(same-generation ?x-eid ?y-eid)
     [?x-eid :par ?z-eid]
     (same-generation ?z-eid ?z1-eid)
     [?y-eid :par ?z1-eid]]])

Object sameGenerationRules = Datalevin.edn(
    "[[(same-generation ?x-eid ?y-eid) " +
    "  [?x-eid :sib ?y-eid]] " +
    " [(same-generation ?x-eid ?y-eid) " +
    "  [?x-eid :par ?z-eid] " +
    "  (same-generation ?z-eid ?z1-eid) " +
    "  [?y-eid :par ?z1-eid]]]");

same_generation_rules = interop().read_edn(
    '[[(same-generation ?x-eid ?y-eid) '
    '  [?x-eid :sib ?y-eid]] '
    ' [(same-generation ?x-eid ?y-eid) '
    '  [?x-eid :par ?z-eid] '
    '  (same-generation ?z-eid ?z1-eid) '
    '  [?y-eid :par ?z1-eid]]]')

const sameGenerationRules = await interop().readEdn(
  "[[(same-generation ?x-eid ?y-eid) " +
  "  [?x-eid :sib ?y-eid]] " +
  " [(same-generation ?x-eid ?y-eid) " +
  "  [?x-eid :par ?z-eid] " +
  "  (same-generation ?z-eid ?z1-eid) " +
  "  [?y-eid :par ?z1-eid]]]");

The base case says that sibling pairs are same-generation. The recursive case says that if ?x-eid has a :par edge to ?z-eid, ?y-eid has a :par edge to ?z1-eid, and ?z-eid and ?z1-eid are same-generation, then ?x-eid and ?y-eid are same-generation. This kind of query is useful for structural comparisons, lineage analysis, and rule-engine tests because the derived relation is about two moving positions in the graph, not one source-to-target path.

5. Example: Finding the Forum for a Message (LDBC-SNB IS6)

The LDBC Social Network Benchmark (LDBC SNB) is an industry standard for evaluating graph databases. It models a social network with people, friendships, forums, posts, comments, likes, tags, organizations, and places [6]. This section examines one real Interactive Short query from the benchmark to show graph traversal in practice.

Query IS6: Given a message, find the forum that contains it and the person who moderates that forum. Because comments are not directly contained in forums, the query traverses to the original post in the thread.

Define a recursive rule to find the root post of any message:

(def root-post-rule
  '[;; base case
    [(root-post ?message-eid ?post-eid)
     [?message-eid :message/isContainedIn _]
     [(ground ?message-eid) ?post-eid]] ; copy the root message eid into ?post-eid

    ;; recursive case
    [(root-post ?message-eid ?post-eid)
     [?message-eid :message/replyOf ?parent-eid]
     (root-post ?parent-eid ?post-eid)]])

Object rootPostRule = Datalevin.edn(
    "[[(root-post ?message-eid ?post-eid) " +
    "  [?message-eid :message/isContainedIn _] " +
    "  [(ground ?message-eid) ?post-eid]] " +
    " [(root-post ?message-eid ?post-eid) " +
    "  [?message-eid :message/replyOf ?parent-eid] " +
    "  (root-post ?parent-eid ?post-eid)]]");

root_post_rule = interop().read_edn(
    '[[(root-post ?message-eid ?post-eid) '
    '  [?message-eid :message/isContainedIn _] '
    '  [(ground ?message-eid) ?post-eid]] '
    ' [(root-post ?message-eid ?post-eid) '
    '  [?message-eid :message/replyOf ?parent-eid] '
    '  (root-post ?parent-eid ?post-eid)]]')

const rootPostRule = await interop().readEdn(
  "[[(root-post ?message-eid ?post-eid) " +
  "  [?message-eid :message/isContainedIn _] " +
  "  [(ground ?message-eid) ?post-eid]] " +
  " [(root-post ?message-eid ?post-eid) " +
  "  [?message-eid :message/replyOf ?parent-eid] " +
  "  (root-post ?parent-eid ?post-eid)]]");

The rule has two branches:

If the message has :message/isContainedIn, it is itself the root post.
Otherwise, follow :message/replyOf recursively until the query reaches the root.

Now the query to find the forum and moderator:

(d/q '[:find ?forum-id ?forum-title ?moderator-id
              ?moderator-first-name ?moderator-last-name
       :in $ % ?message-id            ; $=db, %=rules, ?message-id=input
       :where
       ;; locate the message
       [?message-eid :message/id ?message-id]

       ;; traverse to root post (recursive rule)
       (root-post ?message-eid ?post-eid)

       ;; get forum containing the post
       [?post-eid :message/isContainedIn ?forum-eid]
       [?forum-eid :forum/id ?forum-id]
       [?forum-eid :forum/title ?forum-title]

       ;; get forum moderator
       [?forum-eid :forum/hasModerator ?moderator-eid]
       [?moderator-eid :person/id ?moderator-id]
       [?moderator-eid :person/firstName ?moderator-first-name]
       [?moderator-eid :person/lastName ?moderator-last-name]]
     db root-post-rule message-id)

Object forum = conn.query(
    "[:find ?forum-id ?forum-title ?moderator-id " +
    "       ?moderator-first-name ?moderator-last-name " +
    " :in $ % ?message-id " +
    " :where [?message-eid :message/id ?message-id] " +
    "        (root-post ?message-eid ?post-eid) " +
    "        [?post-eid :message/isContainedIn ?forum-eid] " +
    "        [?forum-eid :forum/id ?forum-id] " +
    "        [?forum-eid :forum/title ?forum-title] " +
    "        [?forum-eid :forum/hasModerator ?moderator-eid] " +
    "        [?moderator-eid :person/id ?moderator-id] " +
    "        [?moderator-eid :person/firstName ?moderator-first-name] " +
    "        [?moderator-eid :person/lastName ?moderator-last-name]]",
    rootPostRule,
    messageId);

forum = conn.query(
    '[:find ?forum-id ?forum-title ?moderator-id '
    '       ?moderator-first-name ?moderator-last-name '
    ' :in $ % ?message-id '
    ' :where [?message-eid :message/id ?message-id] '
    '        (root-post ?message-eid ?post-eid) '
    '        [?post-eid :message/isContainedIn ?forum-eid] '
    '        [?forum-eid :forum/id ?forum-id] '
    '        [?forum-eid :forum/title ?forum-title] '
    '        [?forum-eid :forum/hasModerator ?moderator-eid] '
    '        [?moderator-eid :person/id ?moderator-id] '
    '        [?moderator-eid :person/firstName ?moderator-first-name] '
    '        [?moderator-eid :person/lastName ?moderator-last-name]]',
    root_post_rule,
    message_id)

const forum = await conn.query(
  "[:find ?forum-id ?forum-title ?moderator-id " +
  "       ?moderator-first-name ?moderator-last-name " +
  " :in $ % ?message-id " +
  " :where [?message-eid :message/id ?message-id] " +
  "        (root-post ?message-eid ?post-eid) " +
  "        [?post-eid :message/isContainedIn ?forum-eid] " +
  "        [?forum-eid :forum/id ?forum-id] " +
  "        [?forum-eid :forum/title ?forum-title] " +
  "        [?forum-eid :forum/hasModerator ?moderator-eid] " +
  "        [?moderator-eid :person/id ?moderator-id] " +
  "        [?moderator-eid :person/firstName ?moderator-first-name] " +
  "        [?moderator-eid :person/lastName ?moderator-last-name]]",
  rootPostRule,
  messageId);

This query uses several Datalevin features together:

Recursive traversal: The root-post rule follows reply chains of arbitrary depth.
Graph navigation: Multiple hops from message to post to forum to moderator.
Rule composition: The % parameter passes rules into the query.
Unified schema: All entities use the same attribute-based model.

The Datalevin project includes an unofficial LDBC-SNB SF1 benchmark implementation for both Datalevin and Neo4j [7]. Treat the benchmark as a reproducible, self-published workload observation, not as a general graph database guarantee.

The reported run used LDBC-SNB scale factor 1, approximately 3.2M entities and 17.3M edges, on one 2023 Apple M2 Max machine with 12 cores, 32 GB RAM, a 1 TB SSD, macOS 15.2, OpenJDK 21, and Clojure 1.12.4. Queries were run twice, with the second run reported. Different Neo4j versions, memory settings, indexes, query parameters, hardware, or larger scale factors can change the result.

Under that setup, the main result is that Datalevin is much faster than Neo4j on the Interactive Short queries, including the IS6 query shown above. The exact numbers can change from release to release as Datalevin, Neo4j, JVMs, indexes, and benchmark settings change, so consult the benchmark page for the current table [7]. Likely contributing factors are:

Index locality: Following refs is typically an indexed B+Tree lookup.
Query optimizer: Efficient plans reduce wasted computation.
Semi-naive evaluation: Recursive rules reduce fact re-processing; see Chapter 21.
Magic-set rewrites: Constraints push deep into recursive expansion; see Chapter 21.

5.1 Other LDBC-SNB Graph Questions

LDBC-SNB contains many graph problems beyond plain traversal:

Temporal neighborhoods: find friends or friends-of-friends who produced activity inside a time window, then exclude activity before that window.
Co-occurrence: find tags, topics, or forums that co-occur in posts written by a social neighborhood.
Recommendation: find friends-of-friends who are not direct friends, then rank them by shared interests or interaction evidence.
Referral and expert search: combine social paths, organizations, places, replies, and tag-class descendants into one query.
Trusted paths: enumerate bounded social paths and score them by message interactions along each edge.

These examples all use the same Datalevin building blocks: refs for graph edges, join entities when an edge has facts, rules for reusable derived relations, and not-join when one graph shape must exclude another. The important modeling lesson is that "graph query" often means a mix of topology, time, text, taxonomy, and ranking, and these are all readily represented in Datalevin's native data model.

Summary: Graph Design Principles

Edges are Refs: Use :db.type/ref for relationships between Datalevin entities.
Think Navigation in Both Directions: Forward and reverse lookups both use indexed access paths. The optimizer can choose between them automatically.
Use Rules for Paths: Encapsulate reusable traversal logic in recursive rules.
Preserve Distance When Needed: Bounded rules can return path length as data for ranking, grouping, or filtering.
Use or-join for Branch Shapes: Combine alternative graph patterns when several paths bind the same result.
Use not-join for Exclusion: Express "reachable this way but not that way" with explicit anti-joins.
Use Nodes for Edge Metadata: If an edge needs properties, make the edge an entity.
Normalize for Depth: Deep graph queries are easier to plan when nodes are small and relationships are explicit.
Name Derived Graphs: Use rules when the useful graph relation is assembled from several lower-level facts.
Use Algorithms When Needed: For arbitrary shortest paths, weighted routing, or other global graph algorithms, use Datalevin for indexed neighbor lookup and keep the search policy in application code.

By treating graph shape as part of the normal data model, you can combine navigation, rules, search, and ordinary facts without moving data into a separate graph-only system.

References

[1] Renzo Angles, "The Property Graph Database Model," Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, CEUR Workshop Proceedings 2100, 2018. URL: https://ceur-ws.org/Vol-2100/paper26.pdf.

[2] E. F. Codd, "Further Normalization of the Data Base Relational Model," IBM Research Report RJ909, August 31, 1971. Republished in Randall J. Rustin, ed., Data Base Systems: Courant Computer Science Symposia Series 6, Prentice-Hall, 1972.

[3] Andrew Dennis, "Using Datomic as a Graph Database," Hashrocket, April 10, 2014. URL: https://hashrocket.com/blog/posts/using-datomic-as-a-graph-database.

[4] Datalevin project, "Math Bench," benchmark implementation based on the Mathematics Genealogy Project. URL: https://github.com/datalevin/datalevin/tree/master/benchmarks/math-bench.

[5] Datalevin project, "OpenRuleBench," benchmark implementation including transitive closure, same-generation, and LUBM-style type inference rules. URL: https://github.com/datalevin/datalevin/tree/master/benchmarks/openrulebench.

[6] LDBC, "LDBC Social Network Benchmark (LDBC SNB)," official benchmark overview and links to the SNB workloads, datasets, and specification. URL: https://ldbcouncil.org/benchmarks/snb/.

[7] Datalevin project, "LDBC SNB Benchmark," benchmark writeup and implementation. URL: https://github.com/datalevin/datalevin/tree/master/benchmarks/LDBC-SNB-bench.

User Examples

No examples for this chapter yet.