Design and Implementation of the LogicBlox System
Thursday, January 1, 2015
The LogicBlox system aims to reduce the complexity of software development for modern applications which enhance and automate decision-making and enable their users to evolve their capabilities via a “self-service” model.
Join Processing for Graph Patterns: An Old Dog with New Tricks
Thursday, January 1, 2015
Join optimization has been dominated by Selinger-style, pairwise optimizers for decades. But, Selinger-style algorithms are asymptotically suboptimal for applications in graphic analytics. This suboptimality is one of the reasons that many have advocated supplementing relational engines with specialized graph processing engines.
Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm
Wednesday, January 1, 2014
In 2012, Ngo, Porat, R«e and Rudra (henceforth NPRR) devised a join algorithm with worst-case running time proportional to the AGM bound [8]. Our commercial database system LogicBlox employs a novel join algorithm, leapfrog triejoin, which compared conspicuously well to the NPRR algorithm in preliminary benchmarks.
Hybrid Context-Sensitivity for Points-To Analysis
Tuesday, January 1, 2013
Context sensitive points-to analysis is valuable for achieving high precision with good performance.The standard flavors of context sensitivity are call site-sensitivity (kCFA) and object-sensitivity. Combining both flavors of context-sensitivity increases precision but at an infeasibly high cost.
Worst-case Optimal Join Algorithms
Sunday, January 1, 2012
Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a new algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a natural join query in terms of the sizes of the individual relations in the body of the query
Pick Your Contexts Well: Understanding Object-Sensitivity
Saturday, January 1, 2011
Object-sensitivity has emerged as an excellent context abstraction for points-to analysis in object-oriented languages. Despite its practical success, however, object-sensitivity is poorly understood.