BDDBDDB < SPL

Tags: view all tags

---+ BDD-Based Deductive Database

---++ What is BDDBDB?

From the BDDBDB website:

<blockquote>
bddbddb stands for [[BDD]]-Based [[DeductiveDatabase.][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.
</blockquote>

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.

-- Main.KrisDeVolder - 07 May 2005

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
pdf	pldi04.pdf	r1	manage	266.5 K	2005-05-07 - 15:26	KrisDeVolder	Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams. John Whaley & Monica Lam. PLDI 2004
pdf	pods05.pdf	r1	manage	142.7 K	2005-05-07 - 15:28	KrisDeVolder	Context Sensitive Program Analysis as Database Queries. Monica Lam et. al. PODS 2005.

Raw edit | More topic actions

Topic revision: r1 - 2005-05-07 - KrisDeVolder