Context-Sensitive Program Analysis as Database Queries
Summary: Maps context-sensitive program analysis to a deductive-database framework: program facts stored as relations and analyses written in Datalog, compiled by bddbddb into optimized BDD programs to compactly represent ~10^14 contexts. Shows many heap/alias analyses can be expressed succinctly (PQL front-end) and executed efficiently to find real web-application security holes. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Monica S. Lam (Stanford University)
- 2. John Whaley (Stanford University)
- 3. V. Benjamin Livshits (Stanford University)
- 4. Michael C. Martin (Stanford University)
- 5. Dzintars Avots (Stanford University)
- 6. Michael Carbin (Stanford University)
- 7. Christopher Unkel (Stanford University)
BibTeX Citation
@inproceedings{lam_pods05,
address = {New York, NY, USA},
series = {{PODS} '05},
title = {{Context-Sensitive Program Analysis as Database Queries}},
url = {https://dl.acm.org/doi/10.1145/1065167.1065169},
doi = {10.1145/1065167.1065169},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Lam, Monica S. and Whaley, John and Livshits, V. Benjamin and Martin, Michael C. and Avots, Dzintars and Carbin, Michael and Unkel, Christopher},
year = {2005}
}
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,985 | Querying Business Processes | 2006 | VLDB | 9.353709e-05 |
| 3,097 | Evita Raced: Metacompilation for Declarative Networks | 2008 | VLDB | 7.7619658e-05 |
| 7,079 | Adding Magic to an Optimising Datalog Compiler | 2008 | SIGMOD | 5.7090732e-05 |
| 7,390 | Querying and Monitoring Distributed Business Processes | 2008 | VLDB | 5.626643e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 16 | MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) | 1986 | PODS | 0.00060089598 |
| 1,538 | Bottom-Up Beats Top-Down For Datalog | 1989 | PODS | 0.00010446034 |
| 4,975 | Implementation of the CORAL Deductive Database System | 1993 | SIGMOD | 6.41738e-05 |
| 7,679 | Space Optimization in the Bottom-Up Evaluation of Logic Programs | 1991 | SIGMOD | 5.5684407e-05 |
| 7,680 | Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs | 1990 | VLDB | 5.5684407e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,745 | Graph Queries in a Next-Generation Datalog System | 2013 | VLDB |
| 2 | 6,752 | Modelling Non Deterministic Queries and Updates In Deductive Databases | 1988 | VLDB |
| 3 | 13,099 | Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases | 1991 | PODS |
| 4 | 6,587 | Selective Provenance for Datalog Programs Using Top-K Queries | 2015 | VLDB |
| 5 | 12,976 | Static Analysis of Intensional Databases in U-Datalog | 1996 | PODS |
| 6 | 13,281 | A Methodology of Application Program Analysis and Conversion Based on Database Semantics | 1977 | SIGMOD |
| 7 | 8,120 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD |
| 8 | 6,754 | Program Analysis for Conversion from a Navigation to a Specification Database Interface | 1983 | VLDB |
| 9 | 7,902 | Analysis Of The Context Dependency Of Codasyl Find-Statements With Application To Database Program Conversion | 1985 | SIGMOD |
| 10 | 13,558 | Towards Creating Application-Specific Database Management Systems | 2015 | CIDR |