BDD-Based Deductive Database

What is BDDBDB?

From the BDDBDB website:

bddbddb stands for BDD-Based Deductive Database It is an implementation of Datalog, a declarative programming language similar to Prolog for talking about relations. What makes bddbddb unique is that it represents the relations using binary decision diagrams (BDDs). BDDs are a data structure that can efficiently represent large relations and provide efficient set operations. This allows bddbddb to efficient represent and operate on extremely large relations - relations that are too large to represent explicitly.

We use bddbddb primarily as a tool for easily and efficiently specifying program analyses. We represent the entire program as database relations. Developing a program analysis becomes as simple as writing the specification for the analysis in a declarative style and then feeding that specification to bddbddb, which automatically transforms your specification into efficient BDD operations.

This appears to be a very impressive piece of work expressing sophisticated static analysis algorithms in a declarative programming language (datalog) and executing them over large code bases.

The BDDBDB algorithms manage to outperform even carefully hand optimized analysis!

They also provide a more user friendly (but less expressive) language "PQL" (Program Query Language) with which developers can express code patterns to search for in the database in the form of little snippets of program text that get translated into datalog queries.

Links

• http://bddbddb.sourceforge.net/

Papers

Two papers about this work have been published at PODS and PLDI. Papers attached.

-- KrisDeVolder - 07 May 2005