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
-
Pick Your Contexts Well: Understanding Object-Sensitivity
Shan Shan Huang, , Publications, 0
Using Datalog for program analysis has garnered a lot of interest in the academic community in recent years. In...
-
Morphing: Structurally Shaping a Class by Reflecting on Others
Shan Shan Huang, , Publications, 0
The ability to write reusable code is important for all programming languages. LogicBlox is keen to support research in...
-
Win-move is Coordination Free… Sometimes
Shan Shan Huang, , Publications, 0
Coordination barriers are a major source of inefficiency in distributed query evaluation. Identifying queries that can be evaluated in...
-
LogicBlox, Platform and Language: a Tutorial
Shan Shan Huang, , Publications, 0
Datalog is the mathematical foundation to LogiQL, the LogicBlox query language. We here take a keen interest in fostering...
-
Algebraic Structures for Capturing the Provenance of SPARQL Queries
Shan Shan Huang, , Publications, 0
Congratulations to LogicBlox team member Grigoris Karvounarakis on his recent publication in ICDT 2013: 16thInternational Conference on Database Theory....
-
Experience Report: Using Tools and Domain Expertise to Remediate Architectural Violations in the LogicBlox Software Base
Shan Shan Huang, , Publications, 0
LogicBlox team members Kurt Stirewalt, Spencer Rugaber, David Zook, and collaborator Hwa-You Hsu wrote about their experience modeling software...
-
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...
-
Querying Data Provenance
Shan Shan Huang, , Publications, 0
Data provenance has important applications in databases, from optimization, to verifying trustworthiness of answers, to helping programmers with debugging....