As a heavy Datalog user, here's my opinion of the paper.
Generally, my objection to this work would be that almost all "Datalog" programs they evaluate (7 programs in total) are either just SQL (i.e., they only have joins, no recursion) or they are transitive closure (i.e., they only have linear recursion). This is not Datalog. This is *provably* (one of the few things we can prove in complexity theory) a lower complexity class than Datalog. So, there is very strong reason to believe that these results do *not* translate to full Datalog. Transitive closure can be sped up arbitrarily much, compared to more complex recursion.
The authors only evaluate *one* program (out of the 7) that has complex recursion. That one is "context-sensitive program analysis" (CSPA). However:
a) the souffle version is not optimized for complex recursion, I strongly suspect it can be sped up by 2 orders of magnitude, so I really doubt the GPU speedup for this one
b) despite the name, the analysis is not "context-sensitive", but let's just say this is an oversight
c) it's still just a 10-line program, hardly representative of full Datalog.
Yannis, we would love to be in touch to help you reproduce the results--we are absolutely happy to facilitate it, and would love to chat. Sorry about the LFS storage issue--we have made the results available to your students in a private email, I believe (I see my students have responded and engaged with them).
I'm not really sure I understand the comment about TC being provably not full Datalog? For example, what is the query beyond TC that is "full" Datalog? Notice for example that the CSPA example is--while still quite small (totally trivial compared to DOOP, a massive development in souffle)--roughly ten rules (and also a widely-established benchmark appearing in other papers on similar research-prototype Datalog engines). Is the root of your concern, for example, queries that involve more complex joins? I would very much like to see the "challenge query" that you propose so that we can tackle that next. I will give you my own answer: this framework does not handle multi-way joins (and no good answer for cyclic queries--though souffle has none either) without pre-planning, is that the root of your concern?
Regarding your point of context sensitivity: the analysis is context sensitivity via method cloning--we are certainly aware that the analysis is not dynamically enumerating context-sensitive control-flow points. I agree with you that this is perhaps dishonest, but it is also a widely-established benchmark suggested by some reviewers, and Graspan is a highly-cited paper from which this dataset originates (as you know, I'm sure). That being said, we are absolutely porting large subsets of DOOP to this framework now--I am eager to see the results, and to use DOOP as a benchmark for planning large joins.
Please reach out via email, we would love to chat more: kkmicins@syr.edu. We have been highly influenced your excellent work in this area and would love to address your criticism to whatever degree you feel it is warranted.
As a heavy Datalog user, here's my opinion of the paper.
Generally, my objection to this work would be that almost all "Datalog" programs they evaluate (7 programs in total) are either just SQL (i.e., they only have joins, no recursion) or they are transitive closure (i.e., they only have linear recursion). This is not Datalog. This is *provably* (one of the few things we can prove in complexity theory) a lower complexity class than Datalog. So, there is very strong reason to believe that these results do *not* translate to full Datalog. Transitive closure can be sped up arbitrarily much, compared to more complex recursion.
The authors only evaluate *one* program (out of the 7) that has complex recursion. That one is "context-sensitive program analysis" (CSPA). However:
a) the souffle version is not optimized for complex recursion, I strongly suspect it can be sped up by 2 orders of magnitude, so I really doubt the GPU speedup for this one
b) despite the name, the analysis is not "context-sensitive", but let's just say this is an oversight
c) it's still just a 10-line program, hardly representative of full Datalog.
Methodologically, I cannot reproduce anything from this paper, at least not without talking to the authors directly. The artifact link in the paper (https://file.io/YZE8MKx12iqX) is broken already. In the repo, most of the large inputs are replaced with git lfs links and the github repo doesn't seem to serve git lfs, e.g., https://github.com/harp-lab/gdlog/blob/main/data/cspa/httpd/assign.facts
Yannis, we would love to be in touch to help you reproduce the results--we are absolutely happy to facilitate it, and would love to chat. Sorry about the LFS storage issue--we have made the results available to your students in a private email, I believe (I see my students have responded and engaged with them).
I'm not really sure I understand the comment about TC being provably not full Datalog? For example, what is the query beyond TC that is "full" Datalog? Notice for example that the CSPA example is--while still quite small (totally trivial compared to DOOP, a massive development in souffle)--roughly ten rules (and also a widely-established benchmark appearing in other papers on similar research-prototype Datalog engines). Is the root of your concern, for example, queries that involve more complex joins? I would very much like to see the "challenge query" that you propose so that we can tackle that next. I will give you my own answer: this framework does not handle multi-way joins (and no good answer for cyclic queries--though souffle has none either) without pre-planning, is that the root of your concern?
Regarding your point of context sensitivity: the analysis is context sensitivity via method cloning--we are certainly aware that the analysis is not dynamically enumerating context-sensitive control-flow points. I agree with you that this is perhaps dishonest, but it is also a widely-established benchmark suggested by some reviewers, and Graspan is a highly-cited paper from which this dataset originates (as you know, I'm sure). That being said, we are absolutely porting large subsets of DOOP to this framework now--I am eager to see the results, and to use DOOP as a benchmark for planning large joins.
Please reach out via email, we would love to chat more: kkmicins@syr.edu. We have been highly influenced your excellent work in this area and would love to address your criticism to whatever degree you feel it is warranted.