Advanced search
1 file | 284.55 KB

Optimizing inequality joins in Datalog with approximated constraint propagation

Author
Organization
Abstract
Datalog systems evaluate joins over arithmetic (in)equalities as a naive generate-and-test of Cartesian products. We exploit aggregates in a source-to-source transformation to reduce the size of Cartesian products and to improve performance. Our approach approximates the well-known propagation technique from Constraint Programming. Experimental evaluation shows good run time speed-ups on a range of non-recursive as well as recursive programs. Furthermore, our technique improves upon the previously reported in the literature constraint magic set transformation approach.
Keywords
Logic Programming, Datalog, program transformation, LogicBlox, bounds consistency, Constraint Programming

Downloads

  • paper.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 284.55 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Campagna, Dario, Beata Sarna-Starosta, and Tom Schrijvers. 2012. “Optimizing Inequality Joins in Datalog with Approximated Constraint Propagation.” In Lecture Notes in Computer Science, ed. Claudio Russo and Neng-Fa Zhou, 7149:108–122. Heidelberg, Germany: Springer.
APA
Campagna, D., Sarna-Starosta, B., & Schrijvers, T. (2012). Optimizing inequality joins in Datalog with approximated constraint propagation. In C. Russo & N.-F. Zhou (Eds.), Lecture Notes in Computer Science (Vol. 7149, pp. 108–122). Presented at the 14th International symposium on Practical Aspects of Declarative Languages, Heidelberg, Germany: Springer.
Vancouver
1.
Campagna D, Sarna-Starosta B, Schrijvers T. Optimizing inequality joins in Datalog with approximated constraint propagation. In: Russo C, Zhou N-F, editors. Lecture Notes in Computer Science. Heidelberg, Germany: Springer; 2012. p. 108–22.
MLA
Campagna, Dario, Beata Sarna-Starosta, and Tom Schrijvers. “Optimizing Inequality Joins in Datalog with Approximated Constraint Propagation.” Lecture Notes in Computer Science. Ed. Claudio Russo & Neng-Fa Zhou. Vol. 7149. Heidelberg, Germany: Springer, 2012. 108–122. Print.
@inproceedings{1940522,
  abstract     = {Datalog systems evaluate joins over arithmetic (in)equalities as a naive generate-and-test of Cartesian products. We exploit aggregates in a source-to-source transformation to reduce the size of Cartesian products and to improve performance. Our approach approximates the well-known propagation technique from Constraint Programming.
Experimental evaluation shows good run time speed-ups on a range of non-recursive as well as recursive programs. Furthermore, our technique improves upon the previously reported in the literature constraint magic set transformation approach.},
  author       = {Campagna, Dario and Sarna-Starosta, Beata and Schrijvers, Tom},
  booktitle    = {Lecture Notes in Computer Science},
  editor       = {Russo, Claudio and Zhou, Neng-Fa},
  issn         = {0302-9743},
  keyword      = {Logic Programming,Datalog,program transformation,LogicBlox,bounds consistency,Constraint Programming},
  language     = {eng},
  location     = {Philadelphia, PA, USA},
  pages        = {108--122},
  publisher    = {Springer},
  title        = {Optimizing inequality joins in Datalog with approximated constraint propagation},
  volume       = {7149},
  year         = {2012},
}