Design and implementation of query languages for program databases
Santanu Paul · Deep Blue (University of Michigan) · 1996
Querying and analyzing source code is an essential aspect of a variety of software engineering tasks such as program understanding, reverse engineering, and program analysis. Current source code query mechanisms seem unable to combine expressive power and query compactness within a single framework; either they are highly expressive and involve writing queries as procedural code, or they have easy user interfaces with restricted expressive power. This dissertation presents a highly expressive, applicative solution to the source code query problem by letting users express complex source code queries and views as algebraic expressions. This paradigm shift in source code query processing is achieved by the design and implementation of an algebraic source code query language (Source Code Algebra or SCA) that interfaces with an object-oriented database populated with program source code. The SCA algebraic approach offers many benefits. First, it equips its users with an expressive and compact formal query language that can handle a variety of structural and flow information in a seamless manner. Second, it offers powerful capabilities for software view generation. Third, it serves as a unifying framework for formally expressing source code queries that have traditionally been dealt in isolation by graphical, relational, or pattern-based query languages. Finally, its algebraic formalism offers opportunities for query optimization. SCA is an order-sorted algebra that has a computational power equivalent to that of relational algebra extended with generalized transitive closure and sequence operations. In addition to the algebraic query paradigm, the dissertation also explores a pattern-based query paradigm for source code using a tool called SCRUPLE. Prototype query processing systems based on SCA and SCRUPLE have been implemented and used to analyze C programs. Experimental results demonstrate that the algebraic approach to source code query and analysis combines the benefits of expressive power, compactness, and formalism within a single query language.