Document Open Access Logo

A Pattern Calculus for Rule Languages: Expressiveness, Compilation, and Mechanization

Authors Avraham Shinnar, Jérôme Siméon, Martin Hirzel

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2015.542.pdf
  • Filesize: 0.76 MB
  • 26 pages

Document Identifiers

Author Details

Avraham Shinnar
Jérôme Siméon
Martin Hirzel

Cite As Get BibTex

Avraham Shinnar, Jérôme Siméon, and Martin Hirzel. A Pattern Calculus for Rule Languages: Expressiveness, Compilation, and Mechanization. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 542-567, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ECOOP.2015.542

Abstract

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 of 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 CAMP and NRA is NP-complete. CAMP and its correspondence to NRA provide the foundations for efficient implementations of rules languages using databases technologies.

Subject Classification

Keywords
  • Rules
  • Pattern Matching
  • Aggregation
  • Nested Queries
  • Mechanization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Serge Abiteboul and Catriel Beeri. The power of languages for the manipulation of complex values. Journal on Very Large Data Bases (VLDB J.), 4(4):727-794, 1995. Google Scholar
  2. Serge Abiteboul and Stephane Grumbach. COL: A logic-based language for complex objects. In Extending Database Technology (EDBT), pages 271-293, 1988. Google Scholar
  3. Serge Abiteboul and Richard Hull. Data functions, Datalog and negation. In International Conference on Management of Data (SIGMOD), pages 143-153, 1988. Google Scholar
  4. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases. Addison-Wesley, 1995. Google Scholar
  5. Michal Bali. Drools JBoss Rules 5.0 Developer’s Guide. Packt Publishing, 2009. Google Scholar
  6. Catriel Beeri and Yoram Kornatzky. Algebraic optimization of object-oriented query languages. Theoretical Computer Science, 116(1&2):59-94, 1993. Google Scholar
  7. Véronique Benzaken, Evelyne Contejean, and Stefania Dumbrava. A Coq formalization of the relational data model. In European Symposium on Programming (ESOP), pages 189-208, 2014. Google Scholar
  8. K. Beyer, V. Ercegovac, R. Gemulla, A. Balmin, M. Eltabakh, C-C. Kanne, F. Özcan, and E. Shekita. Jaql: A scripting language for large scale semistructured data analysis. In Conference on Very Large Data Bases (VLDB), pages 1272-1283, 2011. Google Scholar
  9. Bard Bloom and Martin Hirzel. Robust scripting via patterns. In Dynamic Languages Symposium (DLS), pages 29-40, 2012. Google Scholar
  10. Federico Cabitza, Marcello Sarini, and Bemardo Dal Seno. DJess - a context-sharing middleware to deploy distributed inference systems in pervasive computing domains. In International Conference on Pervasive Services (ICPS), pages 229-238, 2005. Google Scholar
  11. James Cheney, Sam Lindley, and Philip Wadler. A practical theory of language-integrated query. In International Conference on Functional Programming (ICFP), pages 403-416, 2013. Google Scholar
  12. James Cheney and Christian Urban. Mechanizing the metatheory of mini-XQuery. In Conference on Certified Programs and Proofs (CPP), pages 280-295, 2011. Google Scholar
  13. William F. Clocksin and Christopher S. Mellish. Programming in PROLOG. Springer, 1987. Google Scholar
  14. Sophie Cluet and Guido Moerkotte. Nested queries in object bases. In Workshop on Database Programming Languages (DBPL), pages 226-242, 1993. Google Scholar
  15. Mariano P. Consens and Alberto O. Mendelzon. Low complexity aggregation in GraphLog and Datalog. In International Conference on Database Theory (ICDT), pages 379-394, 1990. Google Scholar
  16. Coq reference manual, version 8.4pl41. URL: http://coq.inria.fr/.
  17. Oege de Moor, Damien Sereni, Pavel Avgustinov, and Mathieu Verbaere. Type inference for Datalog and its application to query optimisation. In Principles of Database Systems (PODS), pages 291-300, 2008. Google Scholar
  18. Miki Enoki, Jérôme Siméon, Hiroshi Horii, and Martin Hirzel. Event processing over a distributed JSON store: Design and performance. In Web Information System Engineering (WISE), pages 395-404, 2014. Google Scholar
  19. Charles L. Forgy. OPS5 user’s manual. Technical Report 2397, CMU, 1981. Google Scholar
  20. Charles L. Forgy. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence, 19:17-37, 1982. Google Scholar
  21. Timothy Griffin and Leonid Libkin. Incremental maintenance of views with duplicates. In International Conference on Management of Data (SIGMOD), pages 328-339, 1995. Google Scholar
  22. Torsten Grust, Manuel Mayr, Jan Rittinger, and Tom Schreiber. Ferry: Database-supported program execution. In International Conference on Management of Data (SIGMOD), pages 1063-1066, 2009. Google Scholar
  23. Martin Hirzel, Nathaniel Nystrom, Bard Bloom, and Jan Vitek. Matchete: Paths through the pattern matching jungle. In Practical Aspects of Declarative Languages (PADL), pages 150-166, 2008. Google Scholar
  24. IBM WebSphere ILOG JRules BRMS. URL: http://www.ibm.com/software/integration/business-rule-management/jrules-family/.
  25. Jed Liu and Andrew C. Myers. JMatch: Iterable abstract pattern matching for Java. In Practical Aspects of Declarative Languages (PADL), pages 110-127, 2003. Google Scholar
  26. J. Gregory Malecha, Greg Morrisett, Avraham Shinnar, and Ryan Wisnesky. Toward a verified relational database management system. In Principles of Programming Languages (POPL), 2010. Google Scholar
  27. N. May, S. Helmer, and G. Moerkotte. Strategies for query unnesting in XML databases. Transactions on Database Systems (TODS), 31(3):968-1013, 2006. Google Scholar
  28. Inderpal Singh Mumick, Hamid Pirahesh, and Raghu Ramakrishnan. The magic of duplicates and aggregates. In Conference on Very Large Data Bases (VLDB), pages 264-277, 1990. Google Scholar
  29. IBM Operational Decision Manager: Decision Server Insights. URL: http://www.ibm.com/support/knowledgecenter/SSQP76_8.7.0.
  30. Dana Petcu. Parallel Jess. In International Symposium on Parallel and Distributed Computing (ISPDC), pages 307-316, 2005. Google Scholar
  31. Christopher Re, Jérôme Siméon, and Mary Fernandez. A complete and efficient algebraic compiler for XQuery. In International Conference on Data Engineering (ICDE), 2006. Google Scholar
  32. Damien Sereni, Pavel Avgustinov, and Oege de Moor. Adding magic to an optimising datalog compiler. In International Conference on Management of Data (SIGMOD), pages 553-566, 2008. Google Scholar
  33. Ambuj Shatdal and Jeffrey F. Naughton. Adaptive parallel aggregation algorithms. In International Conference on Management of Data (SIGMOD), pages 104-114, New York, NY, USA, 1995. Google Scholar
  34. Val Tannen, Peter Buneman, and Limsoon Wong. Naturally embedded query languages. In International Conference on Database Theory (ICDT), pages 140-154, 1992. Google Scholar
  35. Jan Van den Bussche and Stijn Vansummeren. Polymorphic type inference for the named nested relational calculus. Transactions on Computational Logic (TOCL), 9(1), 2007. Google Scholar
  36. Eelco Visser. Stratego: A language for program transformation based on rewriting strategies. In Rewriting Techniques and Applications (RTA), pages 357-362, 2001. Google Scholar
  37. Philip Wadler. Views: A way for pattern matching to cohabit with data abstraction. In Principles of Programming Languages (POPL), pages 307-313, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact