Document Open Access Logo

Boolean Tensor Decomposition for Conjunctive Queries with Negation

Authors Mahmoud Abo Khamis, Hung Q. Ngo, Dan Olteanu, Dan Suciu

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2019.21.pdf
  • Filesize: 0.65 MB
  • 19 pages

Document Identifiers

Author Details

Mahmoud Abo Khamis
  • RelationalAI, Berkeley, USA
Hung Q. Ngo
  • RelationalAI, Berkeley, USA
Dan Olteanu
  • Department of Computer Science, University of Oxford, UK
Dan Suciu
  • Department of Computer Science and Engineering, University of Washington, USA

Funding

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 682588. This project is also supported in part by NSF grants AITF-1535565 and III-1614738.

Acknowledgements

The authors would like to thank the anonymous reviewers for their suggestions that helped improve the readability of this paper.

Cite As Get BibTex

Mahmoud Abo Khamis, Hung Q. Ngo, Dan Olteanu, and Dan Suciu. Boolean Tensor Decomposition for Conjunctive Queries with Negation. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICDT.2019.21

Abstract

We propose an approach for answering conjunctive queries with negation, where the negated relations have bounded degree. Its data complexity matches that of the InsideOut and PANDA algorithms for the positive subquery of the input query and is expressed in terms of the fractional hypertree width and the submodular width respectively. Its query complexity depends on the structure of the conjunction of negated relations; in general it is exponential in the number of join variables occurring in negated relations yet it becomes polynomial for several classes of queries.
This approach relies on several contributions. We show how to rewrite queries with negation on bounded-degree relations into equivalent conjunctive queries with not-all-equal (NAE) predicates, which are a multi-dimensional analog of disequality (!=). We then generalize the known color-coding technique to conjunctions of NAE predicates and explain it via a Boolean tensor decomposition of conjunctions of NAE predicates. This decomposition can be achieved via a probabilistic construction that can be derandomized efficiently.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query processing and optimization (theory)
  • Information systems → Database query processing
Keywords
  • color-coding
  • combined complexity
  • negation
  • query evaluation

Metrics

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

Related Versions

References

  1. Mahmoud Abo Khamis, Hung Q. Ngo, Dan Olteanu, and Dan Suciu. Boolean Tensor Decomposition for Conjunctive Queries with Negation. CoRR, abs/1712.07445, 2017. URL: http://arxiv.org/abs/1712.07445.
  2. Mahmoud Abo Khamis, Hung Q. Ngo, and Atri Rudra. FAQ: Questions Asked Frequently. In PODS, pages 13-28, 2016. Google Scholar
  3. Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another? In PODS, pages 429-444, 2017. Google Scholar
  4. Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Information Theory, 38(2):509-516, 1992. Google Scholar
  5. Noga Alon and Jeong Han Kim. On the degree, size, and chromatic index of a uniform hypergraph. J. Combin. Theory Ser. A, 77(1):165-170, 1997. Google Scholar
  6. Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms, 2(2):153-177, 2006. Google Scholar
  7. Noga Alon and Joel Spencer. The Probabilistic Method. John Wiley, 1992. Google Scholar
  8. Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  9. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In CSL, pages 208-222, 2007. Google Scholar
  10. Yijia Chen and Jörg Flum. On Parameterized Path and Chordless Path Problems. In CCC, pages 250-263, 2007. Google Scholar
  11. Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In ICALP, pages 587-596, 2008. Google Scholar
  12. Ding-Zhu Du and Frank K. Hwang. Combinatorial group testing and its applications, volume 12 of Series on Applied Mathematics. World Scientific Publishing Co. Inc., second edition, 2000. Google Scholar
  13. V. Faber. Linear Hypergraph Edge Coloring. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1603.04938.
  14. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  15. Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello. Hypertree Decompositions: Questions and Answers. In PODS, pages 57-74, 2016. Google Scholar
  16. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding First-Order Properties of Nowhere Dense Graphs. J. ACM, 64(3):17:1-17:32, 2017. Google Scholar
  17. Martin Grohe and Dániel Marx. Constraint Solving via Fractional Edge Covers. ACM Trans. Alg., 11(1):4, 2014. Google Scholar
  18. Tommy R. Jensen and Bjarne Toft. Graph coloring problems. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley &Sons Inc., New York, 1995. A Wiley-Interscience Publication. Google Scholar
  19. Tamara G. Kolda and Brett W. Bader. Tensor Decompositions and Applications. SIAM Rev., 51(3):455-500, 2009. Google Scholar
  20. D. König. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann., 77:453-465, 1916. Google Scholar
  21. Paraschos Koutris, Tova Milo, Sudeepa Roy, and Dan Suciu. Answering Conjunctive Queries with Inequalities. Theory Comput. Syst., 61(1):2-30, 2017. Google Scholar
  22. Valentas Kurauskas and Katarzyna Rybarczyk. On the chromatic index of random uniform hypergraphs. SIAM J. Discrete Math., 29(1):541-558, 2015. Google Scholar
  23. Dániel Marx. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. J. ACM, 60(6):42:1-42:51, November 2013. URL: http://dx.doi.org/10.1145/2535926.
  24. Hung Q. Ngo and Ding-Zhu Du. A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening. In DIMACS, volume 55, pages 171-182. Amer. Math. Soc., 2000. Google Scholar
  25. Hung Q. Ngo, Christopher Ré, and Atri Rudra. Skew Strikes Back: New Developments in the Theory of Join Algorithms. In SIGMOD Rec., pages 5-16, 2013. Google Scholar
  26. Dan Olteanu and Jakub Závodnỳ. Size Bounds for Factorised Representations of Query Results. TODS, 40(1):2:1-2:44, 2015. Google Scholar
  27. Christos H. Papadimitriou and Mihalis Yannakakis. On the Complexity of Database Queries. J. Comput. Syst. Sci., 58(3):407-427, 1999. Google Scholar
  28. Michał Pilipczuk and Sebastian Siebertz. Sparsity. Technical report, University of Warsaw, December 2017. URL: https://www.mimuw.edu.pl/~mp248287/sparsity/.
  29. Nicholas Pippenger and Joel Spencer. Asymptotic behavior of the chromatic index for hypergraphs. J. Combin. Theory Ser. A, 51(1):24-42, 1989. Google Scholar
  30. Jürgen Plehn and Bernd Voigt. Finding Minimally Weighted Subgraphs. In Graph-Theoretic Concepts in Computer Science, pages 18-29, 1990. Google Scholar
  31. Ely Porat and Amir Rothschild. Explicit Nonadaptive Combinatorial Group Testing Schemes. IEEE Trans. Information Theory, 57(12):7982-7989, 2011. Google Scholar
  32. Luc Segoufin. Enumerating with Constant Delay the Answers to a Query. In ICDT, pages 10-20, 2013. Google Scholar
  33. Nicholas D. Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E. Papalexakis, and Christos Faloutsos. Tensor Decomposition for Signal Processing and Machine Learning. Trans. Sig. Proc., 65(13):3551-3582, 2017. Google Scholar
  34. Mihalis Yannakakis. Algorithms for Acyclic Database Schemes. In VLDB, pages 82-94, 1981. 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