3 ms·

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

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
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 3y ago
  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 3y ago
    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 3y ago
mamcx 3y ago
> 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.

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

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 3y ago
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 3y ago
  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 3y ago

mamcx 3y ago

> 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.