162 Implementing the Genealogy Example

The genealogy example in the Event Sourcing chapter contains a graph of people and events. A marriage event can occur under both spouses, an event refers back to its spouses, and people refer to parents and children.

This chapter applies the persistent object store described in the preceding chapter. Persistent entity references are encoded as OIDs. The POS maps each OID to an opaque byte sequence, and genealogy deserialisation functions reconstruct the corresponding in-memory object. The representation therefore does not require compiler-placed ownership arenas or serialised memory pointers.

Representation

The following structures illustrate one possible lowering of the logical schema. They describe serialised records rather than a required C++ ABI:

using OID = uint64_t;

struct GenealogySystemRecord
{
    // Person.id is the logical lookup key; the OID names its serialised record.
    btree<PersonId, OID> person;
};

struct PersonRecord
{
    PersonId id;
    string name;
    Gender gender;
    optional<BirthEventRecord> birth;
    optional<DeathEventRecord> death;

    vector<OID> marriage;
    vector<OID> divorce;
    vector<OID> child;
};

struct BirthEventRecord
{
    DateTime datetime;
    optional<string> location;
    optional<OID> mother;
    optional<OID> father;
};

struct DeathEventRecord
{
    DateTime datetime;
    optional<string> location;
};

struct MarriageEventRecord
{
    array<OID, 2> spouse;
    DateTime datetime;
    optional<string> location;
};

struct DivorceEventRecord
{
    array<OID, 2> spouse;
    DateTime datetime;
};

GenealogySystem.person* is represented by a B-tree because Person.id is its declared key. The B-tree maps that logical key to the OID of a person record. The POS stores the serialised PersonRecord bytes under that OID. This separation permits the storage engine to reorganise those bytes without changing the B-tree key or any OIDs stored elsewhere.

Birth and death events are optional and belong to only one person in this schema, so they can be encoded inline in the person record. Mothers, fathers, children, marriages, divorces, and spouses are references to persistent entities and are encoded as OIDs.

The child, marriage, and divorce collections are vectors because they are normally small and are commonly traversed in full. Although a vector has a physical order, the corresponding Predica attributes are set-valued. The implementation must prevent duplicate OIDs, and insertion order has no logical meaning. A sorted vector, B-tree, or another collection can be substituted for an unusual workload without changing the schema.

Logical keys and physical identity

An OID is not a declared Predica key. The two have different purposes:

A physical index can map a canonical relationship-event key to an event OID. Because spouse[2] is set-valued, the two spouse OIDs must first be placed in a canonical order. The pairs {Alice, Bob} and {Bob, Alice} must generate the same index key.

struct RelationshipEventKey
{
    array<OID, 2> spouse;       // Ascending OID order
    DateTime datetime;

    RelationshipEventKey(OID a, OID b, DateTime dt)
        : spouse{min(a, b), max(a, b)}, datetime(dt)
    {
        assert(a != b);
    }

    friend bool operator==(const RelationshipEventKey& a,
                           const RelationshipEventKey& b)
    {
        return tie(a.spouse, a.datetime) == tie(b.spouse, b.datetime);
    }

    friend bool operator<(const RelationshipEventKey& a,
                          const RelationshipEventKey& b)
    {
        return tie(a.spouse, a.datetime) < tie(b.spouse, b.datetime);
    }
};

The assertion represents the cardinality requirement that the spouse set contain two distinct people. Production code reports a constraint violation instead of relying on an assertion. Equality and ordering compare the same canonical fields, so the ordering is suitable for a map or B-tree index.

Shared events

Alice and Bob can both store the OID of one marriage event:

Alice.marriage ──┐
                 ├── OID 8341 ──→ MarriageEventRecord
Bob.marriage ────┘

The serialised payload is stored once. There is no persistent shared_ptr, and the compiler does not have to choose an arena owned by Alice, Bob, or their GenealogySystem. The POS stores one byte sequence under the event OID, while the two person records contain ordinary serialisable OIDs.

The object store is a physical mechanism. Its storing all marriage records does not make GenealogySystem.marriage* a logical base population. GenealogySystem.marriage* remains derived by navigating the people and eliminating duplicate event OIDs. A physical index over relationship events is likewise an access structure rather than an independent source of logical facts.

Sharing and symmetric membership are separate requirements. The existing Person.marriage constraint says that the containing person is one of the event's spouses, but it does not require the other spouse to contain the same event OID. An additional constraint, a derived inverse, or an atomic update operation is needed to maintain that symmetry.

Navigation through the object graph

Once a PersonRecord has been loaded, the representation exposes several useful directions of navigation directly:

• child contains the OIDs of the person's children;
• birth.mother and birth.father contain the OIDs of both parents;
• marriage contains the OIDs of marriage events in which the person participates;
• divorce contains the OIDs of divorce events in which the person participates; and
• each relationship event contains the OIDs of both spouses.

The vectors are normally small, so navigation commonly consists of reading one person record, iterating a short vector, and resolving its OIDs through the POS snapshot. The strings, optional birth and death events, and the vectors themselves are decoded with the person rather than requiring a separate lookup for every in-memory allocation.

Current and previous spouses are reached through the same event graph. Previous spouses are obtained by following marriage-event OIDs and selecting the other spouse recorded by each event. The current spouse is determined by ordering the person's marriage and divorce events by datetime and interpreting the last relationship event. The physical vector order is irrelevant; the ordering is the logical event-time order declared by the query.

Person
├── child[] ──────────────────────────────→ Person
├── birth.mother ─────────────────────────→ Person
├── birth.father ─────────────────────────→ Person
└── marriage[] / divorce[] ──→ Event ──→ spouse[2] ──→ Person

These directions compose. A sibling path follows a parent OID and then that parent's child vector. A grandparent path follows a parent and then another parent. Cousins, descendants, in-laws, and other derived relationships are built from the same small set of typed navigation steps. The compiler therefore begins with known routes through the data rather than having to rediscover every relationship during query planning.

Efficient navigation in both parent-to-child and child-to-parent directions is not free. The child vector and the parent OIDs in the birth event must describe the same relationship, and updates must preserve that constraint. The additional direction consumes storage and update work in the same way that an additional index does. Its benefit is that both common directions become explicit, type-checked access paths.

Wide entities as navigation hubs

In a complex information system it can be entirely appropriate for an entity type to declare one hundred or more attributes. Predica does not treat a wide entity as evidence that its facts should be distributed among unrelated top-level populations. The usual design principle is to place each fact in the most specific domain to which it belongs.

Many such attributes are scalars, optional values, small strings, or OIDs. A serialised entity containing a hundred of them can still be only a few kilobytes, well within the useful I/O granularity discussed in the chapter on chunk size. Reading the entity then obtains a substantial amount of related information with one object-store read and one deserialisation operation.

A wide entity can also act as a navigation hub. Its OID-valued attributes and small collections expose typed routes to many other entities:

                         parent
                           ↑
supplier ← account ← Customer → address → region
                           ↓
                    order[] / contact[]

The compiler knows the type and cardinality of every outgoing route. A query can read the hub once and then follow only the references it needs. Several paths that begin at the same entity can reuse the already deserialised record.

This does not mean that every attribute should always be encoded in one persistent object. A large document, an unbounded collection, or infrequently used data with very different access characteristics may deserve its own OID. The physical boundary should reflect encoded size, update frequency, and access locality rather than an automatic objection to a large number of logical attributes.

A typed object graph is not a generic graph database

This representation is graph-shaped, but it is not a generic property-graph representation made from untyped vertices, edges, labels, and dynamic property maps. The compiler knows the record type at each OID-valued attribute, the field offset after deserialisation, and the cardinality of the relationship. A path such as person.birth.mother does not need to search a generic edge-label index or interpret a property value dynamically.

Nor does a Predica path require the implementation to execute one pointer-like step at a time. Typed OID navigation is attractive for a selective query that visits a small neighbourhood. A query that processes most of the population may instead be compiled into batched OID reads, sequential scans, vectorised operations, or set-oriented joins.

The performance claim is therefore not that graph databases are inherently faster than relational databases. It is that a typed, chunk-local representation avoids unnecessary reconstruction for common entity-centred navigation while retaining enough logical information for the compiler to choose a bulk execution strategy when the workload calls for one.

Contrast with a relational representation

A conventional relational representation is likely to use relations for people, births, relationship events, event spouses, and possibly parent-child links. Navigating several generations or roles then requires many joins. The same Person relation must be renamed for each role, such as person, mother, maternal grandmother, father, child, sibling, and spouse.

For example, finding a person's siblings can require joining a person to a birth record, joining the recorded parents to other birth records, and joining those records back to differently renamed occurrences of Person. Grandparents and cousins add further occurrences and join paths. Indexes can make each individual lookup efficient, but the relational optimiser must still select access methods, choose join orders, estimate intermediate cardinalities, and recognise when different aliases represent repeated navigation through the same relationships.

The contrast becomes stronger in a large, fully normalised, unnested schema. Facts that are local attributes in Predica can be spread across many relations. Partial information can require additional optional-fact relations rather than one locally encoded presence marker. Reconstructing one conceptual entity may therefore require many indexed lookups and joins before navigation to another entity even begins.

For workloads centred on selective entity access and local navigation, a direct physical mapping of that schema often has worse locality than reading a chunk-sized hub object and following its OIDs. A relational implementation can close or reverse the gap with clustered storage, covering indexes, materialised views, column groups, bulk columnar execution, or deliberate denormalisation. Those are valid physical optimisations; several work by recovering or materialising locality that the Predica type structure already makes explicit, while bulk execution can be intrinsically better for scans over much of the population.

The object representation does not make every genealogy query constant-time. Recursive ancestor and descendant queries can visit large parts of the graph, OID resolution can require I/O, and indexes or cached derived relationships may still be valuable. Its advantage is that common relationship directions are already embodied by typed OID references and local collections. Query implementation can follow those routes directly or batch them into set-oriented work, leaving the optimiser to concentrate on genuinely set-valued choices, filtering, ordering, cardinality, and I/O planning.

Lifetime in the genealogy database

The database catalog contains the OID of each named GenealogySystemRecord. That record reaches person records through its B-tree, people reach other people and relationship events through their OID fields, and relationship events refer back to their spouses. The genealogy object layer traces this graph using the record-layout metadata generated by the compiler and reports live OIDs to the POS.

database catalog
      ↓
GenealogySystemRecord
      ↓
PersonRecord
  ↙       ↘
Person    RelationshipEvent

The cycles between people and relationship events do not require special ownership rules. If an entire genealogy system becomes unreachable from the catalog, tracing can identify its unreachable component. If an individual event becomes unreachable, the object layer can remove its weak index entries and mark its OID dead. The POS can reclaim its obsolete byte-sequence versions after no transaction snapshot can still observe them.

Event retention remains an application policy. Audit or temporal requirements may keep committed birth, death, marriage, and divorce events even after ordinary application references disappear. Reachability determines which objects could be collected; the retention policy determines which historical events may actually be deleted.

Generated implementation

For this schema the compiler generates serialisation and deserialisation functions for the records above, schema-version handling, tracing metadata for their OID fields, comparison code for the declared keys, and navigation code that reads referenced byte sequences and reconstructs objects. The POS supplies OID allocation, stream access, partition actors, transactions, snapshot visibility, and safe reclamation of obsolete versions. Neither component needs to infer a person-owned, event-owned, or system-owned arena.