Document Open Access Logo

Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation

Authors Gaetano Geck, Bas Ketsman, Frank Neven, Thomas Schwentick

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2016.9.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Gaetano Geck
Bas Ketsman
Frank Neven
Thomas Schwentick

Cite As Get BibTex

Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick. Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICDT.2016.9

Abstract

Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query, also referred to as parallel-correctness. This paper extends the study of the complexity of parallel-correctness and its constituents, parallel-soundness and parallel-completeness, to unions of conjunctive queries with and without negation. As a by-product it is shown that the containment problem for conjunctive queries with negation is coNEXPTIME-complete.

Subject Classification

Keywords
  • Conjunctive queries
  • distributed evaluation

Metrics

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

References

  1. Foto N. Afrati, Stavros S. Cosmadakis, and Mihalis Yannakakis. On datalog vs. polynomial time. J. Comput. Syst. Sci., 51(2):177-196, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1060.
  2. Foto N. Afrati, Paraschos Koutris, Dan Suciu, and Jeffrey D. Ullman. Parallel skyline queries. In International Conference on Database Theory (ICDT 2012), pages 274-284, 2012. URL: http://dx.doi.org/10.1145/2274576.2274605.
  3. Foto N. Afrati and Jeffrey D. Ullman. Optimizing joins in a map-reduce environment. In Extending Database Technology (EDBT 2010), pages 99-110, 2010. URL: http://dx.doi.org/10.1145/1739041.1739056.
  4. Tom J. Ameloot, Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick. Parallel-correctness and transferability for conjunctive queries. In Principles of Database Systems (PODS 2015), pages 47-58. ACM, 2015. Google Scholar
  5. Tom J. Ameloot, Bas Ketsman, Frank Neven, and Daniel Zinn. Weaker forms of monotonicity for declarative networking: a more fine-grained answer to the CALM-conjecture. In Principles of Database Systems (PODS 2014), pages 64-75, 2014. Google Scholar
  6. Tom J. Ameloot, Frank Neven, and Jan Van den Bussche. Relational transducers for declarative networking. J. ACM, 60(2):15, 2013. URL: http://dx.doi.org/10.1145/2450142.2450151.
  7. Apache spark. URL: http://spark.apache.org.
  8. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Principles of Database Systems (PODS 2013), pages 273-284, 2013. Google Scholar
  9. Paul Beame, Paraschos Koutris, and Dan Suciu. Skew in parallel query processing. In Principles of Database Systems (PODS 2014), pages 212-223, 2014. Google Scholar
  10. Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Symposium on Theory of Computing (STOC 1979), pages 77-90, 1977. Google Scholar
  11. Shumo Chu, Magdalena Balazinska, and Dan Suciu. From theory to practice: Efficient join query evaluation in a parallel database system. In ACM SIGMOD Conference, pages 63-78, 2015. Google Scholar
  12. Carles Farré, Werner Nutt, Ernest Teniente, and Toni Urpí. Containment of conjunctive queries over databases with null values. In International Conference on Database Theory (ICDT 2007), pages 389-403, 2007. URL: http://dx.doi.org/10.1007/11965893_27.
  13. Sumit Ganguly, Abraham Silberschatz, and Shalom Tsur. Parallel bottom-up processing of datalog queries. J. Log. Program., 14(1&2):101-126, 1992. Google Scholar
  14. Gaetano Geck, Bas Ketsman, Frank Neven, and Thomas Schwentick. Parallel-correctness and containment for conjunctive queries with union and negation. CoRR, abs/1512.06246, 2015. URL: http://arxiv.org/abs/1512.06246.
  15. Paraschos Koutris and Dan Suciu. Parallel evaluation of conjunctive queries. In Principles of Database Systems (PODS 2011), pages 223-234, 2011. Google Scholar
  16. Alon Y. Levy and Yehoshua Sagiv. Queries independent of updates. In International Conference on Very Large Data Bases (VLDB 1993), pages 171-181, 1993. Google Scholar
  17. Marie-Laure Mugnier, Geneviève Simonet, and Michaël Thomazo. On the complexity of entailment in existential conjunctive first-order logic with atomic negation. Inf. Comput., 215:8-31, 2012. Google Scholar
  18. Christos H. Papadimitriou and Mihalis Yannakakis. A note on succinct representations of graphs. Information and Control, 71(3):181-185, 1986. URL: http://dx.doi.org/10.1016/S0019-9958(86)80009-2.
  19. Jeffrey D. Ullman. Information integration using logical views. Theoretical Computer Science, 239(2):189-210, 2000. Google Scholar
  20. Fang Wei and Georg Lausen. Containment of conjunctive queries with safe negation. In International Conference on Database Theory (ICDT 2003), pages 343-357, 2003. Google Scholar
  21. Reynold S. Xin, Josh Rosen, Matei Zaharia, Michael J. Franklin, Scott Shenker, and Ion Stoica. Shark: SQL and rich analytics at scale. In ACM SIGMOD Conference, 2013. Google Scholar
  22. Daniel Zinn, Todd J. Green, and Bertram Ludäscher. Win-move is cordination-free (sometimes). In International Conference on Database Theory (ICDT 2012), pages 99-113, 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