Document Open Access Logo

Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width

Authors Christoph Berkholz, Nicole Schweikardt

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.58.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Christoph Berkholz
  • Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany
Nicole Schweikardt
  • Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany

Funding

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - SCHW 837/5-1.

Cite As Get BibTex

Christoph Berkholz and Nicole Schweikardt. Constant Delay Enumeration with FPT-Preprocessing for Conjunctive Queries of Bounded Submodular Width. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.58

Abstract

Marx (STOC 2010, J. ACM 2013) introduced the notion of submodular width of a conjunctive query (CQ) and showed that for any class Phi of Boolean CQs of bounded submodular width, the model-checking problem for Phi on the class of all finite structures is fixed-parameter tractable (FPT). Note that for non-Boolean queries, the size of the query result may be far too large to be computed entirely within FPT time. We investigate the free-connex variant of submodular width and generalise Marx’s result to non-Boolean queries as follows: For every class Phi of CQs of bounded free-connex submodular width, within FPT-preprocessing time we can build a data structure that allows to enumerate, without repetition and with constant delay, all tuples of the query result. Our proof builds upon Marx’s splitting routine to decompose the query result into a union of results; but we have to tackle the additional technical difficulty to ensure that these can be enumerated efficiently.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Finite Model Theory
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Database theory
  • Theory of computation → Database query processing and optimization (theory)
Keywords
  • conjunctive queries
  • constant delay enumeration
  • hypertree decompositions
  • submodular width
  • fixed-parameter tractability

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. URL: http://webdam.inria.fr/Alice/.
  2. 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? CoRR, abs/1612.02503, 2016. URL: http://arxiv.org/abs/1612.02503.
  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 Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems PODS 2017, pages 429-444, 2017. URL: https://doi.org/10.1145/3034786.3056105.
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and Counting Given Length Cycles. Algorithmica, 17(3):209-223, 1997. URL: https://doi.org/10.1007/BF02523189.
  5. Antoine Amarilli, Pierre Bourhis, and Stefan Mengel. Enumeration on Trees under Relabelings. In 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, pages 5:1-5:18, 2018. URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.5.
  6. Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. Enumeration on Trees with Tractable Combined Complexity and Efficient Updates. CoRR, abs/1812.09519, 2018. URL: http://arxiv.org/abs/1812.09519.
  7. Antoine Amarilli, Pierre Bourhis, Stefan Mengel, and Matthias Niewerth. Constant-Delay Enumeration for Nondeterministic Document Spanners. In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pages 22:1-22:19, 2019. URL: https://doi.org/10.4230/LIPIcs.ICDT.2019.22.
  8. Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. In Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, pages 167-181, 2006. URL: https://doi.org/10.1007/11874683_11.
  9. Guillaume Bagan. Algorithmes et complexité des problèmes d'énumération pour l'évaluation de requêtes logiques. (Algorithms and complexity of enumeration problems for the evaluation of logical queries). PhD thesis, University of Caen Normandy, France, 2009. URL: https://tel.archives-ouvertes.fr/tel-00424232.
  10. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In Proceedings of the 16th Annual Conference of the EACSL, CSL'07, Lausanne, Switzerland, September 11-15, 2007, pages 208-222, 2007. URL: https://doi.org/10.1007/978-3-540-74915-8_18.
  11. Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the Desirability of Acyclic Database Schemes. J. ACM, 30(3):479-513, 1983. URL: https://doi.org/10.1145/2402.322389.
  12. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering Conjunctive Queries under Updates. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS'17, Chicago, IL, USA, May 14-19, 2017, pages 303-318, 2017. Full version available at http://arxiv.org/abs/1702.06370. URL: https://doi.org/10.1145/3034786.3034789.
  13. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering FO+MOD Queries Under Updates on Bounded Degree Databases. In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, volume 68 of LIPIcs, pages 8:1-8:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICDT.2017.8.
  14. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering UCQs under Updates and in the Presence of Integrity Constraints. In 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, pages 8:1-8:19, 2018. URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.8.
  15. Philip A. Bernstein and Nathan Goodman. Power of Natural Semijoins. SIAM J. Comput., 10(4):751-771, 1981. URL: https://doi.org/10.1137/0210059.
  16. Johann Brault-Baron. De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order). PhD thesis, University of Caen Normandy, France, 2013. URL: https://tel.archives-ouvertes.fr/tel-01081392.
  17. Johann Brault-Baron. Hypergraph Acyclicity Revisited. ACM Comput. Surv., 49(3):54:1-54:26, 2016. URL: https://doi.org/10.1145/2983573.
  18. Shaleen Deep and Paraschos Koutris. Compressed Representations of Conjunctive Query Results. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 307-322, 2018. URL: https://doi.org/10.1145/3196959.3196979.
  19. Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log., 8(4), 2007. URL: https://doi.org/10.1145/1276920.1276923.
  20. Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014, pages 121-131, 2014. URL: https://doi.org/10.1145/2594538.2594539.
  21. Arnaud Durand and Yann Strozecki. Enumeration Complexity of Logical Query Problems with Second-order Variables. In Computer Science Logic, 25th International Workshop / 20th Annual Conference of the EACSL, CSL 2011, September 12-15, 2011, Bergen, Norway, Proceedings, pages 189-202, 2011. URL: https://doi.org/10.4230/LIPIcs.CSL.2011.189.
  22. Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello. Hypertree Decompositions: Questions and Answers. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 57-74, 2016. URL: https://doi.org/10.1145/2902251.2902309.
  23. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree Decompositions and Tractable Queries. J. Comput. Syst. Sci., 64(3):579-627, 2002. URL: https://doi.org/10.1006/jcss.2001.1809.
  24. Martin Grohe and Dániel Marx. Constraint Solving via Fractional Edge Covers. ACM Trans. Algorithms, 11(1):4:1-4:20, 2014. URL: https://doi.org/10.1145/2636918.
  25. Muhammad Idris, Martín Ugarte, and Stijn Vansummeren. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017, pages 1259-1274, 2017. URL: https://doi.org/10.1145/3035918.3064027.
  26. Ahmet Kara and Dan Olteanu. Covers of Query Results. In 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, pages 16:1-16:22, 2018. URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.16.
  27. Wojciech Kazana and Luc Segoufin. First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science, 7(2), 2011. URL: https://doi.org/10.2168/LMCS-7(2:20)2011.
  28. Wojciech Kazana and Luc Segoufin. Enumeration of first-order queries on classes of structures with bounded expansion. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 297-308, 2013. URL: https://doi.org/10.1145/2463664.2463667.
  29. Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Trans. Comput. Log., 14(4):25:1-25:12, 2013. URL: https://doi.org/10.1145/2528928.
  30. Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12, 2017. URL: https://doi.org/10.1109/LICS.2017.8005133.
  31. Katja Losemann and Wim Martens. MSO queries on trees: enumerating answers under updates. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Vienna, Austria, July 14 - 18, 2014, pages 67:1-67:10, 2014. URL: https://doi.org/10.1145/2603088.2603137.
  32. Dániel Marx. Tractable Structures for Constraint Satisfaction with Truth Tables. Theory Comput. Syst., 48(3):444-464, 2011. URL: https://doi.org/10.1007/s00224-009-9248-9.
  33. Dániel Marx. Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. Journal of the ACM (JACM), Volume 60, Issue 6, Article No. 42, November 2013. URL: https://doi.org/10.1145/2535926.
  34. Matthias Niewerth. MSO queries on trees: Enumerating answers under updates using forest algebras. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 769-778, 2018. URL: https://doi.org/10.1145/3209108.3209144.
  35. Matthias Niewerth and Luc Segoufin. Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 179-191, 2018. URL: https://doi.org/10.1145/3196959.3196961.
  36. Dan Olteanu and Maximilian Schleich. Factorized Databases. SIGMOD Record, 45(2):5-16, 2016. URL: https://doi.org/10.1145/3003665.3003667.
  37. Dan Olteanu and Jakub Závodný. Size Bounds for Factorised Representations of Query Results. ACM Trans. Database Syst., 40(1):2:1-2:44, 2015. URL: https://doi.org/10.1145/2656335.
  38. Francesco Scarcello. From Hypertree Width to Submodular Width and Data-dependent Structural Decompositions. In Proceedings of the 26th Italian Symposium on Advanced Database Systems, Castellaneta Marina (Taranto), Italy, June 24-27, 2018., 2018. URL: http://ceur-ws.org/Vol-2161/paper24.pdf.
  39. Nicole Schweikardt, Luc Segoufin, and Alexandre Vigny. Enumeration for FO Queries over Nowhere Dense Graphs. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 151-163, 2018. URL: https://doi.org/10.1145/3196959.3196971.
  40. Luc Segoufin. Constant Delay Enumeration for Conjunctive Queries. SIGMOD Record, 44(1):10-17, 2015. URL: https://doi.org/10.1145/2783888.2783894.
  41. Luc Segoufin and Alexandre Vigny. Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion. In 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, pages 20:1-20:16, 2017. URL: https://doi.org/10.4230/LIPIcs.ICDT.2017.20.
  42. Mihalis Yannakakis. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings, 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