Datalog, a much older language than SPARQL or Cypher, arose from academic research in the 1980s. It is less well-known among software engineers and not widely supported in mainstream databases, but it ought to be better known since it is a very expressive language that is especially powerful for complex queries. Several niche databases, including Datomic, LogicBlox, CozoDB, and LinkedIn’s LIquid, use Datalog as their query language. It’s based on a relational data model, not a graph, but we discuss it here because recursive queries on graphs are a particular strength of Datalog.
The contents of a Datalog database are known as facts, and each fact corresponds to a row in a relational table. For example, say we have a location table containing locations, and it has three columns: ID, name, and type. The fact that the US is a country could then be written as location(2, "United States", "country"), where 2 is the ID of the US. In general, the statement table(val1, val2, …) means that table contains a row where the first column contains val1, the second column contains val2, and so on.
Example 3-11 shows how to write the data from the lefthand side of Figure 3-6 in Datalog. The edges of the graph (within, born_in, and lives_in) are represented as two-column join tables. For example, Lucy has the ID 100 and Idaho has the ID 3, so the relationship “Lucy was born in Idaho” is represented as born_in(100, 3).
Example 3-11. A subset of the data in Figure 3-6, represented as Datalog facts
location(1, "North America", "continent").
location(2, "United States", "country").
location(3, "Idaho", "state").
within(2, 1). /* US is in North America */
within(3, 2). /* Idaho is in the US */
person(100, "Lucy").
born_in(100, 3). /* Lucy was born in Idaho */
Now that we have defined the data, we can write the same query as before as shown in Example 3-12. It looks a bit different from the equivalent in Cypher or SPARQL, but don’t let that put you off. Datalog is a subset of Prolog, a programming language that you might have seen before if you’ve studied computer science.
Example 3-12. The same query as Example 3-5, expressed in Datalog
within_recursive(LocID, PlaceName) :- location(LocID, PlaceName, _). /* Rule 1 */
within_recursive(LocID, PlaceName) :- within(LocID, ViaID), /* Rule 2 */
within_recursive(ViaID, PlaceName).
migrated(PName, BornIn, LivingIn) :- person(PersonID, PName), /* Rule 3 */
born_in(PersonID, BornID),
within_recursive(BornID, BornIn),
lives_in(PersonID, LivingID),
within_recursive(LivingID, LivingIn).
us_to_europe(Person) :- migrated(Person, "United States", "Europe"). /* Rule 4 */
/* us_to_europe contains the row "Lucy". */
Cypher and SPARQL jump in right away with SELECT, but Datalog takes a small step at a time. We define rules that derive new virtual tables from the underlying facts. These derived tables are like (virtual) SQL views: they are not stored in the database, but you can query them in the same way as a table containing stored facts.
In Example 3-12 we define three derived tables: within_recursive, migrated, and us_to_europe. The names and columns of the virtual tables are defined by what appears before the:- symbol in each rule. For example, migrated(PName, BornIn, LivingIn) is a virtual table with three columns: the name of a person, the name of the place where they were born, and the name of the place where they are living.
The content of a virtual table is defined by the part of the rule after the:- symbol, where we try to find rows that match a certain pattern in the tables. For example, person(PersonID, PName) matches the row person(100, "Lucy"), with the variable PersonID bound to the value 100 and the variable PName bound to the value "Lucy". A rule applies if the system can find a match for all patterns on the righthand side of the:- operator. When the rule applies, it’s as though the lefthand side of the:- was added to the database (with variables replaced by the values they matched).
One possible way of applying the rules is thus (as illustrated in Figure 3-7):
-
location(1, "North America", "continent") exists in the database, so rule 1 applies. It generates within_recursive(1, "North America").
-
within(2, 1) exists in the database and the previous step generated within_recursive(1, "North America"), so rule 2 applies. It generates within_recursive(2, "North America").
-
within(3, 2) exists in the database and the previous step generated within_recursive(2, "North America"), so rule 2 applies. It generates within_recursive(3, "North America").
By repeated application of rules 1 and 2, the within_recursive virtual table can tell us all the locations in North America (or any other location) contained in our database.
Diagram illustrating the recursive application of rules to determine that Idaho is in North America, showing changes in the
within_recursivetable through different stages of rule application.
Figure 3-7. Determining that Idaho is in North America, using the Datalog rules from Example 3-12
Now rule 3 can find people who were born in some location BornIn and live in some location LivingIn. Rule 4 invokes rule 3 with BornIn = 'United States' and LivingIn = 'Europe' and returns only the names of the people who match the search. By querying the contents of the virtual us_to_europe table, the Datalog system finally gets the same answer as the earlier Cypher and SPARQL queries.
The Datalog approach requires a different kind of thinking compared to the other query languages discussed in this topic. It allows complex queries to be built up rule by rule, with one rule referring to other rules, similarly to the way that you break code into functions that call each other. Just as functions can be recursive, Datalog rules can also invoke themselves, like rule 2 in Example 3-12, which enables graph traversals in Datalog queries.