[HN Gopher] The "missing" graph datatype already exists. It was ...
___________________________________________________________________
The "missing" graph datatype already exists. It was invented in the
'70s
Author : tylerhou
Score : 162 points
Date : 2024-03-05 17:53 UTC (5 hours ago)
(HTM) web link (tylerhou.com)
(TXT) w3m dump (tylerhou.com)
| rendaw wrote:
| 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 wrote:
| 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 wrote:
| 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/h
| tml/manual/manua...
| convolvatron wrote:
| 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 wrote:
| > 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
| chc4 wrote:
| 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/ 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 wrote:
| 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 wrote:
| 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 wrote:
| 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
| chc4 wrote:
| 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.
| riku_iki wrote:
| for someone not familiar with this topic, maybe you can
| give one/two sentences description of some usecase which
| you use this for?..
| pentaphobe wrote:
| Also notable that Rego (the language in Open Policy Agent) [1]
| is a Datalog (or heavily inspired by)
|
| It's used in various policy evaluators (unsurprisingly) around
| access management, but also for gatekeeper [2] which allows
| security teams to define constraints around kubernetes
| resources, similarly conftest [3] can do the same for terraform
|
| For a lot of simple cases it's a fair bit more complicated (and
| unfamiliar) than tailored query languages, but really shines
| for matching over a complex graph of interlinking resources and
| then evaluating Boolean logic against the matches.
|
| [1]: https://www.openpolicyagent.org/docs/latest/policy-
| language/....
|
| [2]: https://open-policy-agent.github.io/gatekeeper/website/
|
| [3]: https://www.conftest.dev/
| ChrisArchitect wrote:
| Related:
|
| _The hunt for the missing data type_ -
| https://news.ycombinator.com/item?id=39592444
| joshuamorton wrote:
| 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) is
| noted in the research paper from 2022, I think saying "datalog"
| solves all these problems seems incorrect.
| tylerhou wrote:
| 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...
|
| > But datalog has limitations, stuff as simple as weighted
| [edges]... are the realm of academic research.
|
| Weighted edges are well-supported by Souffle, which is stable
| and I would be comfortable using it in production. Souffle 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_ Souffle, 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 wrote:
| 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.
| joshuamorton wrote:
| 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.
| jvanderbot wrote:
| Well I'm only saying what the article was saying. And
| you're repeating what both articles were saying. So I think
| we're in perfect agreement?
|
| > until some necessary thing isn't supported
|
| Taking a third side, I dont think the possibility of a
| missing algorithm should remove the positives of not
| assuming a graph format apriori.
|
| What I mean is, it seems that the approach of "use a data
| representation and implement your algorithm using something
| like queries" is meant to be an argument for empowering
| graph library writers to support a wider array of inputs
| (e.g., all of them) without specifying different
| implementations for those inputs.
|
| That's cool. Maybe I misunderstood what you said.
| joshuamorton wrote:
| > What I mean is, it seems that the approach of "use a
| data representation and implement your algorithm using
| something like queries" is meant to be an argument for
| empowering graph library writers to support a wider array
| of inputs (e.g., all of them) without specifying
| different implementations for those inputs.
|
| I think this gets back to the thing I initially brought
| up, which is that if you take this as the guidance,
| features as simple as weighted edges jumps to the realm
| of SoTA. It's perhaps good research guidance, but that's
| not useful for me who needs to analyze a graph today.
| mamcx wrote:
| > But this doesn't actually address the graph "datatype".
|
| This is correct. What is shown is in fact a _programming
| environment_ with _query engine /optimizer_ using an internal
| DSL. That is cool, and that is something you see with Sql,
| Tensor, etc but that is a full-blown thing.
|
| Not a datatype.
| asdff wrote:
| Aren't graphs already represented through matrices?
| physicsgraph wrote:
| The original blob post [0] referenced hypergraphs and other
| more complicated structures like property graphs.
|
| [0] https://news.ycombinator.com/item?id=39592444
| michelpp wrote:
| Which can all be represented with Incidence Matrices:
|
| https://en.wikipedia.org/wiki/Incidence_matrix
| jvanderbot wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| tylerhou wrote:
| Yes, you're right that one cannot express Datalog semantics
| (and also transitive closure semantics) with just one
| "query", as queries cannot be recursive.
|
| If you view each rule as a query, however, looping over
| rules _does_ capture Datalog semantics. Furthermore, by
| optimizing over rules using the relational algebra, one can
| derive algorithms "equivalent" to traditional graph
| algorithms.
|
| (I don't think you would disagree with me; just want to
| clarify for other people who might be reading.)
| physicsgraph wrote:
| The back-and-forth exchange between blogs, each with comment
| threads on HN, is a great use of the Internet.
| benopal64 wrote:
| 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 wrote:
| 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.
| ThisIsMyAltAcct wrote:
| This ecosystem used to be called the Blogosphere
| 48864w6ui wrote:
| Especially because both blogs and HN comments can be linked to.
| graphviz wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| But only if the data is valuable enough to cover the (much)
| higher costs that come with those assumptions.
| refset wrote:
| 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
| zozbot234 wrote:
| > graph databases win on actual data layouts in disk blocks
|
| You can cluster a table to physically "fix" the data layout,
| but this of course comes with some drawbacks.
| zozbot234 wrote:
| Earlier versions of SQL did not support recursive queries
| (though there were vendor-specific extensions) so graph
| databases had a very real edge there. In fact, recent SQL
| versions have added "property-based" syntactic sugar for such
| queries to further improve ease of use.
| taeric wrote:
| 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 wrote:
| 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-u...)
| hwayne wrote:
| 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.
| michelpp wrote:
| 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_Graph...
|
| I also created an introductory video some time ago explaining the
| very basic concepts:
|
| https://www.youtube.com/watch?v=JUbXW_f03W0
| refulgentis wrote:
| 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 100x100 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)
| michelpp wrote:
| > ex. "with 100 nodes and 200 edges...If we use an adjacency
| matrix representation...we need a 100x100 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.
___________________________________________________________________
(page generated 2024-03-05 23:00 UTC)