Document Open Access Logo

Datalog Queries Distributing over Components

Authors Tom J. Ameloot, Bas Ketsman, Frank Neven, Daniel Zinn

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.308.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

Tom J. Ameloot
Bas Ketsman
Frank Neven
Daniel Zinn

Cite As Get BibTex

Tom J. Ameloot, Bas Ketsman, Frank Neven, and Daniel Zinn. Datalog Queries Distributing over Components. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 308-323, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ICDT.2015.308

Abstract

We investigate the class D of queries that distribute over components. These are the queries that can be evaluated by taking the union of the query results over the connected components of the database instance. We show that it is undecidable whether a (positive) Datalog program distributes over components. Additionally, we show that connected Datalog with Negation (the fragment of Datalog with Negation where all rules are connected) provides an effective syntax for Datalog with Negation programs that distribute over components under the stratified as well as under the well-founded semantics. As a corollary, we obtain a simple proof for one of the main results in previous work [Zinn, Green, and Ludäscher, ICDT2012], namely, that the classic win-move query is in F_2 (a particular class of coordination-free queries).

Subject Classification

Keywords
  • Datalog
  • stratified semantics
  • well-founded semantics
  • coordination-free evaluation
  • distributed databases

Metrics

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

References

  1. S. Abiteboul, Z. Abrams, S. Haar, and T. Milo. Diagnosis of asynchronous discrete event systems: Datalog to the rescue! In PODS, pages 358-367. ACM Press, 2005. Google Scholar
  2. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
  3. P. Alvaro, N. Conway, J.M. Hellerstein, and D. Maier. Blazes: Coordination analysis for distributed programs. In IEEE 30th International Conference on Data Engineering, pages 52-63. IEEE, 2014. Google Scholar
  4. T.J. Ameloot, B. Ketsman, F. Neven, and D. Zinn. Weaker forms of monotonicity for declarative networking: A more fine-grained answer to the CALM-conjecture. In PODS, pages 64-75. ACM Press, 2014. Google Scholar
  5. T.J. Ameloot, F. Neven, and J. Van den Bussche. Relational transducers for declarative networking. J. ACM, 60(2):15:1-15:38, 2013. Google Scholar
  6. L. Cabibbo. The expressive power of stratified logic programs with value invention. Information and Computation, 147(1):22-56, 1998. Google Scholar
  7. K.J. Compton. Some useful preservation theorems. Journal of Symbolic Logic, 48:427-440, 1983. Google Scholar
  8. N. Conway, W.R. Marczak, P. Alvaro, J.M. Hellerstein, and D. Maier. Logic and lattices for distributed programming. In Proceedings of the Third ACM Symposium on Cloud Computing, pages 1:1-1:14. ACM Press, 2012. Google Scholar
  9. A. Dawar and S. Kreutzer. On Datalog vs. LFP. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pages 160-171. Springer, 2008. Google Scholar
  10. T. Feder and M.Y. Vardi. Homomorphism closed vs. existential positive. In LICS, pages 311-320. IEEE Computer Society, 2003. Google Scholar
  11. I. Guessarian. Deciding boundedness for uniformly connected datalog programs. In S. Abiteboul and P.C. Kanellakis, editors, ICDT, volume 470 of Lecture Notes in Computer Science, pages 395-405. Springer, 1990. Google Scholar
  12. J.M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record, 39(1):5-19, 2010. Google Scholar
  13. R. Hull and M. Yoshikawa. ILOG: Declarative creation and manipulation of object identifiers. In VLDB, pages 455-468. Morgan Kaufmann Publishers Inc., 1990. Google Scholar
  14. T. Jim and D. Suciu. Dynamically distributed query evaluation. In PODS, pages 28-39. ACM Press, 2001. Google Scholar
  15. D.B. Kemp, D. Srivastava, and P.J. Stuckey. Bottom-up evaluation and query optimization of well-founded models. Theor. Comput. Sci., 146(1&2):145-184, 1995. Google Scholar
  16. B.T. Loo, T. Condie, M. Garofalakis, D.E. Gay, J.M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative networking: Language, execution and optimization. In SIGMOD, pages 97-108. ACM Press, 2006. Google Scholar
  17. O. Shmueli. Equivalence of Datalog queries is undecidable. The Journal of Logic Programming, 15(3):231-241, 1993. Google Scholar
  18. A. Van Gelder. The alternating fixpoint of logic programs with negation. J. Comput. Syst. Sci., 47(1):185-221, 1993. Google Scholar
  19. D. Zinn, T.J. Green, and B. Ludäscher. Win-move is coordination-free (sometimes). In ICDT, pages 99-113. ACM Press, 2012. 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