We recently had occasion to study and admire the join algorithm of Ngo, Porat, Ré and Rudraa (henceforth NPRR). Given bounds on the input relation sizes, the running time of NPRR is bounded by the largest possible result size, which may be determined using the fractional edge cover method. Our commercial Datalog-based system LogicBlox employs a novel join algorithm (leapfrog triejoin) which performs conspicuously well over diverse benchmarks; we were curious how it would compare. We establish that leapfrog triejoin is also worst-case optimal for fully conjunctive queries, and in fact satisfies a more exacting optimality criterion. Our algorithm may offer a practical competitor to NPRR, being easy to absorb, simple to implement, and having a concise optimality proof.
Leapfrog Triejoin: A Worst-case Optimal Join Algorithm
-
In LogiQL: Relating Constraint Handling Rules to Datalog
Shan Shan Huang, , Publications, 0
One of the advantages of using LogiQL is the unification of programming model such that prescriptive rules of computation...
-
Taming the Wildcards: Combining Definition- and Use-Site Variance
Shan Shan Huang, , Publications, 0
While the focus of our language work at LogicBlox is on LogiQL, a declarative query language, we do, together...
-
SecureBlox: Customizable Secure Distributed Data Processing
Shan Shan Huang, , Publications, 0
The application of Datalog to the area of security, both in analysis and in the specification of rules, has...
-
Simulation of Database-valued Markov Chains Using SimSQL
Shan Shan Huang, , Publications, 0
Congratulations to LogicBlox team member Zografoula Vagena on her recent publication in SIGMOD 2013, the premier international conference in...
-
Automated Test Input Generation for Software That Consumes ORM Models
Shan Shan Huang, , Publications, 0
Abstract Software tools that analyze and generate code from ORM conceptual schemas are highly susceptible to feature interaction bugs....
-
More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets
Shan Shan Huang, , Publications, 0
Congratulations to LogicBlox team member Tuncay Tekle and academic collaborator Yanhong (Annie) Liu on the acceptance of their paper...
-
Exception Analysis and Points-to Analysis: Better Together
Shan Shan Huang, , Publications, 0
In this ISSTA 2009 publication, LogicBlox team member Martin Bravenboer and academic collaborator Yannis Smaragdakis write about how Doop,...
-
Scalable Analysis of Conceptual Data Models
Shan Shan Huang, , Publications, 0
Abstract Conceptual data models describe information systems without the burden of implementation details, and are increasingly used to generate...