Simple and Efficient Relational Querying of Software Structures

Dirk Beyer, Andreas Noack, Claus Lewerentz
Software Systems Engineering Research Group
Brandenburg Technical University at Cottbus, Germany

Many analyses of software systems can be formalized as relational queries, for
example the detection of design patterns, of patterns of problematic design, of
code clones, of dead code, and of differences between the as-built and the
as-designed architecture. This paper describes the concepts of CrocoPat, a tool
for querying and manipulating relations. CrocoPat is easy to use, because of
its simple query and manipulation language based on predicate calculus, and its
simple file format for relations. CrocoPat is efficient, because it internally
represents relations as binary decision diagrams, a data structure that is
well-known as a compact representation of large relations in computer-aided
verification. CrocoPat is general, because it manipulates not only graphs (i.e.
binary relations), but n-ary relations.