Document Open Access Logo

Answering Conjunctive Queries with Inequalities

Authors Paraschos Koutris, Tova Milo, Sudeepa Roy, Dan Suciu

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.76.pdf
  • Filesize: 0.85 MB
  • 18 pages

Document Identifiers

Author Details

Paraschos Koutris
Tova Milo
Sudeepa Roy
Dan Suciu

Cite As Get BibTex

Paraschos Koutris, Tova Milo, Sudeepa Roy, and Dan Suciu. Answering Conjunctive Queries with Inequalities. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 76-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.ICDT.2015.76

Abstract

In this parer, we study the complexity of answering conjunctive queries (CQ) with inequalities. In particular, we compare the complexity of the query with and without inequalities. The main contribution of our work is a novel combinatorial technique that enables the use of any Select-Project-Join query plan for a given CQ without inequalities in answering the CQ with inequalities, with an additional factor in running time that only depends on the query. To achieve this, we define a new projection operator that keeps a small representation (independent of the size of the database) of the set of input tuples that map to each tuple in the output of the projection; this representation is used to evaluate all the inequalities in the query. Second, we generalize a result by Papadimitriou-Yannakakis [PODS'97] and give an alternative algorithm based on the color-coding technique [Alon, Yuster and Zwick, PODS'02] to evaluate a CQ with inequalities by using an algorithm for the CQ without inequalities. Third, we investigate the structure of the query graph, inequality graph, and the augmented query graph with inequalities, and show that even if the query and the inequality graphs have bounded treewidth, the augmented graph not only can have an unbounded treewidth but can also be NP-hard to evaluate. Further, we illustrate classes of queries and inequalities where the augmented graphs have unbounded treewidth, but the CQ with inequalities can be evaluated in poly-time. Finally, we give necessary properties and sufficient properties that allow a class of CQs to have poly-time combined complexity with respect to any inequality pattern.

Subject Classification

Keywords
  • query evaluation
  • conjunctive query
  • inequality
  • treewidth

Metrics

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

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
  2. Foto Afrati, Chen Li, and Prasenjit Mitra. Answering queries using views with arithmetic comparisons. In PODS, pages 209-220, 2002. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Color coding. In Ming-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2008. Google Scholar
  5. Albert Atserias, Martin Grohe, and Daniel Marx. Size bounds and query plans for relational joins. FOCS, pages 739-748, 2008. Google Scholar
  6. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci., 239(2):211-229, 2000. Google Scholar
  7. Marc Demange and Dominique De Werra. On some coloring problems in grids. Theor. Comput. Sci., 472:9-27, February 2013. Google Scholar
  8. Arnaud Durand and Etienne Grandjean. The complexity of acyclic conjunctive queries revisited. CoRR, abs/cs/0605008, 2006. Google Scholar
  9. Jörg Flum, Markus Frick, and Martin Grohe. Query evaluation via tree-decompositions. J. ACM, 49(6):716-752, November 2002. Google Scholar
  10. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. In PODS, pages 21-32, 1999. Google Scholar
  11. M.H. Graham. On the universal relation. Technical Report, University of Toronto, Ontario, Canada, 1979. Google Scholar
  12. Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers. In SODA, pages 289-298, 2006. Google Scholar
  13. Klaus Jansen and Petra Scheffler. Generalized coloring for tree-like graphs. Discrete Applied Mathematics, 75(2):135-155, 1997. Google Scholar
  14. Phokion G. Kolaitis, David L. Martin, and Madhukar N. Thakur. On the complexity of the containment problem for conjunctive queries with built-in predicates. In PODS, pages 197-204, 1998. Google Scholar
  15. Paraschos Koutris, Tova Milo, Sudeepa Roy, and Dan Suciu. Answering conjunctive queries with inequalities. CoRR, abs/1412.3869, 2014. Google Scholar
  16. B. Monien. How to find long paths efficiently. In G. Ausiello and M. Lucertini, editors, Analysis and Design of Algorithms for Combinatorial Problems, volume 109 of North-Holland Mathematics Studies, pages 239 - 254. North-Holland, 1985. Google Scholar
  17. Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms: [extended abstract]. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 37-48, 2012. Google Scholar
  18. Christos H. Papadimitriou and Mihalis Yannakakis. On the complexity of database queries. In PODS, pages 12-19, 1997. Google Scholar
  19. Neil Robertson and P.D Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49 - 64, 1984. Google Scholar
  20. Riccardo Rosati. The limits of querying ontologies. In ICDT, pages 164-178, 2007. Google Scholar
  21. Ron van der Meyden. The complexity of querying indefinite data about linearly ordered domains. J. Comput. Syst. Sci., 54(1):113-135, February 1997. Google Scholar
  22. Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014., pages 96-106, 2014. Google Scholar
  23. Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82-94. IEEE Computer Society, 1981. Google Scholar
  24. C.T. Yu and M. Z. Ozsoyoglu. An algorithm for tree-query membership of a distributed query. In COMPSAC, pages 306-312, 1979. Google Scholar
  25. Raphael Yuster and Uri Zwick. Finding even cycles even faster. SIAM J. Discrete Math., 10(2):209-222, 1997. 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