Abstract | ||
---|---|---|
Calculating with graphs and relations has many applications in the analysis of software systems, for example, the detection of design patterns or patterns of problematic design and the computation of design metrics. These applications require an expressive query language, in particular, for the detection of graph patterns, and an efficient evaluation of the queries even for large graphs. In this paper, we introduce RML, a simple language for querying and manipulating relations based on predicate calculus, and CrocoPat, an interpreter for RML programs. RML is general because it enables the manipulation not only of graphs (i.e., binary relations), but of relations of arbitrary arity. CrocoPat executes RML programs efficiently 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. We evaluate RML by giving example programs for several software analyses and CrocoPat by comparing its performance with calculators for binary relations, a Prolog system, and a relational database management system. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1109/TSE.2005.23 | IEEE Trans. Software Eng. |
Keywords | Field | DocType |
PROLOG,binary decision diagrams,data structures,formal verification,graph theory,object-oriented programming,query languages,relational databases,reverse engineering,software metrics,systems re-engineering,Prolog system,RML,binary decision diagram,computer-aided verification,data structure,design metrics,design patterns,graph pattern,query language,relation manipulation language,relational database management system,software analysis,Index Terms- Logic programming,data structures,graph algorithms,reengineering.,reverse engineering | Programming language,Arity,Relational database,Computer science,Software analysis pattern,Software design pattern,Binary decision diagram,Software system,Theoretical computer science,Relational database management system,Software metric | Journal |
Volume | Issue | ISSN |
31 | 2 | 0098-5589 |
Citations | PageRank | References |
61 | 3.31 | 37 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dirk Beyer | 1 | 1736 | 100.85 |
Andreas Noack | 2 | 61 | 3.31 |
Claus Lewerentz | 3 | 665 | 64.65 |