The "missing" graph datatype already exists. It was invented in the '70s

I imagine that lots of “vulnerability detection software/SaaS” is built on that kind of tools plus queries developed for specific vulnerabilities.

OTOH, my experience with these systems has been that they are popular with enterprise ISOs, but have very high inaccuracy (lots of false positives, and lots of misses on the kind of vulns they purport to detect), and while they are marginally useful, they seem do more for security checklist compliance than for security.

Most of the time you shouldn't worry too much about all the edge cases. I mostly use it for a general query for variant analysis of some fixed bug, which will have false positives but also give you a list of actual code positions you can triage and review. You still are looking at the code, like in your case, you're just doing it faster or more confident you're looking at all the relevant code instead of having to grep and pray there isn't a construct that had an extra space somewhere. It's also useful IMO as basically just a search engine for constructs you're interested in when approaching new codebases: "show me all classes that inherit from X and have a pointer member of type Y" or whatever is really easy to query, and something that comes up surprisingly often.

On the other hand, nearly everybody’s data fits in RAM nowadays, and NVMe is so fast the disk layout constraints have changed a lot. So maybe now’s a good time to rethink anyway.

There's more potential applicability/overlap for columnar relational engines (vs. row stores) - this 2023 paper offers some useful background: https://arxiv.org/pdf/2308.08702.pdf

> The isomorphism extends to operations as well, every BFS is a matrix multiplication, and vice versa.

Can you expand on that?

I believe what they are saying is that any graph can be represented by either a matrix or edge list. So they are equivalently capable representations of graphs. The "they" refers to matrices, not graphs, when they said "and they are equivalent to edge lists". That's how I read it anyways.

GP says "graphs can be conveniently represented as matrices", which I believe is totally correct.

The GP's claim that graphs (not matrices) are equivalent to edge lists is almost correct. The textbook definition of graphs is G = (V, E) , where V are the set of vertices and E are the set of edges. Implicitly E contains relationships between some of the vertices, so the only thing in the V which isn't part of an edge in E are vertices that are not related to any edge. So if you have a connected graph, you can unambiguously define it by way of a set of edges (~= "edge lists") without explicitly mentioning the vertices.

In short, I don't see any fundamental error in GP's quoted sentence unless you're trying to be extra pedantic.

And this works great, until some necessary thing isn't supported by the language/library/black-box/datalog implementation you're using.

In reality the original (hillelwayne) article is saying that the "graph" datatype is missing, as a standard type, which is true. Imperative language implementations abstract that away to libraries, which may be graph databases (datalog being one of many), or may be more tightly coupled things like networkx for cases where you need some kind closer knit integration and custom computation.

Like, taking a step back, you're saying that no single representation is a panacea. And the original article is taking the same stance, that no single graph representation or library is a panacea, because so much is computation dependent.

Wait, what happened? There was a comment here by a user who was expressing frustration with their fist attempts to learn Prolog.

Dude, I wasn't going to be mean at you. I was going to say I get it, learning Prolog is hard and you need to understand the subject matter very deeply, in a whole other level than the usual languages we learn at uni, Python, or java, or, dunno Ada in the olden days.

Prolog's not easy to learn. But it pays off in spades for the effort.

First, thanks for the article, and the reply. I'm always happy to see logic programming-y material on HN (even if it is not labelled as such).

>> Datalog /happens/ to be a subset of Prolog syntactically, but their semantics are very different. An analogy is how LL parsers and LR parsers can both parse context free grammars, but their properties are different -- LL parsers parse from "top down" and thus will not halt on left-recursive grammars (just like Prolog) while LR parsers parse from "bottom up" and can support left-recursive grammars, at the cost of increased space.

You have to be careful when you're talking about "semantics" because there's a difference between the semantics of a language and the semantics of its execution. Like you say, Datalog is normally evaluated bottom-up, with what we call a TP Operator. If a Datalog program is evaluated top-down, like a Prolog program, then it's not guaranteed to terminate. On the flip side, Prolog is normally evaluated by SLD-Resolution, implemented as a Depth-First Search with backtracking and so it can get stuck in loops on left-recursions, as you say very correctly, but it can also be evaluated by SLG-Resolution, implemented as Breadth-First Search with memoization (a.k.a. tabling) in which case it _doesn't_ get stuck in loops on left-recursions.

In short, no I wouldn't agree that Datalog "happens" to be a subset of Prolog syntactically. That's what it is, by design. Evaluation is a different matter.

And this is where we get into the discussion of trade-offs.

>> Note that the demand transformation / magic set optimization, which is a common optimization, closes the gap between Datalog and Prolog semantically. In particular, it gives Datalog the best of both worlds: (1) increased speed, because it is not computing all possible facts, just the ones "reachable" from the query (like Prolog) and also (2) termination guarantee because all programs in the base Datalog language terminate.

Well I'm not sure whether that's right because I'm not sure what are the two "worlds" we get the best of. Efficiency is one thing. When you say that Datalog is not computing all facts, I understand this as saying it doesn't have to ground the Herbrand base of a logic program, like ASP has to, for example. True.

But the important trade-off (in my opinion anyway) is between efficiency and completeness, which is another way to look at termination guarantees, a.k.a. decidability. If a language, under some inference rule, is decidable, then it is not complete. And that's the limitation with Datalog, which comes from the fact it's a function-free language [1]. Without functions there is much you can't do. For example, function free Datalogs can't have lists, the main data structure in Prolog (other than well, "terms") because the Prolog list-constructor operator ([Head|Tail]) is a function. Without functions you can't do integer arithmetic. And so on.

I'm not sure how Datalog systems deal with those limitations (I don't really work with Datalog). I suspect they bolt-on some extra-logical system to do e.g. arithmetic, pretty much like Prolog does. In any case, the limitations of Datalog are I guess the reason it's popular as a database query language, because you don't really need arithmetic, or lists, in a database query language. But recursion, that terminates, is nice to have.

Btw, if you have a reference to the creation of Datalog older than the one I linked to, please share it. I've been trying to find the "original" datalog reference for a while and couldn't. I have no idea at this point who, exactly, came up with it, and how.

___________________

[1] Prolog is not function free, but calls its functions "terms". Which is very confusing because it also calls everything else a "term"; including constants, which it calls "atoms", and literals, i.e. atoms and negations of atoms. If you're lost, that's because you should. Prolog is a terminological atrocity.

I agree, yes. I don't think I said something that disagrees with what you say.

Probably some variation of "hardware usually influences what the optimal datatype is way more than any theoretical runtime differences". For example, B-trees for databases needing to be adapted to the block size of the underlying hardware device. Another example: As soon as you introduce any form pointer chasing to your datatype, you are often going to struggle against relatively simple array-based options because L1 cache is crazy fast compared to RAM.

Hypertext !

> ex. "with 100 nodes and 200 edges...If we use an adjacency matrix representation...we need a 100×100 matrix containing 200 ones and 9,800 zeros. If we instead use an edge list we need only 200 pairs of nodes."

The GraphBLAS is a sparse matrix library, it does not store the non-present values.

Also, a non-present value may or may not be zero. For example in shortest path algorithms, the non present value is positive infinity.

> Abstractions should be seen as models. They are always wrong, but they are sometimes useful. (And sometimes not.)

George Box was very specifically talking about statistical models when he coined that aphorism. Matrices are linear algebra and graphs are graph theory, I find it hard to think they are not correct and useful models.

> A forward traversal >v of node v enters from the left, reads the sequence stored in the node, and exits from the right. A reverse traversal <v enters from the right, reads the reverse complement of the sequence, and exits from the left.

I'm not an expert in this field but I'm guessing you're talking about De Bruijn graphs, which can be very elegantly modeled with incidence matrices, here's an example of one using the GraphBLAS that downloads data from BioPython, loads it into incidence matrices and graphs it. This is just a simple example, SuiteSparse can handle many billions of edges:

https://github.com/Graphegon/Graphony?tab=readme-ov-file#exa...

Traversing bidirectionally is quite easy, the upper triangle of a matrix are the directed outgoing edges, and the lower triangle are the incoming. This style of "push/pull" optimization is common in the GraphBLAS.

> In a good graph representation, you can do this by maintaining a small state that does not grow significantly with the length of the context or the number of underlying paths.

Again if I understand you correctly, in the GraphBLAS this is accomplished by using accumulators and masks. During traversal data can be accumulated, with a stock operator or one you define, into a vector or matrix, and that object can be used to efficiently mask subsequent computations to avoid unnecessary work or determine when you've reached a termination condition.

> Matrices don't feel like a good abstraction for graphs like this.

Mathematically, graphs and matrices are isomorphic. Regardless of algorithm or storage format like edge lists, tuples or CSR, every graph is a matrix, and vice versa. And if you have a matrix, you have linear algebra to operate on it.

Some people don't like Linear Algebra to operate on graphs, so I guess for them it is "not good", but on the other hand, it's Linear Algebra and Graph Theory, whose roots date back to the 2nd century BC, forward through great minds like Descartes and Euler, permeating every kind of math, science, physics and engineering discipline humans have ever created. That's a strong argument for its goodness.

Now it is entirely possible, likely even, that the current SuiteSparse implementation doesn't have exactly the tool needed or maybe not the precise best storage format, but these missing pieces do not invalidate the underlying mathematical foundation that it's based on.

Insightful, and reminds me of Kierkegaard:

Man is spirit. But what is spirit? Spirit is the self. But what is the self? The self is a relation which relates itself to its own self, or it is that in the relation [which accounts for it] that the relation relates itself to its own self; the self is not the relation but [consists in the fact] that the relation relates itself to its own self.

Would this specification suffice for a sentient datalog program? Or is datalog itself sentient?

You've captured my intrigue, and now I want to explore datalog, so thank you for writing the article.

Regarding relational algebra in particular: It is interesting that important and frequently needed relations on graphs cannot be expressed in relational algebra. The transitive closure of a relation is a well-known example, and as you nicely show in your article this relation can be easily and very naturally expressed in two lines of Datalog. For example, we can easily express reachability in a graph:

    reachable(V, V) :- vertex(V).     
    reachable(From, To) :-            
            arc_from_to(From, Next),  
            reachable(Next, To).      

One can show that Datalog with two very conservative and simple extensions (allowing negation of extensional database relations, and assuming a total order on the domain elements) captures the complexity class P, so can be used to decide exactly those properties of databases (and hence graphs) that are evaluable in polynomial time, a major result from descriptive complexity theory.

An example of such a property is CONNECTIVITY ("Is the graph connected?"), which can be easily expressed with Datalog on ordered databases, where we assume 3 built-in predicates (such as first/1, succ/2 and last/1) to express an ordering of domain elements:

    connected(X) :- first(X).
    connected(Y) :- connected(X), succ(X, Y), reachable(X, Y).

    connected    :- last(X), connected(X).

If such an ordering is not available via built-in predicates, then we can easily define it ourselves for any given concrete database by adding suitable facts. Also negated EDB relations can be easily defined for any database as concrete additional relations.

To add to this description, the Prolog-derived syntactic core of Datalog (the Horn clauses and facts) can be viewed as a combination of "unification" and mutually recursive rules to find a fixpoint over your data+query. It's essentially like solving simultaneous equations.

The Prolog-derived syntax is routinely extended because the core is typically too simplistic/inexpressive to be directly useful, e.g. see https://www.fdi.ucm.es/profesor/fernan/des/html/manual/manua...

Which can all be represented with Incidence Matrices:

https://en.wikipedia.org/wiki/Incidence_matrix

Interesting. I'm afraid if my boss saw me trying those out at work, he'd ask me why I'm two weeks behind, and if I told him it was the drawbacks of SQL which are holding me back and this is exactly what I needed to get back on track, he's say "you are two weeks behind because you are always getting distracted by stuff like this."

Sucks but honestly, how could I blame him for thinking that way? He--like practically every other boss on the planet-- so utterly lacks any capacity to understand what datalog brings to the table, that really, on what basis could he even make the call?

And you can't even blame him for not taking two weeks off to investigate it--new gee-whiz techniques and methodologies appear every day, most of which promise more than they can possibly deliver. If he spent all his time studying them, he'd get nothing else done.

So why should this be any different? Besides, everybody else on the planet manages to get their shit done with SQL, so just shut up and get with the program.

Uh...I'm not bitter tho...chuckle