Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A graph DB vs a Prolog (or miniKanren)

Recently I have been looking into graph databases like Neo4j and into logic programming in Prolog and miniKanren. From what I have learned so far, both allow specifying facts and relations between them, and also querying the resulting system for some selections. So, actually I cannot see much difference between them in that they both can be used to build a graph and query it, but using different syntax. However, they are presented as totally different kinds of software.

Except the technicality that databases maybe propose a more space-time effective storage technology, and except that tiny logic cores like miniKanren are simpler and embeddable, what is the actual difference between graph databases and logic programming languages, if they are both just a graph database + query API?

like image 718
noncom Avatar asked Mar 22 '15 09:03

noncom


2 Answers

No, logic programming as embodied by those things and neo4j are quite different.

On one level, you're right that they conceptually both amount to graph storage and graph query. But for logic programming, it's only conceptually graph query, there's no guarantee that it's actually stored that way (where with neo4j, it is).

Second, with logic programming you're usually trying to establish horn clauses that allow you to reason through lots of data. You can think of a horn clause as a simple rule, like "If a person is male, and is the direct ancestor of a biological child, that implies that person is a father". In cypher with neo4j, you would describe a graph pattern you wish to match, that results in data, e.g.:

 MATCH (p:Person)-[:father*]->(maleAncestor:Person)  RETURN maleAncestor 

This tells to traverse the graph by father relationships, and return male ancestors. In a logic programming language, you wouldn't do it this way. You might specify that a being a father of b means that a is male, and a is an ancestor of b. This would implicitly and transitively state that for all valid a/b pairings. Then you'd ask a question, "who are the male ancestors"? The programming environment would then answer that by exploiting your rules. That would have the effect of building a traversal through the data that's very similar to the cypher I specified above, but the way you go about understanding your data and building that traversal is totally different.

Logic programming languages usually work via predicate resolution. A graph query language like cypher works by a combination of pattern matching, and explicit path designation. They're very different.

like image 118
FrobberOfBits Avatar answered Sep 23 '22 05:09

FrobberOfBits


There are some very cool parallels between a graph database and logic programming. It's pretty clever that you associated the two.

However, while they are abstractly able to describe the same datasets, prolog usually operates on small datasets and performs its scans in-memory. It's not a database and certainly not suited to scale with many/most of the real-time constraints that databases run across – namely a large volume of database writes.

A language like Datomic uses a subset of prolog (Datalog) as its query language, and might be slightly more compatible with your idea, but even that is far from a Labeled Property Graph (LPG) like neo4j. A big difference is that "labeled edges" between nodes, with properties, are not (as far as I can tell) a first-order concept in anything but an LPG. Although you can describe these edges or realtionships between nodes with eg. a join-table to create many-to-many relationships, they are much more fluid in something like neo4j.

like image 36
Ryan Taylor Avatar answered Sep 23 '22 05:09

Ryan Taylor