ECOOP 2015
Sun 5 - Fri 10 July 2015 Prague 1, Czech Republic
Fri 10 Jul 2015 10:30 - 11:00 at Bohemia - Abstraction Chair(s): Davide Ancona

This paper introduces a core calculus for pattern-matching in production rule languages: the Calculus for Aggregating Matching Patterns (CAMP). CAMP is expressive enough to capture modern rule languages such as JRules, including extensions for aggregation. We show how CAMP can be compiled into a nested-relational algebra (NRA), with only minimal extension. This paves the way for applying relational techniques to running rules over large stores. Furthermore, we show that NRA can also be compiled back to CAMP, using named nested-relational calculus (NNRC) as an intermediate step. We mechanize proofs for correctness, program size preservation, and type preservation of the translations using modern theorem-proving techniques. A corollary of the type preservation is that polymorphic type inference for both NRA and CAMP is NP-complete. CAMP and its correspondence to NRA provide the foundations for efficient implementation of rules languages using databases technologies.