DEV Community: Oliver

Building a vector database sidecar for semantic search & entity resolution

Oliver — Wed, 21 Jun 2023 10:23:17 +0000

Vector databases are currently all the rage in the tech world, and it isn't just hype. Vector search has become ever more critical due to artificial intelligence advances which make use of vector embeddings. These vector embeddings are vector representations of word embeddings, sentences, or documents that provide semantic similarity for semantically close inputs by simply looking at a distance metric between the vectors.

The canonical example from word2vec in which the embedding of the word "king" was very near the resulting vector from the vectors of the words "queen", "man", and "woman" when arranged in the following formula:

    king - man + woman ≈ queen

The fact that this works has always seemed amazing to me, but it works even for fairly large documents provided our embedding space is of sufficiently high dimension. With modern deep learning methods, you can get excellent embeddings of complex documents.

For TerminusDB we needed a way to leverage these sorts of embeddings for the following tasks that our users have asked for:

Full-text search
Entity resolution (finding other documents which are likely the same for deduplication)
Similarity search (for related content or for recommender systems)
Clustering

We decided to prototype using OpenAI's embeddings, but in order to get the rest of the features we required a vector database.

We needed a few unusual features, including the ability to do incremental indexing, and the ability to index the basis of commits, so we know precisely what commit an index applies to. This allows us to put indexing into our CI workflows.

A versioned open-source vector database doesn't exist in the wild. So we wrote one!

Writing a vector database

A vector database is a store of vectors with the ability to compare any two vectors using some metric. The metric can be a lot of different things such as Euclidean distance, Cosine similarity, Taxicab geometry, or really anything which obeys the triangle inequality rules required to define a metric space.

In order to make this fast, you need to have some sort of indexing structure to quickly find candidates that are already close for comparison. Otherwise, many operations will need to compare with every single thing in the database, every time.

There are many approaches to indexing vector spaces, but we went with the HNSW (Hierarchical Navigable Small World) graph. See Malkov and Yashunin. HNSW is easy to understand and provides good performance in both low and high dimensions, so is flexible. Most importantly there is a very clear open-source implementation that we found - HNSW for Rust Computer Vision.

Storing the vectors

Vectors are stored in a domain. This helps to separate different vector stores that do not need to describe the same vectors. For TerminusDB we have many different commits that all pertain to the same vectors, so it's important that we put them all into the same domain.

            Page
            0            1         2...
            ———————————————————————
Vectors:   | 0 [......]  2 [......]
           | 1 [......]  3 [......]

The vector store is page based, where each buffer is designed to map cleanly to the operating system pages but fit the vectors we use closely. We assign each vector an index and then we can map from the index to the appropriate page and offset.

Inside the HNSW index, we refer to a LoadedVec. This ensures that the page lives in a buffer, currently loaded so we can perform our metric comparisons on the vectors of interest.

As soon as the last LoadedVec drops from a buffer, the buffer can be added back into a buffer pool to be used to load a new page.

Creating a versioned index

We build an HNSW structure for each (domain + commit) pair. If starting a new index, we start with an empty HNSW. If starting an incremental index from a previous commit, we load the old HNSW from the previous commit and then begin our indexing operations.

What is new versus what is old is all kept in TerminusDB, which knows how to find changes between commits and can submit them to the vector database indexer. The indexer only needs to know the operations it is being asked to perform (i.e. Insert, Delete, Replace).

We maintain the indexes themselves in an LRU pool that allows us to load on demand or use a cache if the index is already in memory. Since we only perform destructive operations at commits, this caching is always coherent.

When we save the index, we serialize the structure with the raw vector index as a stand-in for the LoadedVec which helps to keep the index small.

In the future, we would like to use some of the tricks we have learned in TerminusDB to keep layers of an index around, so new layers can be added without requiring each incremental index to add a duplicate when serializing. However, the indexes have proved small enough compared to the vectors we are storing that it has not mattered much.

NOTE: While we currently do incremental indexing, we have yet to implement the delete and replace operations (there are only so many hours in a week!). I've read the literature on HNSW and it seems that it is not yet well described.

We have a design for the delete and replace operations that we think will work well with HNSW and wanted to explain in case any technical people have ideas:

If we are in an upper layer of the HNSW, then simply ignore the deletion - it should not matter much as most vectors are not in upper layers, and ones that are, are only for navigation
If we are in the zero layer but not in an above layer, delete the node from the index, while trying to replace links between all neighbors of the deleted link according to closeness.
If we are in the zero layer but also above, mark the node as deleted, and use it for navigation but do not store this node in the candidate pool.

Finding embeddings

We use OpenAI to define our embeddings, and after an indexing request is made to TerminusDB, we feed each of the documents to OpenAI which returns lists of float vectors in JSON.

It turns out that the embeddings are quite sensitive to context. We tried initially just submitting TerminusDB JSON documents and the results were not fantastic.

However, we found that if we define a GraphQL query + Handlebars template, we can create very high-quality embeddings. For People in Star Wars, this pair, which is defined in our schema, looks like this:

{
    "embedding": {
        "query": "query($id: ID){ People(id : $id) { birth_year, created, desc, edited, eye_color, gender, hair_colors, height, homeworld { label }, label, mass, skin_colors, species { label }, url } }",
        "template": "The person's name is {{label}}.{{#if desc}} They are described with the following synopsis: {{#each desc}} *{{this}} {{/each}}.{{/if}}{{#if gender}} Their gender is {{gender}}.{{/if}}{{#if hair_colors}} They have the following hair colours: {{hair_colors}}.{{/if}}{{#if mass}} They have a mass of {{mass}}.{{/if}}{{#if skin_colors}} Their skin colours are {{skin_colors}}.{{/if}}{{#if species}} Their species is {{species.label}}.{{/if}}{{#if homeworld}} Their homeworld is {{homeworld.label}}.{{/if}}"
    }
}

The meaning of each field in the People object is rendered as text which helps OpenAI understand what we mean, providing much better semantics.

Ultimately it would be nice if we could guess these sentences from a combination of our schema documentation and the schema structure, which is probably also possible using AI chat! But for now, this works brilliantly and does not require much technical sophistication.

Indexing Star Wars

So what happens when we actually run this thing? Well, we tried it out on our Star Wars data product to see what would happen.

First, we fire off an index request, and our indexer obtains the information from TerminusDB:

curl 'localhost:8080/index?commit=o2uq7k1mrun1vp4urktmw55962vlpto&domain=admin/star_wars'

This returns with a task-id which we can use to poll an endpoint for completion.

The index file and vector files for the domain admin/star_wars and the commit o2uq7k1mrun1vp4urktmw55962vlpto come out as:

admin%2Fstar_wars@o2uq7k1mrun1vp4urktmw55962vlpto.hnsw

and

admin%2Fstar_wars.vecs

We can now ask the semantic index server about our documents at the specified commit.

curl 'localhost:8080/search?commit=o2uq7k1mrun1vp4urktmw55962vlpto&domain=admin/star_wars' -d "Who are the squid people"

We get back a number of results as JSON which look like this:

[{"id":"terminusdb:///star-wars/Species/8","distance":0.09396297}, ...]

But what is the embedding string we used to produce this result? This is how the text rendered for the Species/8 id:

"The species name is Mon Calamari. They have the following hair colours: 
none. Their skin colours are red, blue, brown, magenta. They speak the 
Mon Calamarian language."

Amazing! Notice that it never says squid anywhere! There is some pretty amazing work being done by our embeddings here.

Let's have another go:

curl 'localhost:8080/search?commit=o2uq7k1mrun1vp4urktmw55962vlpto&domain=admin/star_wars' -d "Wise old man"

"The person's name is Yoda. They are described with the following synopsis:
Yoda is a fictional character in the Star Wars franchise created by George 
Lucas, first appearing in the 1980 film The Empire Strikes Back. In the 
original films, he trains Luke Skywalker to fight against the Galactic 
Empire. In the prequel films, he serves as the Grand Master of the Jedi 
Order and as a high-ranking general of Clone Troopers in the Clone Wars. 
Following his death in Return of the Jedi at the age of 900, Yoda was the 
oldest living character in the Star Wars franchise in canon, until the 
introduction of Maz Kanata in Star Wars: The Force Awakens. Their gender 
is male. They have the following hair colours: white. They have a mass of 
17. Their skin colours are green."

Incredible! While we do say "oldest" in the text, we don't say "wise" or "man"!

I hope you can see how this could be helpful for you in getting high-quality semantic indexing of your data!

Conclusion

We have also added endpoints to find neighboring documents and to find duplicates that search the entire corpus. The latter was used on some benchmarks and has performed admirably. We hope to show the results of these experiments here soon.

While there are really great vector databases out there in the wild, such as Pinecone, we want to have a sidecar that integrates well with TerminusDB and which can be used for less technical users who care about content primarily and are not going to be spinning up their own vector database.

We are really excited about the potential of this VectorLink, and would love people to have a look at what we have so far! Please forgive us a bit for the relatively sparse error handling. We're working furiously on it!

Update - July 2023

We're pleased to let you know that VectorLink is now available in TerminusCMS. Here are some useful links -

Schema Migration for Graph Databases

Oliver — Tue, 16 May 2023 13:24:52 +0000

Data is always changing – that’s why we have databases in the first place! And it is not just the content that changes, but also the shape of the data.

I spend a lot of time thinking about change management for data – how to make change requests with approval workflows function smoothly, allowing users to update their content and see what it would look like in practice before putting their data into production.

But part of the data lifecycle is managing these changes to the data model itself.

Schema Migration in Graph Databases

In a normal RDBMS there is a command language of “schema” operations that can be performed. You can add or drop tables, add or drop foreign keys, and add or drop columns from your tables.

Similar things are needed in a graph database, where you will need to add and drop edges in the graph, drop node types, add new node types, and alter keys.

However, when it comes to change management with branches and merges, things get a little bit trickier. To make things work smoothly, we need to keep track of how we got where we are.

Schema Migrations as First-Class Citizens

In the latest version of TerminusDB, we have added tracking of schema migration to each commit. This schema migration information can be used to ensure that branches can be made comparable so that we can do change requests between them.

In addition, this will later allow us to have model products that can be updated in ways that downstream users of the model products can track the schema alterations without having to figure out how to alter their data.

Weakening and Strengthening of Schemas

We can split the kinds of schema changes into two types: weakening and strengthening.

A weakening operation is backward compatible. It changes the schema in such a way that it can not invalidate data that already exists, and does not require any change to be made to existing data.

In an SQL world this might be something like adding a new table, or adding a nullable column to a table.

In TerminusDB it means operations such as adding optional or set properties to a class, or adding new classes, or extending an enum with new values.

One additional interesting point about these operations is that the operations can be inferred. We can guess from the addition of a new schema document, or update of a schema document that it is a weakening operation, which means you don’t have to explicitly migrate your schema, but can just edit the schema directly.

Weakening Inference

So how might we infer a schema migration? Let’s demonstrate with the command line tool.

terminusdb db create admin/m
echo '{ "@type" : "Class", "@id" : "A", "a": "xsd:string" }' | ./terminusdb doc insert admin/m -g schema

We have created a new database (called m), and added one type of class A to the schema.

If we look at the log of this (with the verbose flag) we can see the inferred migration reported.

terminusdb log admin/m -v

You’ll get something along the lines of:

wrhzet2rzenaiud9dc7nw03gbgwfsof
--------------------------------
Date: 2023-04-21T11:24:49+00:00
Author: admin
Message: cli: document insert
Migration:
[
    {
    "@type":"CreateClass",
    "class_document": {"@id":"A", "@type":"Class", "a":"xsd:string"}
    }
]

The migration operation to obtain this schema has been inferred.

In addition we can make a slightly more complex change to the schema which is also a weakening, such as:

echo '{ "@type" : "Class", "@id" : "A", "a" : "xsd:string", "b" : { "@type" : "Optional", "@class" : "xsd:boolean" }}' | terminusdb doc replace admin/m -g schema

The most recent commit is given from the command:

terminusdb log admin/m -v -c 1

It will now be along the lines of:

cezsjyywg7o1r2f1fj6otvod5ka6zqa
--------------------------------
Date: 2023-04-21T11:26:35+00:00
Author: admin
Message: cli: document replace
Migration:
[
    {
    "@type":"CreateClassProperty",
    "class":"A",
    "property":"b",
    "type": {"@class":"xsd:boolean", "@type":"Optional"}
    }
]

This migration operation tells the system that we updated the class A with a weakening operation.

Strengthening operations are also possible implicitly using inference but we have not exposed this feature yet as it is still experimental (it can potentially change your instance data!)

Explicit Migration

It is also possible to perform explicit migrations, whether strengthening or weakening, by stating them explicitly through the API or via the CLI.

First, lets add a bit of data to illustrate.

echo '{ "a" : "foo", "b": true }' | terminusdb doc insert admin/m

This is now legal because of our above alterations which introduced the b property.

Now, to add a new required property c to our class A which is an integer, we can write the following:

terminusdb migration admin/m --operations '[{"@type" : "CreateClassProperty", "class" : "A", "property" : "c", "type" : "xsd:integer", "default" : 0 }]'

This returns:

{"instance_operations":1, "schema_operations":1}

Meaning that we changed the data in the database.

To see this we can get the documents back out:

terminusdb doc get admin/m

Which returns:

{"@id":"A/86b5201b5e907ad916ed650b7656828a8f89bea12edf50ecfd341cd290194695","@type":"A","a":"foo","b":true,"c":"0"}

With a new default value of 0 (represented as a string, unfortunately, since it is in fact an unbounded integer that causes problems with many programming languages if not represented as a string).

Targeting a Migration

This is pretty great in itself as we can migrate the shape of our data even when we have instance data, but it’s especially important when doing change-request-type workflows.

For instance, if I branch the database now (branching with an implicit base of main):

terminusdb branch create admin/m/local/branch/other

I can now update the main branch again as follows:

echo '{ "@type" : "Class", "@id" : "B", "b": "xsd:string" }' | ./terminusdb doc insert admin/m -g schema

Now my other branch has difficulties comparing with the main branch since the schema is not symmetric.

To alleviate this problem I can simply target the schema of the branch in main by writing:

terminusdb migration admin/m/local/branch/other -t admin/m

Now if I look at the schema, I’ll see that it has been made symmetric, including adding default values on a required property!

terminusdb doc get admin/m/local/branch/other

Returning:

{"@id":"A/86b5201b5e907ad916ed650b7656828a8f89bea12edf50ecfd341cd290194695","@type":"A","a":"foo","b":true,"c":"0"}

Conclusion

Of course this requires that we have migrations the entire way along, so we’ll be adding a mode that forces all schema updates (via the document interface or otherwise) to have a valid migration, or throw an error.

And for model products that are meant to be imported as schema components for other data products, this should also be required.

However if you keep to explicit migrations for schema changes, or restrict to weakening operations, you should always be able to move your branches along with you.

Hope you enjoy the new-found model flexibility!

Stories from over yonder

Oliver — Tue, 16 May 2023 13:14:25 +0000

We don't post all of our blogs on Dev.to, mainly because we're a small team and it's tough to create original content for lots of different sites. I thought I'd provide a quick overview of what we've posted recently over on our blog.

Reframing Data Strategy: The Era of Quality Data - Unlocking Success Through Prioritizing Accuracy

Synopsis: Move beyond the hype of "big data" and embrace the paradigm shift towards prioritizing quality over quantity. This insightful article sheds light on the paramount importance of good data and its impact on businesses. Discover why accuracy, consistency, relevance, and timeliness are the cornerstones of good data, enabling reliable decision-making. Explore the pitfalls of relying solely on big data, including complexity, data gaps, and biased analysis. The article advocates for a transformative mindset that places a premium on quality data, urging business leaders to proactively align their strategies with this new approach. By fostering meaningful dialogue between data producers and consumers, organizations can ensure data aligns with business objectives. Embracing quality data empowers businesses to unleash the true potential of their data, enabling informed and impactful decisions. Join the movement and make quality data the cornerstone of your organization's success.

Good data, not big data

Redefining Collaboration in Database Management: Unleashing the Potential of TerminusCMS

Synopsis: Experience the game-changing capabilities of TerminusCMS as it redefines the landscape of database collaboration. This article unveils the cutting-edge features that empower developers and end-users alike, placing flexibility and collaboration at the forefront. With the revolutionary integration of branches and change request workflows, data and content changes become a seamless process, involving humans at every step. TerminusCMS revolutionizes supply chain management, ensuring regulatory compliance, empowering research teams, and supercharging application features. Whether you're a developer, compliance professional, researcher, or app creator, TerminusCMS offers a transformative platform for accurate, reproducible, and collaborative data management. Embrace the future of database collaboration and witness the remarkable impact TerminusCMS can have on your work.

Database collaboration

Revolutionize SBOM Management with Headless CMS

Synopsis: Dive into the world of headless content management systems (CMS) and unlock the true power of managing your software bill of materials (SBOM). This captivating article delves into the crucial role SBOMs play in businesses, from compliance and risk management to supply chain relationships and product development. Discover how a headless CMS empowers you to streamline SBOM processes by providing a centralized platform, automated data collection, task management applications, and exceptional customer service support. With a special focus on TerminusCMS, explore its game-changing features, including its graph data structure, flexible schema modeling, change request workflows, and dynamic query capabilities. By embracing SBOMs and harnessing the advantages they offer in terms of security, compliance, and innovation, your business will soar to unprecedented heights.

Manage your SBOM with Headless CMS

Elevate Your Data Management: Empowering Business Critical Functions with Data Layer Content Moderation

Synopsis: Embark on a transformative journey with TerminusCMS, an innovative content management system that revolutionizes data and content moderation. This captivating blog uncovers the pivotal role of change request workflows at the data layer and their profound impact on critical business functions such as forecasting, product testing, and regulatory compliance. Immerse yourself in the advanced capabilities of TerminusCMS, including immutable data, version control, and collaborative features, which guarantee unparalleled accuracy, accountability, and transparency. Gain insights into the crucial role of content moderation at the data layer, fostering data integrity, optimizing workflows, and ensuring compliance with regulations.

Content Moderation at the Data Layer

How we built a low-code application for straight-through processing of insurance claims in a week

Oliver — Wed, 26 Apr 2023 09:11:22 +0000

Can you build an app for straight through processing of insurance claims, including UI for necessary human interventions in a week?

The answer, surprisingly, is yes.

Of course, with software, it’s very hard to tell how long code takes unless you try. So we built one. The secret to our success was twofold:

We had a semantic description of our domain, making the building of the UI almost completely automatic, and enabling logical description of entities
We used a declarative logical description of the states of the insurance claim

So both the core logic of transitioning an insurance policy through states and the UI fell out of careful modeling of the problem domain. This is what declarative software design is supposed to do for us, and it worked so well that it even surprised me!

Best of all, it’s very easy to customize, because it is a very low-code application, with most of the logic in the description. I expect this approach can be used in a lot of FinTech applications and would love to have the opportunity to try it.

Demo App

We focused only on one use case: life insurance policies to demonstrate straight through processing of insurance claims with human intervention. Of course, our app doesn’t do everything that you might want in a fully-fledged insurance claims application.

However, it does do a surprising amount considering the time it took to put together, and with a bit of elbow grease it seems to me it could easily be a product in itself, and it could easily be grown out to deal with a much larger assortment of claims.

Modeling Insurance Claims

The first port of call is to model the objects of interest in claims processing. This is the semantic part that is going to drive the rest of the application.

Our demo app has the following elements:

Countries
Claim Cases
Policies
Beneficiaries
Death Certificates

It also has a couple of enumerated types:

Refunds (Sum Assured, Premium or Denied)
Cause of Death (Natural, Manslaughter, Murder, Accidental and Suicide)

The entire claim case model can be seen here.

Right out of the box, with this in place, we can get a default UI that looks like this:

This is what TerminusCMS gives us just by modeling our application domain. A nearly fully functional UI, which can then be customized quickly by passing JavaScript configuration objects in React.

Adding Declarative States

To make our straight-through processing system, we model the states of our system based on whether the object we are interested in meets certain constraints. That way the state of the object is defined by the content of the object, and changing the content of the object (for instance, supplying more information, or correcting information) will change it to a new state.

Let us take a concrete example:

{ "@comment": "Claim is eligible for a premium refund",
  "@given": [
      { "death_certificate_for_claim": {
          "date_of_death": {
              "@var": "DateOfDeath"
          }
      },
        "policy_of_claim": {
            "moratorium_end": {
                "@var": "MoratoriumEnd"
            },
            "moratorium_start": {
                "@var": "MoratoriumStart"
            }
        }
      }
  ],
  "@has": {
      "@ge": {
          "@var": "MoratoriumStart"
      },
      "@le": {
          "@var": "MoratoriumEnd"
      },
      "@with": "DateOfDeath"
  },
  "@noneOf": [
      "ReferralForAssessment",
      "ReferralForService",
      "ClaimClosed"
  ],
  "@on": "ClaimCase",
  "_id": "PremiumRefund",
  "_type": "Restriction"
}

What we are doing here is defining what claims are immediately eligible for a premium refund. The conditions which place a claim in this state are described declaratively. This is a business logical description that helps us move to the appropriate state automatically.

First, we must check to find the death date associated with the claims case, then we look for the start and end of the moratorium written into the policy.

Next, we check a condition, is the date of death between the start of the moratorium, and the end? If so, the person is only eligible for the refund of premiums made to date, and can not avail of the sum assured.

In addition, however, we have to check that the status of the record is safe in the sense that all necessary associated information has matched the conditions which place it into a referral for assessment or referral for service. These are conditions such as an unusual cause of death (perhaps murder), or failure for the death certificate to match policy details.

All of these other conditions are likewise written declaratively (as you can see from the above schema).

We also want to exclude those records for which the claim has already been closed (either due to a prior payout, or rejection).

Straight Through Processing Actions and the UI

With these definitions which incorporate the relevant business logic, we can turn it into a fully-fledged application. We build React components automatically and expose a rich GraphQL interface that allows you to pull objects which meet a given restriction status easily.

If a premium payout status is reached, for instance, then we can have an automated procedure for payment, which then places the object in a closed status if successful. In fact, there may be many automatic procedures that take place, each moving the object into a further state which can ultimately result in the closure of the claim case or movement into some human interaction.

If an insurance claim is referred for servicing or some other state that requires human intervention, it will appear in a dashboard automatically.

The dashboard only refers to the state of the claim it would like to retrieve, in this case, referred for servicing. All of the query logic is entirely in the model. This means that as business rules change, nothing needs to change about the UI. Changes to the UI are only required when new insurance claim states are defined, saving time and reducing complexity.

When a user views a particular case state in the dashboard, we can tell the reason that it ended up in this state. This helps the human operator understand what needs to be altered in order to place the claim in a new state that no longer requires servicing.

Conclusion

Declarative domain modeling is exceptionally powerful as a means of writing low-code applications and implementing rules-driven functionality such as straight through processing of insurance claims.

Low code brings big benefits itself. It means easier maintenance, faster development time and more flexible business logic. This reduces costs of development and maintenance and improves agility, which is extremely important to respond to customer needs and competitors.

Messing around with GraphQL queries with a critical asset management dataset

Oliver — Tue, 18 Apr 2023 13:40:04 +0000

I wanted to show the simplicity of TerminusCMS’ GraphQL query ability and the work our dev team has achieved to make queries lightning-fast and very simple to construct.

I would consider myself technically inept, so anyone with a modicum of technical skill will breeze through these examples.

The example I’m using is the CAMS (Critical Asset Management System) project that you can clone from the TerminusCMS dashboard. It has a schema and dummy data based around the Caribbean Island of Dominica. It is a copy of the backend for the critical asset management system project we worked on with the UN and ARISE.

The examples use assets and the relationships between them. They have dependency relationships between them. It also looks at the asset owner. Here’s a rough diagram showing the focus.

Hypothetically, I’m a dev and I want to build an application for first responders to communicate asset failures.

Firstly, I want to find all the critical assets associated with my region’s communications.

query {
  Asset(filter: {assetType: {eq: Communications}}) {
    asset_identifier
  }
}

Here I’ve filtered by assetType using equals communications. Read our docs for more information on filtering. The above query produces these JSON results -

{
  "data": {
    "Asset": [
      {
        "asset_identifier": "Communication tower near Good Hope "
      },
      {
        "asset_identifier": "Petro Caribe Radio Tower"
      }
    ]
  }
}

You can filter and display any document property. The GraphQL schema for properties, filters and limits is constructed automatically from your project's schema. This includes paths too, so you can establish the relationships in your query.

For example, I now want to see which assets are dependent on my comms assets.

query {
  Asset(filter: {assetType: {eq: Communications}}) {
    asset_identifier
     _depends_on_of_DependencyRelation{
      dependent {
        name
      }
    }
  }
}

Using Ctrl C, I can get a list of document classes to specify, this includes the link properties that create the edges in the graph. Here’s a look at the schema builder UI showing the asset document class — you can see it has dependency relationships as properties -

The above query produces a list of your comms assets with those that are dependent on them -

{
  "data": {
    "Asset": [
      {
        "asset_identifier": "Communication tower near Good Hope ",
        "_depends_on_of_DependencyRelation": [
          {
            "dependent": {
              "name": "Mahaut River Health Centre"
            }
          },
          {
            "dependent": {
              "name": "La Plaine Police Station"
            }
          },
          {
            "dependent": {
              "name": "La Plaine Police Station"
            }
          },
          {
            "dependent": {
              "name": "Colihaut Primary School"
            }
          }
        ]
      },
      {
        "asset_identifier": "Petro Caribe Radio Tower",
        "_depends_on_of_DependencyRelation": [
          {
            "dependent": {
              "name": "Princess Margaret Hospital "
            }
          },
          {
            "dependent": {
              "name": "Castle bruce Electrical substation"
            }
          },
          {
            "dependent": {
              "name": "Portsmouth Town Council"
            }
          }
        ]
      }
    ]
  }
}

In order to make my application useful. I need to include the owners of each asset so first responders can relay important information.

The owner document class is added as a link property to an asset and it is specified as a set to allow more than one owner.

I simply add the owner document class and the contact properties I want to see. Again I can press Ctrl C to get a list of properties, or use the handy autofill.

query {
  Asset(filter: {assetType: {eq: Communications}}) {
    asset_identifier
    _depends_on_of_DependencyRelation {
      dependent {
        name
        owner {
          name
          last_name
          email_address
          phone_number
        }
      }
    }
  }
}

This gets me back the assets dependent on my comms assets and the names and contact details for all those that need to be communicated to -

{
  "data": {
    "Asset": [
      {
        "asset_identifier": "Communication tower near Good Hope ",
        "_depends_on_of_DependencyRelation": [
          {
            "dependent": {
              "name": "Mahaut River Health Centre",
              "owner": [
                {
                  "name": "Sue",
                  "last_name": "Sandez",
                  "email_address": "sue@dashcom.com",
                  "phone_number": "21358394"
                }
              ]
            }
          },
          {
            "dependent": {
              "name": "La Plaine Police Station",
              "owner": [
                {
                  "name": "Amanda",
                  "last_name": "Christensen",
                  "email_address": "amanda@vlink.com",
                  "phone_number": "324987392"
                }
              ]
            }
          },
          {
            "dependent": {
              "name": "La Plaine Police Station",
              "owner": [
                {
                  "name": "Amanda",
                  "last_name": "Christensen",
                  "email_address": "amanda@vlink.com",
                  "phone_number": "324987392"
                }
              ]
            }
          },
          {
            "dependent": {
              "name": "Colihaut Primary School",
              "owner": [
                {
                  "name": "Ted",
                  "last_name": "Bigs",
                  "email_address": "tbigs@bbn.org",
                  "phone_number": "2344859"
                }
              ]
            }
          }
        ]
      },
      {
        "asset_identifier": "Petro Caribe Radio Tower",
        "_depends_on_of_DependencyRelation": [
          {
            "dependent": {
              "name": "Princess Margaret Hospital ",
              "owner": [
                {
                  "name": "Ted",
                  "last_name": "Bigs",
                  "email_address": "tbigs@bbn.org",
                  "phone_number": "2344859"
                }
              ]
            }
          },
          {
            "dependent": {
              "name": "Castle bruce Electrical substation",
              "owner": [
                {
                  "name": "Eliza",
                  "last_name": "Albert",
                  "email_address": "eliza@vvv.org",
                  "phone_number": "32449234"
                }
              ]
            }
          },
          {
            "dependent": {
              "name": "Portsmouth Town Council",
              "owner": [
                {
                  "name": "Oliver",
                  "last_name": "Little",
                  "email_address": "olittle@comms.com",
                  "phone_number": "12384957684"
                }
              ]
            }
          }
        ]
      }
    ]
  }
}

Have a go yourself and sign up for TerminusCMS for free. Clone a project and see how easy it is to query using GraphQL.

The Content Revolution

Oliver — Thu, 16 Feb 2023 15:49:14 +0000

Building the Headless Content Management System of the Future

Myself and team just finished preparing our new cloud headless CMS offering, TerminusCMS. It feels like a pretty long journey getting here, but we feel like we have the basis of a truly next-generation CMS for devs.

We live in the information age, and unsurprisingly that means a lot of what we do with computers is about marshalling, finding or transforming data.

Each domain which IT serves involves creating digital assets which record information to be enriched, served up, or curated over time. And much of this data is highly interconnected.

Moreover, it is being loaded, curated and enriched by a combination of humans and computers. The entire business is fundamentally cybernetic. We need knowledge graph management systems which include easy-to-use interfaces for human data entry, review and curation at the same time that they facilitate the same from a computer. These systems have to be scalable and distributed.

And as AI grows in importance, the importance of well-structured data will simply grow. AIs perform better when fed well-structured data and they will be able to help us create the search engines of the future. It will make expert systems something more like asking an expert, and less like a tool for an expert.

Our infrastructure for creating and managing the data world is still young, so the question is, how is it going to change? We have databases, including graph databases, and we have headless content management systems, what more could we ask for?

As a practitioner in managing data, I developed strong opinions on the matter and made some big bets on what I thought was important by making TerminusDB.

What is currently missing in our data management solutions? I think it essentially boils down to the need for:

Continuous integration / Continuous development (CI/CD): data is always in a pipeline.
Document Graph structured content: Content always relates to other content and we need to manage content with both people and machines.
Discoverability: We require powerful query and search (Drupal / WordPress aren’t going to cut it)

None of these ideas are completely new. In fact, all of them are widely used in their respective domains, but they aren’t currently being used together for data management.

To hit these functional requirements we need a headless, schema-driven knowledge graph management system with external transactions for CI/CD… right, what does that mean… Let’s unpack that…

CI/CD for Data

Transactions in databases tend to be focused around the central server. This makes a lot of sense when you want high-performance ACID transactions and a single source of truth.

However, there are more kinds of transactions than the text-book “decrement a bank account” variety. Content management by humans is often more natural to think about with transactions which could be open for a long time.

In software engineering, we already do this with code. Change requests, ala Git, are external transactions. What do I mean by external transaction? It’s a transaction id which associates a state, which can be used with many individuals or microservices to perform a pipeline of updates on the request branch – and which finally completes only after everything is in order.

To do this we need a state which sticks around and which can refer to other states. We need a graph of states and their relationships. Basically, we need a git-like architecture for our database.

A typical workflow with a change request might be:

(I’ll use cN to refer to the names of individual commits)

1. I branch from main with a change request branch which I name `dev`. Initially we share a commit `c0`.

       c0
main – ∘
       |
      dev

I make some commits to this branch, adding data by human data entry with a front end I’ve designed to make data entry easy for my problem domain.

       c0
main – ∘
        ↘
  dev –  ∘
         cd1

3. A computer programme sees this change request update and enriches my added documents, by performing named entity recognition on the text, enhancing searchability.

       c0
main – ∘
        ↘      dev
         ∘      |
         cd1 → cd2

4. A spell checker runs on cd2 highlighting errors, which I think fixes.

       c0
main – ∘
        ↘
         ∘ → ∘ → ∘ – dev
        cd1 cd2 cd3

5. Now, my cd3 gets a green light from all of the linting operations that run on commits in CRs. It’s ready for a human review. An editor sees it, likes it, and decides to merge it into main. However, main has moved on… some other changes have taken place (perhaps another curator or maybe an automatic ingestion). These need to be merged back into dev.

                        main
       c0          c1    |
       ∘ →→→→→→→→→ ∘  →  ∘
        ↘            ↘ ↗
          ∘ → ∘ → ∘ → ∘ – dev
         cd1 cd2 cd3  cd4

Everything in this process is already possible with TerminusCMS. However, there is more yet to be done.

Document Graphs

Structured documents are widely used by both computers and humans. These include everything from Excel and Word documents which are more human-focused, to Protocol Buffers and JSON which use documents which are more machine focused.

HTML’s great innovation was to introduce into this idea of documents, the concept of the hyperlink. This would allow documents to refer to other documents.

HTML however was focused on rendering (Mark-up) rather than structured content. This means that HTML actually makes poor documents for machine manipulation.

In TerminusDB we have allowed structured content to use references to other documents, which gives us the power of both the graph, and document orientation, and allows machines to process documents more easily. Rendering can be thought of more as a publishing step of processing the structured knowledge graph data, and less as something which is built directly into the structured content.

It is also possible to mix-and-match, keeping the content as mark-up (or markdown) while having more structured accompanying information as well – as in the info-boxes on Wikipedia. For instance, a Politician might have a description renderable as markdown, but positions that could show up in an info-box, be searched easily, or processed by other machines.

{ "@type" : "Class",
  "@id" : "Position"
  "party" : "xsd:string",
  "start" : "xsd:date",
  "end" : "xsd:date",
  "position" : "xsd:date",
}
{ "@type" : "Class",
  "@id" : "Politician",
  "description" : "Markdown",
  "positions" : { "@type" : "Set",
                  "@class" : "Position" }
}
{ "@type" : "Class",
  "@id" : "Markdown",
  "@metadata": { "render_as": { "value": "markdown" }},
  "body" : "xsd:string" }

Empowering Cybernetic Cyborgs

This cybernetic approach is designed based on iterative processes, and bio-mechanical. Ultimately we hope to do more to facilitate this approach to data management to make it more scalable and more external.

Right now, we are adding information to commits about what objects changed to facilitate queries over histories, but we’d also like to be able to retain information about read-sets. A read-set is all of the data which you read that was necessary to make a transaction work. This information can allow you to reorder transactions while retaining the Isolation part of A.C.I.D.

This could allow you to have long-running transactions that can commit out of order with others, retaining isolation, as long as none of the information required for the completion invalidates the information. It also makes it the responsibility of the committing transaction to know whether or not this is the case, taking the load off of the central server, which can not in principle know what precise isolation level is acceptable.

To give a case in point, I could have a user class as follows:

{ "@type" : "Class",
  "@id" : "User",
  "name" : "xsd:string",
  "email" : "xsd:string",
  "credits" : "xsd:integer"
}

Now, we might want to perform a transaction that looks up the number of credits, finds them to be 20, and then commits the transaction if so. If the granularity of isolation is, however, the object, then people changing the user’s name will conflict. This is almost certainly not what is meant, but the DBMS can’t know this. With read-sets, you could.

In fact, you could even have amended transactions which just tack on a bit on the end to make things consistent. For instance, you could decide that the User needs >20 credits since 20 will be deducted. One starts with the read of 30 credits, comes back to commit and finds 25, and hence the committed number should be 5, which we could paste together in an amended transaction and complete.

This is a form of automated conflict resolution, and while not all sorts of conflicts can be resolved without aborting the transaction, it is possible to build logic around things like greater/less-than etc which would work.

Further, it’s entirely possible to ingrate CRDT data types into this model to get a mixed view, when you really don’t care about the ordering of transactions on a field or the exact state of the original or final read.

The approach of read-sets and external transactions are very general and therefore will be a powerful mechanism for sharing state not only among humans but also among micro-services.

Conclusion

TerminusCMS is our latest attempt to put up a cloud service which exposes some of the power of TerminusDB in a way that non-technical users can enjoy, while also giving the full headless API to developers. The tool is open source, and free to use on our cloud for even quite large databases, so we hope you give it a try and give your feedback!

TerminusCMS overview
TerminusCMS features
Free sign up

Written by TerminusDB CTO Gavin Mendel Gleason

Putting the Graph in GraphQL Query

Oliver — Wed, 08 Feb 2023 14:35:43 +0000

From the name, one would think a GraphQL query would be a graph query language. But then one would be incorrect. GraphQL is neither particularly graph-oriented nor is it a query language.

Don’t get me wrong, GraphQL is great, it’s just not exactly what it says on the tin. In reality, GraphQL is a sort of API killer. A way to avoid having to write a bazillion HTTP endpoints, and instead have a well-structured, schema-aware approach to getting information in and out of a service.

This is extremely useful, reducing development time for new APIs and, by having well-defined schemas which actually check for the correctness of the objects being communicated, averting many errors and regressions.

Yet wouldn’t it be great if GraphQL was also about graphs and a query language?

Well, that’s certainly what we thought at TerminusDB! We’ve recently implemented a suite of features which allows you to query a TerminusDB project using GrahpQL in such a way that deep linking can be discovered.

GraphQL Back Links

In a typical document in TerminusDB, you specify classes and their fields. This might look as follows:

{ "@type" : "Class",
  "@id" : "Person",
  "name" : "xsd:string",
  "pet" : { "@type" : "Set", "@class" : "Pet"},
  "friend" : { "@type" : "Set", "@class" : "Friend" }
}
{ "@type" : "Class",
  "@id" : "Pet",
  "@abstract" : [],
  "name" : "xsd:string"
}
{ "@type" : "Class",
  "@id" : "Dog",
  "@inherits" : ["Pet"]
}

TerminusDB automagically constructs a GraphQL schema derived from the project’s schema, which allows us to query it. A GraphQL query might look like this:

query
{
  Person {
    name
    pet {
      name
    }
  }
}

And we might get back a response along the lines of:

{
  "data": {
    "Person": [
      {
        "name": "Joe",
        "pet": [
          {
            "name": "Mimi"
          },
          {
            "name": "Fido"
          }
        ]
      }
    ]
  }
}

But supposing I find Mimi wandering the streets. How can I get back to the owner of Mimi? We defined our edge only in one direction. Yet in TerminusDB going in the reverse direction from an object is actually a cheap operation.

In order to achieve this, we have enriched the GraphQL schema with back-links which automatically give you the reverse edges of every object field.

We can perform the reverse GraphQL query as follows:

query
{
  Pet(filter: {name : {eq : "Mimi"}}) {
    name
    _pet_of_Person{
      name
    }
  }
}

This query asks for a pet, whose name is Mimi, and obtains the name field, but also a link to who they are a pet of: _pet_of_Person.

This field name is constructed automagically, and the language tends to work well using the genetive construction, but most importantly you can clearly see the type of the object from which it comes from. This is because reverse links could come from many different objects, all having the same field name, so it is important to disambiguate.

Our GraphQL query result using my current database state is:

{
  "data": {
    "Pet": [
      {
        "name": "Mimi",
        "_pet_of_Person": [
          {
            "name": "Joe"
          }
        ]
      }
    ]
  }
}

GraphQL Path Queries

Ok, well that is certainly handy since we often need to use these sorts of relationships in two directions, but what about graphs? Can we weave our way through the graph to find what we want? Can we do this with a GraphQL query?

TerminusDB adds path queries to our GraphQL schema to obtain precisely this.

A path query is a regular expression pattern describing the edges that it would like to follow in a graph. The full GraphQL path query specification can be found here.

For those familiar with regular expressions it shouldn’t be too difficult to pick up but even if new to the concept, it’s fairly intuitive.

Basically, I can write down the name of an edge: "friend" then you say how many times you want to follow this edge. If you want to follow it precisely once, we can leave it alone, if you want to follow it zero or more times, you write: "friend*". If you want at least one hop, but any number greater you can write: "friend+". If you want to follow it between 1 and 3 times, you can write: "friend{1,3}".

If I want to go backwards on an edge (similarly to the back links above) I can use a directional modifier: "<friend", and again I can modify this with the number of hops.

Let’s say we want to find everyone who has a friend with a pet named Mimi.

query
{
  Pet(filter: {name : {eq : "Mimi"}}) {
    _path_to_Person(path: "<pet,(friend|<friend)+") {
        name
      }
  }
}

In English, we might write this query as: “Get me all of the friends of the owner of Mimi, whether they believe they are this person’s friend, or the person considers them a friend, i.e. friendship here is not automatically symmetric, so we have to look at it from both perspectives.

The answer we get back is:

{
  "data": {
    "Pet": [
      {
        "_path_to_Person": [
          {
            "name": "Candy"
          },
          {
            "name": "Doug"
          }
        ]
      }
    ]
  }
}

Now we’re really talking about exploring the graph!

Future Directions

We already have a nice GraphQL interface for querying, but we intend to build out the mutation capabilities as well. We also want to have derived edges which are GraphQL queries that are the result of a WOQL query internally. This would allow us to expose very sophisticated queries which might make use of aggregation etc. at the level of GraphQL.

GraphQL has really simplified access to data for front-end developers and those performing analytics. It’s great to be able to expose it in TerminusDB. For us, the fit feels very natural and perhaps best of all: we have a very high-performance GraphQL!

You should try it out. You can either use TerminusDB by downloading it from our repositories, or you sign up for a free TerminusCMS account at dashboard.terminusdb.com.

Data Modelling & Collaboration for Change Makers - Do Good With DFRNT

Oliver — Fri, 27 Jan 2023 11:06:51 +0000

Last week saw the launch of the SaaS version of DFRNT, a tool to model and build data products. Built on top of TerminusDB, DFRNT gives digital architects the means to capture, navigate, and visualise complex graph data structures with accuracy and ease.

Having used DFRNT and had the pleasure of a demo from product creator Philippe Höij, we wanted to do a quick write-up of DFRNT as we know many of our readers have a keen interest in ontologies, data modelling and graph visualisation.

What is DFRNT and who is it for?

DFRNT is a browser-based tool for digital architects and an advanced data/ontology modeller with graph visualisation. There is a free version, a SaaS version that includes hosting of TerminusDB graph data products, and a version for self-hosted (on localhost) TerminusDB instances.

It provides access to an advanced bounded knowledge graph model which is fully type-checked, follows RDF semantics, and exposes both Datalog and JSON-LD document APIs for schema, queries, and updates. The model scales from personal knowledge graphs, all the way up to enterprise data product use cases.

The product has been developed to do good. To help teams collaborate. To confront global issues such as climate change, global pandemic responses, and biodiversity challenges. And to make a positive difference to societal forces like healthcare, economic equality, and racism. A tool to help build shared data structures necessary to navigate the complexities changemakers face making an impact at scale.

Creating change for such huge issues is no easy task. It requires collaboration, thought, and experimentation. A place for academics, business leaders, philanthropists, and digital architects to hypothesise, visualise, share, and plan. These challenges are not predictable, but with a focus on a shared vision and expected outcomes, the chances of success are greatly enhanced. The DFRNT launch brings core tools to address graph data collaboration where complexity is high, and to allow explorers to express graph data freely in the way it should be shaped.

“DFRNT exists to enable digital architects, changemakers and data scientists to collaboratively author, visualise and connect advanced data structures for change initiatives; and to derive new insights through the multiple perspectives offered by dynamic knowledge graph canvases.”
Philippe Höij, founder of DFRNT

DFRNT for Business

DFRNT helps businesses do good too. The challenges organisations face are complex. Cybersecurity, risk assessments, carbon emissions, and regulatory compliance are costly headaches, relationship-heavy, and difficult to understand.

Digital architects, data scientists, and changemakers routinely have to resort to their corporate-imposed collaboration toolbox of Powerpoint, Excel and whiteboard applications offered centrally. It is a big stretch to call these graph tools and using inappropriate tooling makes solving problems that involve exploration and ideation based on hyperconnected datasets extremely challenging.

To help these experts work well, they need multiple perspectives (canvases), data enrichment, and advanced query engines. A significant reason for Philippe to build DFRNT was to build a tool to serve his own needs as a digital and security architect.

Here’s an example of DFRNT in action, using a risk assessment model aimed at helping a business’ cybersecurity department plan and mitigate security vulnerabilities and cyber threats. The data product view features the ability to describe data products using markdown to present the risk model cleanly and informatively to business users.

The risk model is then modelled using types and traits, modelled data structures attached to the types as properties. The example below is of an advanced type definition that uses both multiple inheritance and property composition (traits) for how a qualitative risk JSON-LD type may be modelled. Additionally, there is a recognized markdown data structure that enables strings to be recognized as markdown and rendered, which enables risk details to be expressed in formatted prose and be part of the data model. Risk data is then rendered together with inbound and outbound links to other elements of the graph to easily navigate the graph from a data exploration perspective.

The final image shows the canvas feature of DFRNT. Select data to add to a canvas for graph visualisation. Be as granular as you like, for example view the relationships between a single entity or take a look at the bigger picture and see the model as a whole. With the ability to save canvases and download them as images to use elsewhere, this is a great feature to share and understand the structure of the problem being solved.

The Need for DFRNT

Relational databases and SQL are the most popular type of database and query language. They are well-suited for organising and managing structured data in an efficient manner, however they are not well-suited for certain types of tasks, such as:

Working in a model driven approach with embedded schema and embedded semantics.
Performing complex mathematical computations or data analysis. Handling real-time data streams or handling large numbers of concurrent users.
Handling graph or hierarchical data.
Enabling hierarchical grouping of buckets that are of the same kind.
Making it easy to build thin apps that leverage the semantic model directly.

These types of tasks are often at the heart of the problems that DFRNT is helping to solve. A better solution for these tasks is an RDF graph database that exposes schema-ful/typed data structures.

Predictions for exponential growth of graph database adoption has been a feature of many ‘future trends’ reports, but this growth has never quite hit the forecast heights. Part of this problem has been a high barrier to entry. One of the main barriers to entry is data modelling. Graph databases require a different approach to data modelling, which can be challenging for developers who are used to working with relational databases.

Despite the increasing popularity and maturity of graph databases, the lack of adequate modelling tools for them remains a major hindrance to their wider adoption, leaving many businesses and people struggling to harness the full potential of this powerful technology.

What has been needed is the business-orientated TerminusDB-style closed-world interpretation of OWL, with strongly typed, discernable, and predictably structured graph data. Additionally, using a document-orientated style to express the graph makes taxonomies and ontologies easy to formulate and attach data properties and structures to. Data instances become clearly expressed in a schema with semantic descriptions.

DFRNT is a service that makes this expressive TerminusDB way of modelling easy to use, we find this a remarkable feat. It radically simplifies data and ontology modelling and gives a whole new generation of digital architects powerful tools, and makes it even easier for those already in the field.

Where TerminusDB fits in

TerminusDB is used as DFRNT’s engine for graph data product instances.

TerminusDB is an open-source (Apache 2.0) data model and hosting platform, professionally maintained by the TerminusDB team so you don’t have to.

It features a secure version control system for collaborative data modelling, including branching for experimentation, prototyping and enhanced resilience. Any changes made are tracked with accuracy and security.

These ‘git-for-data’ features were essential for DFRNT to provide a truly collaborative data product builder with several innovations to make cross-data product collaboration easy. Data developers can create a branch (shallow copy) of the main data branch and later “rebase” their changes on top of updates made later in the main (official) branch. Pull and push to remote branches are also elegantly implemented without the usual key-handling complexities. Errors and mistakes can be fixed quickly by branching an older version to retrieve old data, or rolling back to a known good version of the data product, just like working with code,

DFRNT provides peace of mind knowing that your database remains secure and up to date no matter what happens during development and editing processes.

Get started with DFRNT

Getting started with DFRNT is quick and easy. If you, or if you know of other fellow digital enthusiasts who want a better way to model data for complex problems, give it a go, their details are:

Visit dfrnt.com.
Follow DFRNT’s progress on Twitter and LinkedIn.

A look ahead to our open-source headless content and knowledge management system

Oliver — Tue, 10 Jan 2023 13:28:03 +0000

In a little under a month, we will be launching TerminusCMS, an open-source headless CMS to provide businesses with composable architectures and true organization-wide knowledge management.

TerminusCMS is not like existing headless CMS services such as Contentful which are primarily aimed at brochure websites and e-commerce stores. Our headless CMS is developer-first and is designed to enable engineers to build composable architectures and knowledge management systems for complex environments.

The purpose of this article is to provide you with a better understanding of what TerminusCMS is and where it will fit within an organization. If TerminusCMS resonates with your project requirements, please contact us to discuss your needs to get in the door first.

A brief history about how we got here

Like with most startups, there have been a number of pivots in recent years as we seek our market fit. TerminusDB started life as a schema-supported graph database aimed at providing DataOps to engineers with our Git-like collaboration model. As we evolved and developed new features such as the version 4.0 Document Interface we inadvertently began to broach the CMS space, at the time we even wrote in our community Discord server –

‘The document interface is basically a "CMS in a box" for terminus data objects. The documents page allows you to filter and order documents of different types, create documents of any type through a simple form, view documents as either JSON-LD or a simple web page, and edit, delete, create and update them with no code.’

Version 10 of TerminusDB saw us move edge closer to becoming a headless CMS provider as users built collaborative and complex applications with TerminusDB and TerminusX as the backend. Following an increase in user activity in the headless space both within our community and the types of applications being built, we decided in June 2022 to focus our efforts to become the leading headless CMS provider giving organizations a compostable architecture for business-wide knowledge management.

The next two weeks will see us integrate the past six month’s development into TerminusX and make TerminusCMS available as a Docker compose, complete with cloneable demos to play with.

Standard headless CMS features

TerminusDB is and will continue to be available for those looking to build with our document graph database. TerminusCMS will be available as a separate Docker compose, it will come with new CMS features, that include –

Schema model builder – develop with code or user interface
GraphQL & REST API endpoints
Admin UI
Change requests workflows
Media library
User authentication and management

These are the standard features you would expect from any headless CMS.

Features for composable architectures and knowledge management

What sets TerminusCMS apart from other headless CMS providers are several features that have been in our arsenal for years and extended upon. Built from the database up, TerminusCMS gives devs many features at the database layer without being reliant on third-party data stores or troublesome plugins. The exciting features include –

Schema as code – Many CMS providers have invested in slick UIs to build content models and schemas. UIs are great for domains, but from a developer’s perspective, and when schema becomes complicated, are cumbersome and slow. It also causes issues when migrating or cloning schemas. TerminusCMS lets devs build with code to work quickly and efficiently.
Semantically enriched and standards-based CMS – Under the hood of TerminusCMS is an RDF graph database that connects JSON documents into a knowledge graph. Developers can model content, asset, and data with relationships to provide context, discoverability, and advanced analytical capabilities.
Bridging data and content silos – Headless CMS normally provides storage for content and assets, useful for websites. However, headless CMS can be used for so much more. For instance, using CMS as a composable architecture and knowledge management system necessitates the need to include often hidden transactional and operational data. TerminusCMS helps to bridge the gap between content and data to provide greater power to front-end developers.
Custom workflows – Approval workflows and pipelines are built into the database layer and can be completely customized to suit the needs of your organization and the individual working methodologies of your teams. Set specific workflows by user role or content/data type to tailor the way of working to your exact needs.
Analytics engine – We have integrated our datalog query language into GraphQL so you can use GraphQL as a full-blown graph query language. The connected graph of content, assets, and data can be analyzed with powerful GraphQL queries to make discovery and analytics available across your content infrastructure. With the advancements seen with OpenAI, get your content and data AI ready from the start.
Immutable version control & collaboration – Our bread and butter from the very beginning. TerminusCMS is immutable and has Git-like collaboration features allowing branching, cloning, merging, diff, time-travel, and non-lock collaboration.
Authentication from database to front-end – Robust authentication is handled in the database layer so there is no need to integrate other auth providers into front-end apps making it easier and safer to control access.

What are the ideal use cases for TerminusCMS?

TerminusCMS is aimed at large organizations with complex infrastructures. An ideal business is one that wants to understand and manage organization-wide knowledge by integrating interdepartmental data, processes, and content and then making it discoverable and useable internally and externally.

As it’s early days, we don’t have a definitive list of sectors that TerminusCMS is aimed at, but we have a number of customers using TerminusDB as a headless backend for an array of applications and services and a number waiting to get started with TerminusCMS.

Our primary focus, in the beginning, will be to work with developers and consultants who either work for or have large organizations as clients. Much of our development has been driven by the feedback from developers and consultants working on similar projects, and we see TerminusCMS as a perfect fit for –

Manufacturing and Engineering – Manufacturers and engineering companies are rich in data, products, and processes. Information about machine performance, product specifications, the supply chain, and distribution channels is spread across different platforms and made available to the relevant people in unconnected ways, causing many issues. TerminusCMS helps to connect disparate teams, provide leadership with a holistic view of operations, and serve relevant data and content to stakeholders.
Pharma & Biotech – Pharmaceutical and biotech companies are complex operations. From discovery to launch, there are vast amounts of data, documentation, and content required for researchers, medical professionals, patients, and legislative bodies. TerminusCMS aims to help improve the flow of important data and content between departments, legislators, and patients, by making information discoverable and useable to surface relevant information to stakeholders. It is an auditable CMS for medical companies that need stringent governance.
CMS for Compliance – Cybersecurity is at the forefront of policymakers across the world. Ransomware and various other attacks have left major institutions in disarray. Both the EU and the US have plans for rigorous legislation to improve security and reduce the risk of cyber threats. TerminusCMS’s immutability and versioning are ideal for maintaining software bill of materials and vulnerability reports to ensure compliance and to be able to operate in these regions when legislation forces companies to take action.

The list of sectors that can benefit from TerminusCMS and its ability to develop a composable architecture that scales is by no means complete. Other ideas we’ve surfaced include semantically tagged training data for technical documentation so AI can serve customer documentation requirements, interactive blogs where users can branch and create their own twist of the content, and large-scale knowledge bases built collaboratively such as big research projects. The list could go on, and we haven’t even included the basics of brochure websites and e-commerce stores.

Our goal is to provide developers with a headless CMS that makes their jobs easier. No more plugin architectures, no more security flaws, and no more dread of being dragged into a CMS project. Less time firefighting, more time building great things.

If you think of areas where TerminusCMS would sit nicely, we’d love to hear from you, we’re a small team so ideas are always welcomed warmly. If you’ve got projects that you think TerminusCMS could help you with, get in touch and we can provide you with a demo prior to its release.

2022 - A Year In Review

Oliver — Tue, 20 Dec 2022 16:03:35 +0000

This year has gone by so fast. I know, I know, we say that EVERY year, and yet every year it’s true that the year in question really seems to have gone by a lot faster than the previous years. So much has happened in 2022, and there is so much to look forward to in 2023. However, all too often, we can get caught up in the rush of life and all the plans we have for the future, so much so that we lose track of just how far we have already come.

As a tech start-up, we are almost always iterating, pushing out new features, and working on new products and services. TerminusDB has exciting plans for next year, but we are going to take a little moment to look back at all that’s happened in 2022. What better time to do a retrospective than at the end of the year, right? Here’s what happened, ICYMI:

Community and Collaboration

The Terminator community is now 674 people strong! From modest beginnings to now nearly 700 people. We are delighted to be able to share this journey with you and look forward to more growth and success. As always, we are grateful for the feedback and welcome all questions. If you’re new to TerminusDB and haven’t joined our Discord community yet, you can do so here. It’s a great space to chat all things TerminusDB. It’s also a great space for discussions on all things data and databases, so if that’s your vibe, we’re your tribe.

As a result of our growing community and of being open source, we’ve been fortunate to have made friends that we have been able to collaborate with over the years. One of those projects has been on DFRNT with Philippe Hoij. If we’re being perfectly honest, this collaboration started in 2021, but has really come into full force and fruition this year. DFRNT is a SaaS platform that enables visual graph data collaboration while leveraging TerminusDB. DFRNT provides graph data product hosting, visualization and modeling, with data product hosting maintained by us over at TerminusDB. You can find out more here.

Also this year, community member, Fidel Thomet, demonstrated how TerminusDB is being used as a collaborative research database to support the Amazonia Future Lab project.

The purpose of the project is to derive knowledge from indigenous communities and collections spread across various cultural institutions. Collaborative working is at the very heart of the project and is essential to understand how certain artifacts were used, to create new interpretations of cultural heritage, and improve the representation of indigenous perspectives. The connected knowledge will be publicly accessible via interactive formats to explore and contribute to. The tools created will be made freely available to be used or further developed by other communities and institutions that are engaged in the field of participatory cultural education.

To see how you might be able to use TerminusDB for a project of your own, have a look at our use cases, or get in touch with us.

Climate Action

In July 2021, TerminusDB received an interesting email. It was to chat about how TerminusDB might be able to help with the development of a critical asset management tool to help governments be better prepared for disaster management and resilience in the face of climate change. After months of conversation with key stakeholders, and some furious development on our part, the CAMS MVP was launched, with a Spanish version of the tool made available shortly thereafter. CAMS is a critical asset management system developed as part of a voluntary effort, led by ARISE-US, a private-sector advisory group to the United Nations Office for Disaster Risk Reduction (UNDRR), and TerminusDB.

The project is open source and focused on providing a data-driven system to help islands, cities, and communities become disaster resilient. It does this by storing all critical asset data and the asset dependencies. CAMS is a data-driven mobile and desktop application. Government officials and first responders use it to plan and respond to disasters. Learn more about the project here, and see how you can contribute.

Compliance

We achieved SOC 2 compliance! While some of our team are still somewhat recovering from the trauma, we did it all for you! The SOC 2 compliance certification is the most widely recognized method for sharing independently reviewed information about a service organization’s internal controls. The accreditation means that TerminusDB and TerminusX meet or exceed the levels of security required for service providers storing customer data in the cloud.

While we have always taken data security and privacy very seriously – we are after all, a database company – having SOC 2 certification lets us demonstrate to new and existing customers these matters are a priority to us.

New Features and New Releases

There have been plenty of new features, along with a few releases this year.

TerminusDB CLI

If you’re signed up for our newsletters, you’d have received some updates on the TerminusDB CLI for Push / Pull / Clone. TerminusDB is designed to be a distributed database with a collaboration model. The building blocks of that model are revision control, diff, and push/pull/clone. It is essentially meant to be like Git, but for data. The foundation of a distributed database with a collaboration model are Revision Control, Diff, and Push/Pull/Clone. Read more about the TerminusDB CLI, and the building blocks of a distributed database with a collaboration model here.

TerminusDB 10.1: The Mule

We had a need for speed, so we released TerminusDB 10.1, which demonstrated significant improvements to the speed and performance of the document interface, including much improved WOQL integration.

The Mule Release – a homage to Asimov’s Foundation series, of course – was faster, more robust, and packed with new features to make building knowledge graphs and data-intensive applications easier and quicker. Some of the noteworthy elements in the new release were:

Type inference
Unconstrained and untypechecked JSON documents and subdocuments
ID capture
Document UI SDK
JSON Diff & Patch
Applying a patch from any two

The release also included improvements to the CLI, Oauth2 configuration for SSO, and more features you can read more in detail about here.

More Speed with TerminusDB 10.1.5

This version of TerminusDB included some significant performance improvements, including a 10x speedup of document retrieval and a 10x improvement in insertion speed. More details can be found here.

GraphQL is here
This is something that we’ve been working on for the better part of this year, and we were excited to announce that it finally happened. The latest TerminusDB release came with GraphQL to further improve the developer experience. Your data product schemas are automatically loaded in GraphQL for speed and convenience. GraphQL means you can now use most programming languages to work with TerminusDB. This release was a big step toward TerminusDB becoming a headless CMS and managing content in a knowledge graph. You can read more about our plans for headless CMS here.

Company and Celebrations

Over the course of the pandemic, we became rather good at throwing virtual parties and celebrations - all complete with themed quizzes created by the ultimate quiz master, i.e., me.

Jokes aside, 2022 was the first time in a long time we all finally got together in person for a week’s worth of planning - in beautiful Vienna to boot! Many of the new features and developments you’ve been seeing over the course of the year have been a result of all we discussed during that week’s worth of planning. We had an internal retrospective recently, as part of one of our discovery sessions, and almost everything we had planned in Vienna has been implemented.

As per usual, we focused all too much on all the things that are yet to be done and all the plans we have for the future. Still, I think we should be very proud of what we’ve accomplished this year. I, personally, am always in awe of our team. We are small in number, but strong in might. We ended this year of work with a lovely (virtual) Christmas party, and would like to take this opportunity to wish all of you who are along on this ride with us a very Happy Christmas and a joyous New Year.

See you in 2023 with lots more exciting stuff coming your way.

TerminusDB - Now with GraphQL

Oliver — Thu, 17 Nov 2022 14:20:12 +0000

For those of you that don't know, TerminusDB is a document graph database with Git-like superpowers. It stores data as JSON documents and the schema language connects these into a graph. You get the best of both worlds, the convenience of JSON with the query power of Graph.

The latest version of TerminusDB has been released which means TerminusDB now comes with GraphQL to improve the developer experience. Your data product schemas are automatically loaded in GraphQL for speed and convenience. GraphQL means you can now use any programming language to work with TerminusDB.

Enhancements include –

GraphQL endpoint at localhost:6363/api/graphql/ORG/DB
GraphiQL endpoint for testing available at localhost:6363/graphiql/ORG/DB
GraphQL automatic loading of Schema in GraphQL schema
GraphQL search and retrieval

Head on over to GitHub for a full list of enhancements and bug fixes.

If you want to learn more, take a look at our GraphQL docs or install the latest version of TerminusDB to experiment and play.

Excitingly, this release is a big step toward our TerminusDB becoming a headless CMS and connecting content in a knowledge graph. You can read more about our plans for headless CMS here.

Here’s a quick example of how GraphQL works in TerminusDB –

Using the following TerminusDB schema:

{ "@type" : "Class",
  "@id" : "Person",
  "name" : "xsd:string",
  "dob" : "xsd:dateTime",
  "friend" : {"@type" : "Set", "@class" : "Person" }}

TerminusDB will generate the following GraphQL class.

type Query {
  Person(
    id: ID

    """skip N elements"""
    offset: Int

    """limit results to N elements"""
    limit: Int
    filter: Person_Filter

    """order by the given fields"""
    orderBy: Person_Ordering
  ): [Person!]!
}

type Person {
  dob: DateTime!
  friend(
    id: ID

    """skip N elements"""
    offset: Int

    """limit results to N elements"""
    limit: Int
    filter: Person_Filter

    """order by the given fields"""
    orderBy: Person_Ordering
  ): [Person!]!
  name: String!
  id: ID!
}

You can then query this using the GraphQL endpoint.

We’ve got more planned

TerminusDB automatically generates fields in GraphQL based on classes and their properties in the data product schema. Here you can use arguments such as id, offset, limit, and order by, as well as filters such as time comparisons and for strings, and, or, not. All the filter options are also automatically generated for you.

We’re not stopping here though, we are working to integrate WOQL into GraphQL so that you can use GraphQL for complex path queries to make building graph-based applications even easier.

Our goal is to be the smoothest and most powerful GraphQL experience around.

We hope you join us on this journey.

Other resources that you might like

RDF & GraphQL Bridge using a Star Wars Dataset

How we implemented GraphQL in 14 days

Tutorial – Build a blog-focused CMS with TerminusDB & GraphQL

TerminusDB Internals - Part 1 - Graph Representation

Oliver — Thu, 17 Nov 2022 12:06:03 +0000

When we were designing TerminusDB we wanted to make a graph database which would allow curation of large complex graphs where the search mode (we’ll talk a bit about modes in a minute) was not yet known. In playing with some large graphs (for instance a database of all Polish companies since the mid 1990s) we came to the following conclusion:

Graphs, due to their highly interconnected nature, are hard to segment
This makes paging, and network communication, potentially very costly when edges are traversed across segments
Main memory size can accommodate many very large graphs even for enterprise scale problems.

Point two is especially hard to overcome. If you start paging in a graph, because of the very random nature of graphs, we can get extremely varied pages. This could easily lead to thrashing. Since disk access times on fast SSD are one to two orders of magnitude slower than DRAM we’re talking perhaps 100 times worse performance. For networks this climbs to three orders of magnitude.

These considerations let us to speculate that we could build an in-memory graph database if we were careful to ensure that we were sparing with memory use.

In addition to this in-memory advantage, having low memory overhead has additional benefits for collaboration, in that we can send deltas around in a compact format.

Size matters, and smaller is better.

It’s important to note, that by in-memory we mean that there is no database paging, we do not move parts of the database into and out of memory. It does not mean that we are not writing to disk. TerminusDB is both ACID and persistent, so there is no risk of data loss for completed transactions.

Relational indexing

In typical databases, we ask questions of relations. Relations are typically built from tables of facts together with some operations which allow us to join relations. In addition we often specify particular projections of these relations by asking for certain constraints to hold.

SELECT Orders.OrderID, Customers.CustomerName, Orders.OrderDate
FROM Orders
INNER JOIN Customers ON Orders.CustomerID=Customers.CustomerID
WHERE Orders.OrderDate > 2010-04-01;

Create a new relation by joining two relations, Customers and Orders on the customer ID field and project to a relation in which all dates are more recent than 2010-04-01 using the WHERE restriction.

In order to make these queries efficient we will often introduce indexing on the fields which we want to join or restrict. If we do not do this, then we might have to scan through each CustomerID in the one table to see if it is in the second table. A scan means we look at each record. If the size of Customers is n (|Customers| =n) and Orders is m (|Orders| = m), then this would result in a number of operations on the order of n*m. Similarly, if we have not indexed the date field, we will have to compare the date for each record that we produce.

With an index, we can make access log like, by creating a tree which makes it possible to access the data without a scan. Our date restriction will allow us to start our search in the right place in the relation which will make our effective m smaller (which we might call m', and the order of the problem shrinks to n * log(m').

If n and m are big numbers, then this is a big deal. If we have more than one join, we can easily see how unindexed relations could lead to numbers which spiral out of control and are effectively impossible to query.

Graph Databases

In a graph database, we remove a good deal of this complexity by having exactly one type of relation, the edge. And since we want to be able to explore the graph very freely, we will need to index everything. This will let us join to create paths through the graph. Everything is a self join of a single relation in a graph, the edge relation.

For a search we can think of querying our relation in any of the possible modes. A mode means specifying what we know, versus what we need to look for. We write a - for anything we don’t know, and a + for anything we do. We can write our modes as a triple such as (+,+,-).

Graph modes include:

(-,-,-)
(-,-,+)
(-,+,-)
(-,+,+)
(+,-,-)
(+,-,+)
(+,+,-)
(+,+,+)

…so eight query modes that we might want to support.

Now, some of these might be more common than others, and therefore we might want to make them faster. We’ll talk about that later when we get into the guts of our index.

By way of example, let’s think of a data point named Joe. If we wanted to see everything that Joe is connected to, we might say (in WOQL):

let v = Vars("p","x");
triple("Joe", v.p, v.x)

This has mode (+,-,-).

If we wanted to see everything that was connected to everything that Joe was connected to, we might say:

let v = Vars("p","x","q","y");
and(triple("Joe", v.p, v.x),
    triple(v.x, v.q, v.y))

Here we start with (+,-,-) and it might at first appear that we have (-,-,-) for our second search. However, we can get the results back from the first search to reduce this to (+,-,-) meaning we can consider a projection of the relation speeding things up considerably.

Sparing Use of Memory

Doing all of this indexing makes query very flexible. We can weave relationships out of the graph and instead of having all sorts of different tables with different shapes we can just have one big table.

This is also potentially very fast if everything is indexed and we can do restrictions quickly.

But it also threatens to make things very big. How many indexes will we need to build all of this? The mode (-,-,-) is just the whole relation so doesn’t need an index. For (+,+,+) we can probably permit ourselves a scan on one of the fields as we’ve already restricted heavily. What can we get away with?

Indexes are trees that help us get log like behaviour out of our searches. Trees often mean adding lots of pointers. Pointers can actually end up being a substantial amount of the size of an indexed database as we create the many layers of the tree.

If our database grows too great in size, we threaten to hit the size of main memory. We can often add more memory, but the more parsimonious our representation, the more databases will fit into a given memory size. It therefore pays handsomely to be small.

However, we can solve this problem with a family of data structures known as succinct data structures. These try to keep fast, log-like access modes available, while keeping storage space close to the size of the data itself.

The Dictionary

The first point of entry is the dictionary. Given a name (such as Joe) we want to come up with an internal identifier which consists of an unsigned 64 bit integer. This will be our internal name for Joe, which takes a fixed and relatively small amount of space.

Essentially we need a table which goes from integers to names and back again.

In TerminusDB we do this with a data structure known as a Front coded dictionary. This structure is particularly good when your identifiers are likely to share prefixes. Since all named identifiers in TerminusDB are IRIs.

If we have a block size of eight entries, a block might look as follows:

Input	Common prefix	Compressed output
myxa	None	0 myxa
myxophyta	'myx'	3 opyta
myxopod	'myxop'	5 od
nab	None	0 nab
nabbed	'nab'	3 bed
nabbing	'nabb'	4 ing
nabit	'nabit'	3 it

The basic idea is to store deltas between strings, allowing us to use less space to store all of our strings than would be required with a straight dictionary. The dictionary is organized in blocks with each block starting with a full, uncompressed entry, and all subsequent entries in the block are allowed to refer back to any element in the block to reuse parts of previous elements.

As you can see, we get substantial compression here by reusing prior entries. But we have to start over with no common prefix every block size, and if we share nothing, we get a slight disimprovement (as we have to store a zero offset as a prefix to our compressed output).

This gives reasonably good compression for typical IRIs, often between 40 and 80%.

To get our ID, we simply need to know numerically which entry we are in the dictionary. Since we store the dictionary entries lexically sorted, we can find a specific entry using binary search. First we look up Jim in the middle of the dictionary, if the first entry in our middle block is bigger than Jim, we scan through the block, if we’re bigger than every entry of the block, we search in the middle of the second half of the dictionary. If we are less than Jim we can search in the first half. Wash-rinse-repeat, we have access to our index using an access mode that guarantees we get our answer in a log of the size of the dictionary O(log(n)).

And going in reverse we can find the dictionary entry for a given integer in O(1) (constant) time. We do this by keeping around an index of block-offsets so we can quickly find which block we are in. The block offsets themselves are stored in a compressed data structure which has constant time access (in our case a Log Array, but it could be another data structure such as an Elias-Fano encoding).

For our graphs we have three dictionaries. One for nodes, which form the subjects/objects, one for predicates or edges and one for values.

The first shared dictionary allows us to use the same subject id for an object which is convenient in following chains. Predicates, or the edge name, is treated specially as it is seldom necessary to look them up in a chain, so they can reside in their own name space, can can use an overlapping range of integer ids with the nodes.

We also represent our data in a value dictionary. These are represented as a specific offset above the numbers used for nodes, which we add to the number of our dictionary entry to translate to and from id-space.

Note, that to store data effectively here using a dictionary with front encoding, it is important to store everything lexically. We’ll address lexical encodings of data types in another future blog.

The Adjacency List

Once we have our id, we need to see how we are connected. Let’s imagine we are starting with Joan and our access mode is (+,-,-).

Perhaps there are only two people in our database for the moment, and our graph looks like this:

Jim -address-> "12 Mulberry Lane"
Jim -dob-> "1963-01-03"
Jim -friend-> Jim
Jim -friend-> Joan
Jim -name-> "Jim-Bob McGee"
Joan -address-> "3 Builders street, house number 25, apartment number 12"
Joan -dob-> "1985-03-12"
Joan -name-> "Joan Doe"

Our node dictionary is {'Jim':1,'Joan':2} our predicate dictionary is: {address:1,dob:2,friend:3,name:4} and our value dictionary is: {'12 Mulberry Lane':1,'3 Builders street, house number 25, apartment number 12':2,'1963-01-03':3,'1985-03-12':4,'Jim-Bob McGree':5,'Joan Doe':6}. Note that we still have to apply an offset of 2 (the size of our node dictionary) to our value dictionary to get back and forth between id space and our dictionary entry number for values. Also, all dictionaries are 1 indexed rather than zero. We will treat zero as a special identifier representing emptiness.

To find out what predicates are associated with Joan we need to look them up in an adjacency list. Internal to TerminusDB this is represented with a pair of data structures. A log-array and a bit index. The log array stores the ids of our associated predicates, and the bit index tells us which predicates are associated with which subject.

For instance, to look up Joan, we first look up the second entry (Joan’s id is 2). This is done with our succinct data structure, the bit index.

The Conceptual Structure

Our bit index looks conceptually as follows:

Subjects	Subject Id	Bit Index	SP Array
Jim	1	1	1
		1	2
		1	3
		0	4
Jane	2	1	1
		1	2
		0	4

The bit index tells us what subject is associated with which entry of the SP Array (using select), and the SP Array holds the predicate id which is available to that subject. The index of the SP Array is conceptually an Subject-Pair identifier, refering to a concrete subject (available by asking the rank of the bit-index, the population count of 1s at the specific offset) and simply by returning the value of the SP Array at that index.

Making the rank and select operations fast for bit-indexes is its own subject which we will talk about in a moment. For now it’s just important to know why we want them to be fast.

We have the following the concrete representations:

SP BitIndex: 1110110
SP Array: [1,2,3,4,1,2,4]

We can ask for the (subject_id - 1)th 0 of our bit-index to find out which section of the bit index we are interested in. So for instance, if we want to know what Jane is connected to, we look up the index of the 1st 0, add one, and we find our subject-predicate starting index. In this case that index is 5.

We can then iterate over this vector up until we reach the next 0 in our bit index, and these are all the SP pairs associated with Jane. In other words, the indexes into the SP array of 5 through 7 are associated with the Subject 2, and have predicates 1, 2 and 4.

                 Jane's bits in the bit index
                      | | |
SP BitIndex:  1 1 1 0 1 1 0
SP Array:    [1,2,3,4,1,2,4]
                      | | |
                      Jane's associated predicates:
                        address (1), dob (2), name (4)
                        ...but not friend(3)

Now, supposing we have an SP index, how do we find the object associated? Since each predicate can point to multiple objects, we will use the same trick again. In our case we only have one object for each element of the SP Array, Here, we use the Object Log Array.

SP BitIndex:  1 1 1 0 1 1 0
SP Array:    [1,2,3,4,1,2,4]
O BitIndex:   0 0 1 0 0 0 0 0
Object Array [3,5,1,2,7,4,6,8]

Ok, so what object is associated with Jane’s name? First, we look up the name to see that it is predicate id 4. We know that Jane starts at index 5, so we can scan through the SP vector until we get a 4. We remember this index, which is 7.

We can now ask for the index of the (7-1=6)th zero in the Object BitIndex and add one to get 7. The number at this index is 8. Since 8 > 2, the max number for nodes, we know this is a value. We can subtract 2, get 6, and look up the number in the value dictionary, to retrieve “Joan Doe” (6). Success!

Notice that there is one 1 in the Object BitIndex. This corresponds with the fact that the predicate friend (3) has two elements in the Object Array. The 3 in the SP array corresponds with friend. It is at index 3. When we look up the (3-1)th zero in the Object index we get a 1, we add one to get 2, see that there is a 1 in this position, and know that there is more than one value. We count the number of values (number of ones + 1), and get that there are two values. We can now iterate in the Object arroun from the index 3 to the index 4.

The answers here are 1, and 2, both are less than or equal to our node count, so we are nodes. We can look up the node names in our dictionary and find it is Jim, and Joan!

Reversal of Fortune

But how do we go backward from object id to SP? We need another data structure here. In this case it will be the inverted index of the Object Array.

O_SP BitIndex:  0 0 0 0 0 0 0 0
O_SP Array     [2,2,0,5,1,4,3,6]

If we know an object Id, for instance, we want to find the object associated with the name “Joan Doe” we simply look it up in the Object dictionary, get an id of 6, add two (the offset for nodes) to get 8. Now we look up where we are in the Object to SP bit index, by asking for the (8-1)th 0, and add 1 and find that we are at SP index of 6. If we look up this index (6) in the SP_array, we find that it corresponds with name (4), and we can count the number of zeros in the SP BitIndex up to this point to our Subject identifier which is 2, the id of Jane!

Bit Indexes

Our bit index lets us perform two operations, select and rank. We were using them above informally to find the ith zero (my_array.select(0,i)), and the population of zeros up to an index (my_array.rank(0,i)).

Of course we could implement these operations trivially by scanning through a bit vector, but that would take time proportional to the number of elements O(n). To do it faster we need to keep some additional information.

We can see here that our implementation in rust keeps around some book-keeping, a BitArray, and LogArray representing blocks and sblocks.

pub struct BitIndex {
    array: BitArray,
    blocks: LogArray,
    sblocks: LogArray,
}

The bit array just contains the bits themselves. The blocks however, keep track of population counts so we know the rank, and the super blocks keep track of super population counts.

For instance, for the bit sequence used above, blocks of size 3 and super blocks of size 6, we might have:

BitArray:  1 1 1 0 1 1 0
Blocks:   |  3  |  2  |  0  |
SBlocks:  |     5     |     0    |

To find the number of 1s at index j, we simply make the calculation of the number of bits up to j in a block, and use the population counts from blocks and superblocks. In rust pseudocode:

let array = BitArray::from_bits(0b1110110);
let block_index = j / 3;
let sblock_index = block_index / 2;
let block_rank = blocks.sum_rank(blocks_index);
let sblock_rank = sblocks.sum_rank(sblock_index);
let bits_rank = array.sum_rank([block_index * 3],j);
sbock_rank - block_rank + bits_rank

Here the sum_rank function just counts the rank as a sum from the last superblock, last block or last bit sequence. This can be considered a constant time operation as each of these sizes is fixed and though we have to compute all three, three constant time operations is also constant.

The rank of index 4 is now calculated with block_index = 1, sblock_index = 0. Therefore we take 5, subtract 2, and add 1, to get 4. Indeed the correct rank. The number of zeros is the index + 1 minus the population count of 1s, or 1.

So rank is done, but what about select? It turns out we can implement select by doing a binary search with rank. Recall that select finds the ith zero or one. To implement this we can simply start from the mid point, look at the rank, and keep subdividing until we get a select that matches. Since rank is O(n), this means that select, implemented in this way is O(log(n)).

Conclusion

If you’ve made it this far then congratulations, you’ve a lot of stamina! What you’ve learned so far is enough to make a graph with flexible query modes that can be used as a foundation for a database.

All of these succinct structures are tightly packed and therefore optimised to be write once, read often. They aren’t well suited to mutable updates. In order to get these mutations, we’ll need some more machinery. In my next blog, we’ll dig into how that works.

This blog was written by TerminusDB CTO Gavin Mendel-Gleason and posted here on his behalf.

DEV Community: Oliver

Building a vector database sidecar for semantic search & entity resolution

Writing a vector database

Storing the vectors

Creating a versioned index

Finding embeddings

Indexing Star Wars

Conclusion

Update - July 2023

Schema Migration for Graph Databases

Schema Migration in Graph Databases

Schema Migrations as First-Class Citizens

Weakening and Strengthening of Schemas

Weakening Inference

Explicit Migration

Targeting a Migration

Conclusion

Stories from over yonder

Reframing Data Strategy: The Era of Quality Data - Unlocking Success Through Prioritizing Accuracy

Redefining Collaboration in Database Management: Unleashing the Potential of TerminusCMS

Revolutionize SBOM Management with Headless CMS

Elevate Your Data Management: Empowering Business Critical Functions with Data Layer Content Moderation

How we built a low-code application for straight-through processing of insurance claims in a week

Demo App

Modeling Insurance Claims

Adding Declarative States

Straight Through Processing Actions and the UI

Conclusion

Messing around with GraphQL queries with a critical asset management dataset

The Content Revolution

Building the Headless Content Management System of the Future

CI/CD for Data

1. I branch from main with a change request branch which I name dev. Initially we share a commit c0.

3. A computer programme sees this change request update and enriches my added documents, by performing named entity recognition on the text, enhancing searchability.

4. A spell checker runs on cd2 highlighting errors, which I think fixes.

Document Graphs

Empowering Cybernetic Cyborgs

Conclusion

Putting the Graph in GraphQL Query

GraphQL Back Links

GraphQL Path Queries

Future Directions

Data Modelling & Collaboration for Change Makers - Do Good With DFRNT

What is DFRNT and who is it for?

DFRNT for Business

The Need for DFRNT

Where TerminusDB fits in

Get started with DFRNT

A look ahead to our open-source headless content and knowledge management system

A brief history about how we got here

Standard headless CMS features

Features for composable architectures and knowledge management

What are the ideal use cases for TerminusCMS?

2022 - A Year In Review

Community and Collaboration

Climate Action

Compliance

New Features and New Releases

TerminusDB CLI

TerminusDB 10.1: The Mule

More Speed with TerminusDB 10.1.5

Company and Celebrations

TerminusDB - Now with GraphQL

We’ve got more planned

Other resources that you might like

TerminusDB Internals - Part 1 - Graph Representation

Relational indexing

Graph Databases

Sparing Use of Memory

The Dictionary

The Adjacency List

The Conceptual Structure

Reversal of Fortune

Bit Indexes

Conclusion

1. I branch from main with a change request branch which I name `dev`. Initially we share a commit `c0`.