7 ms·

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

335 points by tylerhou 3y ago

deleted 3y ago
[deleted]
rendaw 3y ago
Sorry, kicking things off with a tangent here. I've been seeing datalog for graph queries popping up a lot recently, but every datalog example I see looks totally different. Is it just a general concept? Or are there some actual unifying syntax features for different datalog implementations? Does saying "this uses datalog" guarantee some core functionality?
- chc4 3y ago
  Datalog is basically more of a paradigm than a single language: the "core" is just that you have Horn clauses and facts, and synthesize more facts (usually to fixedpoint) using those clauses. Everything on top is basically up to the implementation: a lot of modern Datalog implementations have lattice types, for example, so that introducing a new fact for the same subject "updates" the previous fact instead of duplicating. Or they might allow for negative clauses instead of only positive clauses, or implement the synthesizing in a way that is more efficient. But it's really up to the implementation what set of features they implement, and what syntax to use for it, since there isn't a specification or agreed upon set of features for what "Datalog" is if you say you use it.
  - refset 3y ago
    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/manualDES.html#_Toc81673921 https://www.fdi.ucm.es/profesor/fernan/des/html/manual/manua...
    - convolvatron 3y ago
      the 'verse' language by SPJ and co explores the notion that datalog semantics can be expressed using 'normal' programs in SSA form. As long as you use pure values this works out quite well. there are some convenient normal datalog abstractions like implicit union of clauses with the same name that don't map so well. I expect this is going to show up as a really popular model at some point - don't have to have two separate worlds for queries and other logic.
      - refset 3y ago
        > don't have to have two separate worlds for queries and other logic That's definitely the dream. Another point along that spectrum (from the author of Apache Calcite): https://github.com/hydromatic/morel https://github.com/hydromatic/morel
chc4 3y ago
In cybersecurity there's a startlingly large amount of Datalog: CodeQL compiles down to Datalog and runs via Souffle, Joern expresses program analysis in Datalog, there are a lot of hand-rolled rules inside companies using Datalog to compute transitive reachability of resources given an ACL, Biscuits are capabilities using Datalog-style rules instead of JWT tokens. I've used https://s-arash.github.io/ascent/ https://s-arash.github.io/ascent/ in a handful of Rust sideprojects, and it was very nice: you can treat it as a built-in graph datatype in the same way Hillel and the OP talk about, because it's a proc macro that can reuse all the rest of your Rust program datatypes and functions with your Datalog queries, instead of an entirely separate program you have to bolt on like if you want to integrate SWI-Prolog or something.
- viiiviiiviii 3y ago
  Are there people working in cybersecurity who actually use those code querying tools in their daily work? I've heard of some showcase projects that end up in blog posts and such, but everyone I've spoken to who's tried CodeQL or Joern or similar says that by the time you've figured out your query with all its edge cases, you might as well have just looked at the code and found any vulns quicker that way. And probably with a better understanding of the program too.
  - dragonwriter 3y ago
    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.
    - pentaphobe 3y ago
      Agree on inaccuracy, but I don't think that this reduces its value as much as you posit. Ultimately other forms of static analysis won't guarantee my code is good, but I still use linters. Similarly, tests (unit, integration, etc..) won't prove that nothing can go wrong - but I'm not going to stop writing them. I'd love to be using a "perfect" language which could prove my program correct at compile time, and would presumedly also make static analysis borderline magical for these use cases - but until that's an option I think there's a place for all these tools. (Beyond simply ticking compliance boxes) With all that said, false negatives are indeed a hard problem - and one not helped by large orgs having painful bureaucracy around false _positives_. Some of this appears to be the fault of tooling (need better filtration, deferral, weighting) but much of it seems a side effect of institutional silo's rather than a lack of perfect analyses. TLDR; pobody's nerfect, but more info generally better than less
ChrisArchitect 3y ago
Related: The hunt for the missing data type - https://news.ycombinator.com/item?id=39592444 https://news.ycombinator.com/item?id=39592444
joshuamorton 3y ago
But this doesn't actually address the graph "datatype". This says article basically says "use an edge list" and plug it into a very fancy library/database that may internally transform the representation and/or otherwise do magic to evaluate the graph better. And I mean like sure, but now you're just sort of burying the problem. You're saying "I've invented the one true graph library and that library will handle all the hard parts." But datalog has limitations, stuff as simple as weighted (much less graphs with non-integer annotations which require some declarative analysis) are the realm of academic research. Like, when "we don't support page rank" (https://link.springer.com/article/10.1007/s11280-021-00960-w https://link.springer.com/article/10.1007/s11280-021-00960-w) is noted in the research paper from 2022, I think saying "datalog" solves all these problems seems incorrect.
- tylerhou 3y ago
  I'm confused by your link. The part where the paper said that they don't support page rank was referencing prior work on Cog. The system that they are now presenting seems to support PageRank queries. > However, despite the high performance and declarativeness benefits of Cog, it does not support common complex data analytics, such as PageRank... We present Nexus, a Datalog evaluation system that overcomes all the aforementioned challenges. And Figure 21 shows two Datalog systems that seem to be able to run the PageRank algorithm: https://link.springer.com/article/10.1007/s11280-021-00960-w#Fig21 https://link.springer.com/article/10.1007/s11280-021-00960-w... > But datalog has limitations, stuff as simple as weighted [edges]... are the realm of academic research. Weighted edges are well-supported by Soufflé, which is stable and I would be comfortable using it in production. Soufflé also supports ADTs, so it also can augment paths with proofs in the same manner as Egglog. I used a more "research" implementation (Egglog) for the post because they have an online interactive demo. It is true that there is academic research being done on Soufflé, but there is academic research being done on e.g. Rust, and people still use Rust in production. I also explicitly say that there needs to be more research into better Datalog engines and integrating Datalog support into programming languages. ("Languages could have amazing graph support! In maybe a decade? And only after lots of research effort?")
- jvanderbot 3y ago
asdff 3y ago
Aren't graphs already represented through matrices?
- physicsgraph 3y ago
  The original blob post [0] referenced hypergraphs and other more complicated structures like property graphs. [0] https://news.ycombinator.com/item?id=39592444 https://news.ycombinator.com/item?id=39592444
  - michelpp 3y ago
    Which can all be represented with Incidence Matrices: https://en.wikipedia.org/wiki/Incidence_matrix https://en.wikipedia.org/wiki/Incidence_matrix
    - tylerhou 3y ago
      A (set) relation with N tuples is isomorphic to a N-dimensional boolean tensor. The mapping is to interpret each tuple as a coordinate in the tensor, and set the entry in that tensor to 1.
jvanderbot 3y ago
So, critically, the missing data type is still missing. TFA talks about an input specification, but actually highlights that the lack of a fixed representation for graphs is a strength, because the "computer" can optimize the representation and algorithms on the fly using something like query optimization. So it's not that the graph datatype already exists, it's that, just like the referenced article posits, there is no good representation. And rather than lament and gnash teeth, we use a neato programming / query language to turn that into a strength.
- tylerhou 3y ago
  Small nitpick: I would say that an abstract graph datatype does exist: it's a relation. I think that idea was not really properly explored by the referenced article. And the relational algebra gives us a powerful way of manipulating the abstract relational datatype, which informs efficient concrete representations.
  - odyssey7 3y ago
    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.
  - triska 3y ago
    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.
physicsgraph 3y ago
The back-and-forth exchange between blogs, each with comment threads on HN, is a great use of the Internet.
- otabdeveloper4 3y ago
  I agree, we should invent the World Wide Web again.
- benopal64 3y ago
  Seriously, so cool. I love watching my fellow nerds debate data types online. On a side note, is there a Bitter Lesson for datatypes, the way there is for algorithms?
  - WJW 3y ago
    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.
    - benopal64 3y ago
      Wow, great point! Thanks for the reply; I did not even think of hardware at the time of posting. I will look into form pointer chasing. Any good reads that you would recommend for software devs who are interested in electrical engineering or rather understanding how to build hardware?
- ThisIsMyAltAcct 3y ago
  This ecosystem used to be called the Blogosphere
- 48864w6ui 3y ago
  Especially because both blogs and HN comments can be linked to.
graphviz 3y ago
It's well understood, graphs can be conveniently represented as matrices/tables/relations, and they are equivalent to edge lists. It might be interesting to discuss to what extent did "graph databases" (you know who you are!) get a foothold because relational database platforms were slow to develop convenient notations and algebras (libraries) for working with abstract graphs. As Hou points out, there is some justifiable skepticism about the argument that graph databases are somehow intrinsically "more efficient" than relational databases for working with graphs. This would be surprising, given the obsession with optimization and performance that dominated the database community for many years, while issues like usability were a bit neglected (leaving the door open for other communities to innovate graph databases and data visualization platforms.) (Another point, don't I sometimes need both relational and graph algebras?) Because I'm looking mainly for expressive convenience (with good in-memory runtime performance) it's not enough to know that Datalog can represent any abstract graph. If I find textbook pseudocode for, say, maximum matching in graphs, or transitive closure or connected components, how hard will it be to program in the target graph programming system? I'm confident that Datalog, Recursive SQL, and Cymbal or Gremlin can all get the job done, but at what expressive cost (assuming my algorithm is not already a graph language primitive)? Will anyone still even recognize the algorithm.
- yawboakye 3y ago
  graph databases win on actual data layouts in disk blocks. trying to make relational databases ‘understand’ graphs really happens only at the query language layer. the data on disk remains optimized for relational queries. i’m not aware of any relational database shipping a storage engine optimized for graphs. if you know any, please share. thanks :)
  - wrs 3y ago
    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.
    - refset 3y ago
taeric 3y ago
Didn't mention it in the last post, but it would be interesting to see Stanford GraphBase explored in some of this discussion. It is very much "in the weeds" as it were, but the entire point is to explore the impact of a graph struct on various algorithms.
lilyball 3y ago
Interesting how this article mentions Rust, and program analysis, but completely fails to mention that Polonius, the next-generation borrow checker project for Rust, is based on datalog (source: https://blog.rust-lang.org/inside-rust/2023/10/06/polonius-update.html https://blog.rust-lang.org/inside-rust/2023/10/06/polonius-u...)
hwayne 3y ago
I'm always deeply impressed by people who can write complex, coherent essays above 2000 words with like a day of advanced notice. The "missing data type" essay was just 3000 and took me months. Show me your dark magic please.
- tylerhou 3y ago
  I'm lucky to have been surrounded by researchers who have been teaching and thinking about these ideas over the last ~6 months, so this essay has been marinating for a long time... your article just provided the necessary activation energy for me to write this all out. Thank you! Here are the researchers, in no particular order: Max Willsey (Berkeley): https://www.mwillsey.com/ https://www.mwillsey.com/ and his PL class (https://inst.eecs.berkeley.edu/~cs294-260/sp24/ https://inst.eecs.berkeley.edu/~cs294-260/sp24/) Joe Hellerstein (Berkeley): https://dsf.berkeley.edu/jmh/ https://dsf.berkeley.edu/jmh/ Dan Suciu (UW): https://homes.cs.washington.edu/~suciu/ https://homes.cs.washington.edu/~suciu/ and his DB theory class (https://berkeley-cs294-248.github.io/ https://berkeley-cs294-248.github.io/) Remy Wang (UCLA): https://remy.wang/ https://remy.wang/ Hung Ngo (relationalAI): https://hung-q-ngo.github.io/ https://hung-q-ngo.github.io/ The Hydro Project at Berkeley: https://hydro.run/ https://hydro.run/
michelpp 3y ago
In the language of Linear Algebra, the type of a graph is a sparse matrix. Adjacency matrices can express simple directed and undirected graphs, and Incidence matrices can express multi, hyper, and ubergraphs. The real power of using matrices for graphs is that you can use Linear Algebra to process them. Instead of "edge and node" thinking, LA brings the power of matrix multiplication and semirings to graph algorithms. Instead of working about edgelists, hashmaps of visited nodes, thread pools and when to fork or not to fork, by using a standard like the GraphBLAS you can just express an algorithm as a system of matrix operations, and the underlying library can choose how to run it, and on what hardware. For example, the current state of the art GraphBLAS implementation is SuiteSparse:GraphBLAS, has a JIT compiler that runs graph algorithms on a variety of CPUs and CUDA GPUs. The same sparse deep neural network inference code that is a few lines of Python can run on a chromebook all the way up to a large GPU system with no changes, the only difference is the size of the graph and the time it takes to process it. As graphs get into billions and trillions of edges, writing algorithms by hand that target different architectures gets extremely difficult and tedious. Future versions of SuiteSparse have a lot of exciting feature planned, including operation fusion and distributed processing. Retargeting hand written algorithms will be a thing of the past. One of the best parts about the GraphBLAS is that the graph really does have a "type" in the programming language sense, it's a Matrix, and the same operators and operations you expect to work are there. There is great support for both Julia and Python at the moment for beginners and data science oriented folks to dive in quickly. Here's an interesting paper on how to express centrality algorithms like PageRank and Triange Centrality (disclaimer: I am one of the paper authors): https://www.researchgate.net/publication/356707900_The_GraphBLAS_in_Julia_and_Python_the_PageRank_and_Triangle_Centralities https://www.researchgate.net/publication/356707900_The_Graph... I also created an introductory video some time ago explaining the very basic concepts: https://www.youtube.com/watch?v=JUbXW_f03W0 https://www.youtube.com/watch?v=JUbXW_f03W0
- refulgentis 3y ago
  Does it avoid the downsides of a matrix representation mentioned? The article responds to another, noting that there's inherent tradeoffs. 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." (n.b. this flattens a lot of the interesting info in both articles into 'ah, matrix!" - open to that being true but it feels unlikely)
airstrike 3y ago
As someone who's been spending an inordinate amount of time thinking about spreadsheets, their dependency graphs, linear algebra and matrices, parallel formula evaluation taking advantage of the GPU, declarative reactive programming, Elm, Flix, Rust... this conversation feels like validation that there's something to explore there but I'm also kinda losing my mind in the process...
- agumonkey 3y ago
  Usually a sign of deep learning (pun half intended)
YeGoblynQueenne 3y ago
>> The answers, of course, are yes. We already have a declarative programming language where expressing graph algorithms is extremely natural—Datalog, whose semantics are based on the relational algebra, which was developed in the 1970s. If that's true - Datalog is based on relational algebra - then I'd be very interested to see the author's reference because the way I know it Datalog is a subset of Prolog, without functions so that termination can be guaranteed, and without negation-as-failure so that it's monotonic, depending on the variant, and in any case, incomplete (because termination). For example, see: What you always wanted to know about Datalog (and never dared to ask) https://ieeexplore.ieee.org/document/43410 https://ieeexplore.ieee.org/document/43410 Which begins with: Datalog, a database query language based on the logic programming paradigm, is described. So the right abstraction to think about Datalog is logic programming, and the First Order Predicate Calculus, not the relational calculus. It's true that Datalog is used as a database query language, unlike Prolog that is a general purpose language, but that's because of the incompleteness of Datalog, which is something you probably want for a db query language, but certainly don't want for a general purpose programming language.
- YeGoblynQueenne 3y ago
  Btw, it goes without saying that if you wanted to have a general-purpose relational language then you should use Prolog, not Datalog. After all, if you use Prolog there's nothing stopping you from sticking to Datalog when you want, and only using the full power of Turing-completeness when you must. Seriously. Learn Prolog. It's a powerful language and you'll never worry about the Object-Relational Impedance-Mismatch ever again in your life. The only reason not to learn it is that you will forever be sad that you can't use it in your day job. Or you'll find one where you can, like I did.
  - deleted 3y ago
    [deleted]
  - YeGoblynQueenne 3y ago
    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.
rhelz 3y ago
Great Insight. Why do we need datalog, though? Why not just use SQL? Granted, datalog is simpler, has a strong theoretical foundation, is more secure and securable, has over 50 years of technological development, is currently wicked fast...and its opportunities for and- and or-parallelism, combined with its single-assignment variables, means that its perfect for the multicore, shared-cache chips we'll have to build to keep Moores Law going. I could go on... ....but that's all been true since the Clinton Administration. Heck, most of it was true since the Nixon administration, but NOBODY WANTS TO USE IT. I can go to my boss and persuade him to let me implement something in python rather than c++. But he wouldn't even understand what I was proposing if I argued for datalog over sql. All he wants to do is finish updating Jira so that he can go home. I can't launch into a week-long tutorial about what a Horn clause is, or why negation-by-failure is more coherent than the corner-cases which SQL's three-valued logic has... We're stuck with SQL. Fortunately, the OP's great points about using relations to implement graphs are still valid even w/o the datalog.
- philzook 3y ago
  You can without too much work transpile datalog to SQL. SQL does have such strong support that it is useful https://github.com/philzook58/snakelog https://github.com/philzook58/snakelog or perhaps just do it manually https://www.philipzucker.com/tiny-sqlite-datalog/ https://www.philipzucker.com/tiny-sqlite-datalog/
  - rhelz 3y ago
    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
zodiac 3y ago
I'm curious about graph algorithms that are "higher order" than what the article describes - e.g. how does Datalog encode the fact that two graphs (given as two relation sets) are isomorphic? How do I write a graph isomorphism algorithm in Datalog, or e.g. enumerate all graphs that have 6 vertices?
- philzook 3y ago
  This perhaps isn't what you're asking about, but a very useful thing to realize is that datalog or sql are quite useful for subgraph isomorphims aka graph patterm matching. One can compile the graph you're looking for into the rhs/query of a rule. This is probably only wise for small pattern graphs in large search target graphs. There's interesting depth here in that constraint satisfaction problems can be modeled as finding homomorphisms (I associated this line of thought with Moshe Vardi and others). Big patterns into small targets tend to look like coloring problems or SAT, whereas small patterns into big targets look like queries. Isomorphism is right in the middle. tringle(X,Y,Z) :- edge(X,Y), edge(Y,Z), edge(Z,X). square(X,Y,Z,W) :- edge(X,Y), edge(Y,Z), edge(Z,W), edge(W,X).
lmeyerov 3y ago
Datalog <> graph is classic, the points-to analysis papers were some of my first "aha"s for why it's practical If you enjoy this kind of thinking, we recently released GFQL for dataframe-native accelerated graph querying & compute that build on some of the under-the-hood insights here Imagine Neo4j Cypher, except no need for a database -- just import it -- and automatically vectorizes for significantly faster CPU+GPU performance. This is fundamentally similar to the kinds of optimized engines the article's datalog approach enables. In fact, one of our big internal questions was whether to use ~datalog syntax as the frontend! We've run it on 100M+ edge graphs in seconds on some of the cheapest GPUs you can get, and are getting ready for the next rev with aggregate compute as it's becoming more important for our community: https://github.com/graphistry/pygraphistry/blob/master/demos/more_examples/graphistry_features/hop_and_chain_graph_pattern_mining.ipynb https://github.com/graphistry/pygraphistry/blob/master/demos...
wodenokoto 3y ago
While it doesn’t refute the “missing data type” article that hit the front page yesterday I think it is a very interesting part of the discussion. But mostly I’m impressed someone read an article, thought “not quite true” and created a well written piece like this, in what? A day and a half?
utopcell 3y ago
Joins are great for OLTP workloads but are horrible for all but the simplest graph algorithms. A datalog-based system makes for a nice story, but it would not survive benchmarking. Pick a classic algorithm, say triangle counting, implement it in Datalog, compare against GBBS [1] and come back here to report results. [1] https://github.com/ParAlg/gbbs https://github.com/ParAlg/gbbs
w10-1 3y ago
Recursive queries are the killer application for datalog. As a nuts-and-bolts developer, I like <https://www.cozodb.org https://www.cozodb.org> for datalog-style data operations. It interoperates nicely with python, C, and Swift. It comes with some basic graph algorithms, data loaders, etc. I haven't found any bugs, but fair warning: it's not 1.0, and the developers seem to be pivoting to AI vector data support. Data modeling is a lot closer to NoSQL key/value stores, or FoundationDB. The append-mainly model requires maintenance compaction. I typically tokenize before putting anything into the database and never had scaling problems with large but not internet-scale uses. Explain-query is a bit opaque.
civilized 3y ago
It seems premature to worry about graphs when most languages don't even have good support for tables.
camgunz 3y ago
I love this back and forth (subscriber of Hillel Wayne; gonna bookmark this blog too)! I think the authors probably agree more than they disagree. There's probably energy around adding better graph support to mainstream languages, but I have significant doubts about whether or not Datalog will get traction there. It's really hard to get programmers to help themselves (I'm in this group FWIW--didn't use linting for waaaay too long), whether it's GC, Rust's ownership model, formal methods, flow analysis, Datalog, functional programming, blah blah. Maybe it's cultural, maybe it's some kind of deep/shared aesthetic amongst engineers, I don't know.
nh23423fefe 3y ago
nit: the turnstile expressions ⊢ are swapped in the examples body :- head should be head ⊢ body

335 points by tylerhou 3y ago

deleted 3y ago

[deleted]

Sorry, kicking things off with a tangent here. I've been seeing datalog for graph queries popping up a lot recently, but every datalog example I see looks totally different. Is it just a general concept? Or are there some actual unifying syntax features for different datalog implementations? Does saying "this uses datalog" guarantee some core functionality?

chc4 3y ago
Datalog is basically more of a paradigm than a single language: the "core" is just that you have Horn clauses and facts, and synthesize more facts (usually to fixedpoint) using those clauses. Everything on top is basically up to the implementation: a lot of modern Datalog implementations have lattice types, for example, so that introducing a new fact for the same subject "updates" the previous fact instead of duplicating. Or they might allow for negative clauses instead of only positive clauses, or implement the synthesizing in a way that is more efficient. But it's really up to the implementation what set of features they implement, and what syntax to use for it, since there isn't a specification or agreed upon set of features for what "Datalog" is if you say you use it.
- refset 3y ago
  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/manualDES.html#_Toc81673921 https://www.fdi.ucm.es/profesor/fernan/des/html/manual/manua...
  - convolvatron 3y ago
    the 'verse' language by SPJ and co explores the notion that datalog semantics can be expressed using 'normal' programs in SSA form. As long as you use pure values this works out quite well. there are some convenient normal datalog abstractions like implicit union of clauses with the same name that don't map so well. I expect this is going to show up as a really popular model at some point - don't have to have two separate worlds for queries and other logic.
    - refset 3y ago
      > don't have to have two separate worlds for queries and other logic That's definitely the dream. Another point along that spectrum (from the author of Apache Calcite): https://github.com/hydromatic/morel https://github.com/hydromatic/morel

chc4 3y ago

In cybersecurity there's a startlingly large amount of Datalog: CodeQL compiles down to Datalog and runs via Souffle, Joern expresses program analysis in Datalog, there are a lot of hand-rolled rules inside companies using Datalog to compute transitive reachability of resources given an ACL, Biscuits are capabilities using Datalog-style rules instead of JWT tokens. I've used https://s-arash.github.io/ascent/ https://s-arash.github.io/ascent/ in a handful of Rust sideprojects, and it was very nice: you can treat it as a built-in graph datatype in the same way Hillel and the OP talk about, because it's a proc macro that can reuse all the rest of your Rust program datatypes and functions with your Datalog queries, instead of an entirely separate program you have to bolt on like if you want to integrate SWI-Prolog or something.

viiiviiiviii 3y ago
Are there people working in cybersecurity who actually use those code querying tools in their daily work? I've heard of some showcase projects that end up in blog posts and such, but everyone I've spoken to who's tried CodeQL or Joern or similar says that by the time you've figured out your query with all its edge cases, you might as well have just looked at the code and found any vulns quicker that way. And probably with a better understanding of the program too.
- dragonwriter 3y ago
  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.
  - pentaphobe 3y ago
    Agree on inaccuracy, but I don't think that this reduces its value as much as you posit. Ultimately other forms of static analysis won't guarantee my code is good, but I still use linters. Similarly, tests (unit, integration, etc..) won't prove that nothing can go wrong - but I'm not going to stop writing them. I'd love to be using a "perfect" language which could prove my program correct at compile time, and would presumedly also make static analysis borderline magical for these use cases - but until that's an option I think there's a place for all these tools. (Beyond simply ticking compliance boxes) With all that said, false negatives are indeed a hard problem - and one not helped by large orgs having painful bureaucracy around false _positives_. Some of this appears to be the fault of tooling (need better filtration, deferral, weighting) but much of it seems a side effect of institutional silo's rather than a lack of perfect analyses. TLDR; pobody's nerfect, but more info generally better than less

ChrisArchitect 3y ago

Related: The hunt for the missing data type - https://news.ycombinator.com/item?id=39592444 https://news.ycombinator.com/item?id=39592444

joshuamorton 3y ago

But this doesn't actually address the graph "datatype". This says article basically says "use an edge list" and plug it into a very fancy library/database that may internally transform the representation and/or otherwise do magic to evaluate the graph better. And I mean like sure, but now you're just sort of burying the problem. You're saying "I've invented the one true graph library and that library will handle all the hard parts." But datalog has limitations, stuff as simple as weighted (much less graphs with non-integer annotations which require some declarative analysis) are the realm of academic research. Like, when "we don't support page rank" (https://link.springer.com/article/10.1007/s11280-021-00960-w https://link.springer.com/article/10.1007/s11280-021-00960-w) is noted in the research paper from 2022, I think saying "datalog" solves all these problems seems incorrect.

tylerhou 3y ago
I'm confused by your link. The part where the paper said that they don't support page rank was referencing prior work on Cog. The system that they are now presenting seems to support PageRank queries. > However, despite the high performance and declarativeness benefits of Cog, it does not support common complex data analytics, such as PageRank... We present Nexus, a Datalog evaluation system that overcomes all the aforementioned challenges. And Figure 21 shows two Datalog systems that seem to be able to run the PageRank algorithm: https://link.springer.com/article/10.1007/s11280-021-00960-w#Fig21 https://link.springer.com/article/10.1007/s11280-021-00960-w... > But datalog has limitations, stuff as simple as weighted [edges]... are the realm of academic research. Weighted edges are well-supported by Soufflé, which is stable and I would be comfortable using it in production. Soufflé also supports ADTs, so it also can augment paths with proofs in the same manner as Egglog. I used a more "research" implementation (Egglog) for the post because they have an online interactive demo. It is true that there is academic research being done on Soufflé, but there is academic research being done on e.g. Rust, and people still use Rust in production. I also explicitly say that there needs to be more research into better Datalog engines and integrating Datalog support into programming languages. ("Languages could have amazing graph support! In maybe a decade? And only after lots of research effort?")
jvanderbot 3y ago

asdff 3y ago

Aren't graphs already represented through matrices?

physicsgraph 3y ago
The original blob post [0] referenced hypergraphs and other more complicated structures like property graphs. [0] https://news.ycombinator.com/item?id=39592444 https://news.ycombinator.com/item?id=39592444
- michelpp 3y ago
  Which can all be represented with Incidence Matrices: https://en.wikipedia.org/wiki/Incidence_matrix https://en.wikipedia.org/wiki/Incidence_matrix
  - tylerhou 3y ago
    A (set) relation with N tuples is isomorphic to a N-dimensional boolean tensor. The mapping is to interpret each tuple as a coordinate in the tensor, and set the entry in that tensor to 1.

jvanderbot 3y ago

So, critically, the missing data type is still missing. TFA talks about an input specification, but actually highlights that the lack of a fixed representation for graphs is a strength, because the "computer" can optimize the representation and algorithms on the fly using something like query optimization. So it's not that the graph datatype already exists, it's that, just like the referenced article posits, there is no good representation. And rather than lament and gnash teeth, we use a neato programming / query language to turn that into a strength.

tylerhou 3y ago
Small nitpick: I would say that an abstract graph datatype does exist: it's a relation. I think that idea was not really properly explored by the referenced article. And the relational algebra gives us a powerful way of manipulating the abstract relational datatype, which informs efficient concrete representations.
- odyssey7 3y ago
  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.
- triska 3y ago
  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.

physicsgraph 3y ago

The back-and-forth exchange between blogs, each with comment threads on HN, is a great use of the Internet.

otabdeveloper4 3y ago
I agree, we should invent the World Wide Web again.
benopal64 3y ago
Seriously, so cool. I love watching my fellow nerds debate data types online. On a side note, is there a Bitter Lesson for datatypes, the way there is for algorithms?
- WJW 3y ago
  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.
  - benopal64 3y ago
    Wow, great point! Thanks for the reply; I did not even think of hardware at the time of posting. I will look into form pointer chasing. Any good reads that you would recommend for software devs who are interested in electrical engineering or rather understanding how to build hardware?
ThisIsMyAltAcct 3y ago
This ecosystem used to be called the Blogosphere
48864w6ui 3y ago
Especially because both blogs and HN comments can be linked to.

graphviz 3y ago

It's well understood, graphs can be conveniently represented as matrices/tables/relations, and they are equivalent to edge lists. It might be interesting to discuss to what extent did "graph databases" (you know who you are!) get a foothold because relational database platforms were slow to develop convenient notations and algebras (libraries) for working with abstract graphs. As Hou points out, there is some justifiable skepticism about the argument that graph databases are somehow intrinsically "more efficient" than relational databases for working with graphs. This would be surprising, given the obsession with optimization and performance that dominated the database community for many years, while issues like usability were a bit neglected (leaving the door open for other communities to innovate graph databases and data visualization platforms.) (Another point, don't I sometimes need both relational and graph algebras?) Because I'm looking mainly for expressive convenience (with good in-memory runtime performance) it's not enough to know that Datalog can represent any abstract graph. If I find textbook pseudocode for, say, maximum matching in graphs, or transitive closure or connected components, how hard will it be to program in the target graph programming system? I'm confident that Datalog, Recursive SQL, and Cymbal or Gremlin can all get the job done, but at what expressive cost (assuming my algorithm is not already a graph language primitive)? Will anyone still even recognize the algorithm.

yawboakye 3y ago
graph databases win on actual data layouts in disk blocks. trying to make relational databases ‘understand’ graphs really happens only at the query language layer. the data on disk remains optimized for relational queries. i’m not aware of any relational database shipping a storage engine optimized for graphs. if you know any, please share. thanks :)
- wrs 3y ago
  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.
  - refset 3y ago

taeric 3y ago

Didn't mention it in the last post, but it would be interesting to see Stanford GraphBase explored in some of this discussion. It is very much "in the weeds" as it were, but the entire point is to explore the impact of a graph struct on various algorithms.

lilyball 3y ago

Interesting how this article mentions Rust, and program analysis, but completely fails to mention that Polonius, the next-generation borrow checker project for Rust, is based on datalog (source: https://blog.rust-lang.org/inside-rust/2023/10/06/polonius-update.html https://blog.rust-lang.org/inside-rust/2023/10/06/polonius-u...)

hwayne 3y ago

I'm always deeply impressed by people who can write complex, coherent essays above 2000 words with like a day of advanced notice. The "missing data type" essay was just 3000 and took me months. Show me your dark magic please.

tylerhou 3y ago
I'm lucky to have been surrounded by researchers who have been teaching and thinking about these ideas over the last ~6 months, so this essay has been marinating for a long time... your article just provided the necessary activation energy for me to write this all out. Thank you! Here are the researchers, in no particular order: Max Willsey (Berkeley): https://www.mwillsey.com/ https://www.mwillsey.com/ and his PL class (https://inst.eecs.berkeley.edu/~cs294-260/sp24/ https://inst.eecs.berkeley.edu/~cs294-260/sp24/) Joe Hellerstein (Berkeley): https://dsf.berkeley.edu/jmh/ https://dsf.berkeley.edu/jmh/ Dan Suciu (UW): https://homes.cs.washington.edu/~suciu/ https://homes.cs.washington.edu/~suciu/ and his DB theory class (https://berkeley-cs294-248.github.io/ https://berkeley-cs294-248.github.io/) Remy Wang (UCLA): https://remy.wang/ https://remy.wang/ Hung Ngo (relationalAI): https://hung-q-ngo.github.io/ https://hung-q-ngo.github.io/ The Hydro Project at Berkeley: https://hydro.run/ https://hydro.run/

michelpp 3y ago

In the language of Linear Algebra, the type of a graph is a sparse matrix. Adjacency matrices can express simple directed and undirected graphs, and Incidence matrices can express multi, hyper, and ubergraphs. The real power of using matrices for graphs is that you can use Linear Algebra to process them. Instead of "edge and node" thinking, LA brings the power of matrix multiplication and semirings to graph algorithms. Instead of working about edgelists, hashmaps of visited nodes, thread pools and when to fork or not to fork, by using a standard like the GraphBLAS you can just express an algorithm as a system of matrix operations, and the underlying library can choose how to run it, and on what hardware. For example, the current state of the art GraphBLAS implementation is SuiteSparse:GraphBLAS, has a JIT compiler that runs graph algorithms on a variety of CPUs and CUDA GPUs. The same sparse deep neural network inference code that is a few lines of Python can run on a chromebook all the way up to a large GPU system with no changes, the only difference is the size of the graph and the time it takes to process it. As graphs get into billions and trillions of edges, writing algorithms by hand that target different architectures gets extremely difficult and tedious. Future versions of SuiteSparse have a lot of exciting feature planned, including operation fusion and distributed processing. Retargeting hand written algorithms will be a thing of the past. One of the best parts about the GraphBLAS is that the graph really does have a "type" in the programming language sense, it's a Matrix, and the same operators and operations you expect to work are there. There is great support for both Julia and Python at the moment for beginners and data science oriented folks to dive in quickly. Here's an interesting paper on how to express centrality algorithms like PageRank and Triange Centrality (disclaimer: I am one of the paper authors): https://www.researchgate.net/publication/356707900_The_GraphBLAS_in_Julia_and_Python_the_PageRank_and_Triangle_Centralities https://www.researchgate.net/publication/356707900_The_Graph... I also created an introductory video some time ago explaining the very basic concepts: https://www.youtube.com/watch?v=JUbXW_f03W0 https://www.youtube.com/watch?v=JUbXW_f03W0

refulgentis 3y ago
Does it avoid the downsides of a matrix representation mentioned? The article responds to another, noting that there's inherent tradeoffs. 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." (n.b. this flattens a lot of the interesting info in both articles into 'ah, matrix!" - open to that being true but it feels unlikely)

airstrike 3y ago

As someone who's been spending an inordinate amount of time thinking about spreadsheets, their dependency graphs, linear algebra and matrices, parallel formula evaluation taking advantage of the GPU, declarative reactive programming, Elm, Flix, Rust... this conversation feels like validation that there's something to explore there but I'm also kinda losing my mind in the process...

agumonkey 3y ago
Usually a sign of deep learning (pun half intended)

YeGoblynQueenne 3y ago

>> The answers, of course, are yes. We already have a declarative programming language where expressing graph algorithms is extremely natural—Datalog, whose semantics are based on the relational algebra, which was developed in the 1970s. If that's true - Datalog is based on relational algebra - then I'd be very interested to see the author's reference because the way I know it Datalog is a subset of Prolog, without functions so that termination can be guaranteed, and without negation-as-failure so that it's monotonic, depending on the variant, and in any case, incomplete (because termination). For example, see: What you always wanted to know about Datalog (and never dared to ask) https://ieeexplore.ieee.org/document/43410 https://ieeexplore.ieee.org/document/43410 Which begins with: Datalog, a database query language based on the logic programming paradigm, is described. So the right abstraction to think about Datalog is logic programming, and the First Order Predicate Calculus, not the relational calculus. It's true that Datalog is used as a database query language, unlike Prolog that is a general purpose language, but that's because of the incompleteness of Datalog, which is something you probably want for a db query language, but certainly don't want for a general purpose programming language.

YeGoblynQueenne 3y ago
Btw, it goes without saying that if you wanted to have a general-purpose relational language then you should use Prolog, not Datalog. After all, if you use Prolog there's nothing stopping you from sticking to Datalog when you want, and only using the full power of Turing-completeness when you must. Seriously. Learn Prolog. It's a powerful language and you'll never worry about the Object-Relational Impedance-Mismatch ever again in your life. The only reason not to learn it is that you will forever be sad that you can't use it in your day job. Or you'll find one where you can, like I did.
- deleted 3y ago
  [deleted]
- YeGoblynQueenne 3y ago
  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.

rhelz 3y ago

Great Insight. Why do we need datalog, though? Why not just use SQL? Granted, datalog is simpler, has a strong theoretical foundation, is more secure and securable, has over 50 years of technological development, is currently wicked fast...and its opportunities for and- and or-parallelism, combined with its single-assignment variables, means that its perfect for the multicore, shared-cache chips we'll have to build to keep Moores Law going. I could go on... ....but that's all been true since the Clinton Administration. Heck, most of it was true since the Nixon administration, but NOBODY WANTS TO USE IT. I can go to my boss and persuade him to let me implement something in python rather than c++. But he wouldn't even understand what I was proposing if I argued for datalog over sql. All he wants to do is finish updating Jira so that he can go home. I can't launch into a week-long tutorial about what a Horn clause is, or why negation-by-failure is more coherent than the corner-cases which SQL's three-valued logic has... We're stuck with SQL. Fortunately, the OP's great points about using relations to implement graphs are still valid even w/o the datalog.

philzook 3y ago
You can without too much work transpile datalog to SQL. SQL does have such strong support that it is useful https://github.com/philzook58/snakelog https://github.com/philzook58/snakelog or perhaps just do it manually https://www.philipzucker.com/tiny-sqlite-datalog/ https://www.philipzucker.com/tiny-sqlite-datalog/
- rhelz 3y ago
  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

zodiac 3y ago

I'm curious about graph algorithms that are "higher order" than what the article describes - e.g. how does Datalog encode the fact that two graphs (given as two relation sets) are isomorphic? How do I write a graph isomorphism algorithm in Datalog, or e.g. enumerate all graphs that have 6 vertices?

philzook 3y ago
This perhaps isn't what you're asking about, but a very useful thing to realize is that datalog or sql are quite useful for subgraph isomorphims aka graph patterm matching. One can compile the graph you're looking for into the rhs/query of a rule. This is probably only wise for small pattern graphs in large search target graphs. There's interesting depth here in that constraint satisfaction problems can be modeled as finding homomorphisms (I associated this line of thought with Moshe Vardi and others). Big patterns into small targets tend to look like coloring problems or SAT, whereas small patterns into big targets look like queries. Isomorphism is right in the middle. tringle(X,Y,Z) :- edge(X,Y), edge(Y,Z), edge(Z,X). square(X,Y,Z,W) :- edge(X,Y), edge(Y,Z), edge(Z,W), edge(W,X).

lmeyerov 3y ago

Datalog <> graph is classic, the points-to analysis papers were some of my first "aha"s for why it's practical If you enjoy this kind of thinking, we recently released GFQL for dataframe-native accelerated graph querying & compute that build on some of the under-the-hood insights here Imagine Neo4j Cypher, except no need for a database -- just import it -- and automatically vectorizes for significantly faster CPU+GPU performance. This is fundamentally similar to the kinds of optimized engines the article's datalog approach enables. In fact, one of our big internal questions was whether to use ~datalog syntax as the frontend! We've run it on 100M+ edge graphs in seconds on some of the cheapest GPUs you can get, and are getting ready for the next rev with aggregate compute as it's becoming more important for our community: https://github.com/graphistry/pygraphistry/blob/master/demos/more_examples/graphistry_features/hop_and_chain_graph_pattern_mining.ipynb https://github.com/graphistry/pygraphistry/blob/master/demos...

wodenokoto 3y ago

While it doesn’t refute the “missing data type” article that hit the front page yesterday I think it is a very interesting part of the discussion. But mostly I’m impressed someone read an article, thought “not quite true” and created a well written piece like this, in what? A day and a half?

utopcell 3y ago

Joins are great for OLTP workloads but are horrible for all but the simplest graph algorithms. A datalog-based system makes for a nice story, but it would not survive benchmarking. Pick a classic algorithm, say triangle counting, implement it in Datalog, compare against GBBS [1] and come back here to report results. [1] https://github.com/ParAlg/gbbs https://github.com/ParAlg/gbbs

w10-1 3y ago

Recursive queries are the killer application for datalog. As a nuts-and-bolts developer, I like <https://www.cozodb.org https://www.cozodb.org> for datalog-style data operations. It interoperates nicely with python, C, and Swift. It comes with some basic graph algorithms, data loaders, etc. I haven't found any bugs, but fair warning: it's not 1.0, and the developers seem to be pivoting to AI vector data support. Data modeling is a lot closer to NoSQL key/value stores, or FoundationDB. The append-mainly model requires maintenance compaction. I typically tokenize before putting anything into the database and never had scaling problems with large but not internet-scale uses. Explain-query is a bit opaque.

civilized 3y ago

It seems premature to worry about graphs when most languages don't even have good support for tables.

camgunz 3y ago

I love this back and forth (subscriber of Hillel Wayne; gonna bookmark this blog too)! I think the authors probably agree more than they disagree. There's probably energy around adding better graph support to mainstream languages, but I have significant doubts about whether or not Datalog will get traction there. It's really hard to get programmers to help themselves (I'm in this group FWIW--didn't use linting for waaaay too long), whether it's GC, Rust's ownership model, formal methods, flow analysis, Datalog, functional programming, blah blah. Maybe it's cultural, maybe it's some kind of deep/shared aesthetic amongst engineers, I don't know.

nh23423fefe 3y ago

nit: the turnstile expressions ⊢ are swapped in the examples body :- head should be head ⊢ body