Document Open Access Logo

Characterising Fixed Parameter Tractability for Query Evaluation over Guarded TGDs

Author Cristina Feier

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2022.12.pdf
  • Filesize: 0.78 MB
  • 20 pages

Document Identifiers

Author Details

Cristina Feier
  • University of Bremen, Germany

Acknowledgements

I would like to thank the reviewers for the useful comments.

Cite As Get BibTex

Cristina Feier. Characterising Fixed Parameter Tractability for Query Evaluation over Guarded TGDs. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICDT.2022.12

Abstract

We consider the parameterized complexity of evaluating Ontology Mediated Queries (OMQ) based on Guarded TGDs (GTGD) and Unions of Conjunctive Queries, in the case where relational symbols have unrestricted arity and where the parameter is the size of the OMQ. We establish exact criteria for fixed-parameter tractable (fpt) evaluation of recursively enumerable (r.e.) classes of such OMQs (under the widely held Exponential Time Hypothesis). One of the main technical tools introduced in the paper is an fpt-reduction from deciding parameterized uniform CSPs to parameterized OMQ evaluation. The reduction preserves measures known to be essential for classifying r.e. classes of parameterized uniform CSPs: submodular width (according to the well known result of Marx for unrestricted-arity schemas) and treewidth (according to the well known result of Grohe for bounded-arity schemas). As such, it can be employed to obtain hardness results for evaluation of r.e. classes of parameterized OMQs based on GTGD both in the unrestricted and in the bounded arity case. Previously, for bounded arity schemas, this has been tackled using a technique requiring full introspection into the construction employed by Grohe.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database theory
Keywords
  • omq
  • fpt evaluation
  • guarded tgds
  • unbounded arity
  • submodular width

Metrics

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

Related Versions

Supplementary Materials

References

  1. Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications, 2003. Google Scholar
  2. Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with existential variables: Walking the decidability line. Artif. Intell., 175(9-10):1620-1654, 2011. Google Scholar
  3. Pablo Barceló, Victor Dalmau, Cristina Feier, Carsten Lutz, and Andreas Pieris. The limits of efficiency for open- and closed-world query evaluation under guarded tgds. In PODS, pages 259-270, 2020. Google Scholar
  4. Pablo Barceló, Cristina Feier, Carsten Lutz, and Andreas Pieris. When is ontology-mediated querying efficient? In LICS, pages 1-13, 2019. Google Scholar
  5. Pablo Barceló, Diego Figueira, Georg Gottlob, and Andreas Pieris. Semantic optimization of conjunctive queries. J. ACM, 67(6):34:1-34:60, 2020. Google Scholar
  6. Pablo Barceló, Andreas Pieris, and Miguel Romero. Semantic optimization in tractable classes of conjunctive queries. SIGMOD Rec., 46(2):5-17, 2017. Google Scholar
  7. Christoph Berkholz and Nicole Schweikardt. Constant delay enumeration with fpt-preprocessing for conjunctive queries of bounded submodular width. In MFCS 2019, volume 138, pages 58:1-58:15, 2019. Google Scholar
  8. Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology-based data access: A study through disjunctive datalog, csp, and MMSNP. ACM Trans. Database Syst., 39(4):33:1-33:44, 2014. Google Scholar
  9. Achim Blumensath. Guarded second-order logic, spanning trees, and network flows. Logical Methods in Computer Science, 6(1), 2010. Google Scholar
  10. Pierre Bourhis, Marco Manna, Michael Morak, and Andreas Pieris. Guarded-based disjunctive tuple-generating dependencies. ACM Trans. Database Syst., 41(4):27:1-27:45, 2016. Google Scholar
  11. Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering under expressive relational constraints. J. Artif. Intell. Res., 48:115-174, 2013. Google Scholar
  12. Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. Datalog±: a unified approach to ontologies and integrity constraints. In ICDT, pages 14-30, 2009. Google Scholar
  13. Andrea Calì, Georg Gottlob, and Andreas Pieris. Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193:87-128, 2012. Google Scholar
  14. Nofar Carmeli and Markus Kröll. Enumeration Complexity of Conjunctive Queries with Functional Dependencies. In (ICDT 2018), volume 98, pages 11:1-11:17, 2018. Google Scholar
  15. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci., 239(2):211-229, 2000. Google Scholar
  16. Hubie Chen, Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler. Semantic width and the fixed-parameter tractability of constraint satisfaction problems. In Christian Bessiere, editor, IJCAI, pages 1726-1733, 2020. Google Scholar
  17. Hubie Chen and Stefan Mengel. A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries. In (ICDT 2015), volume 31, pages 110-126, 2015. Google Scholar
  18. Bruno Courcelle. The monadic second-order logic of graphs XIV: uniformly sparse graphs and edge set quantifications. Theor. Comput. Sci., 299(1-3):1-36, 2003. Google Scholar
  19. Alin Deutsch, Alan Nash, and Jeff B. Remmel. The chase revisisted. In PODS, pages 149-158, 2008. Google Scholar
  20. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: basic results. SIAM Journal on Computing, 24:873-921, 1995. Google Scholar
  21. Jan Foniok. Homomorphisms and structural properties of relational systems, 2007. URL: http://arxiv.org/abs/0710.4477.
  22. Erich Grädel. Decision procedures for guarded logics. In CADE, volume 1632, 1999. Google Scholar
  23. Erich Grädel, Colin Hirsch, and Martin Otto. Back and forth between guarded and modal logics. ACM Trans. Comput. Log., 3(3):418-463, 2002. Google Scholar
  24. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1:1-1:24, 2007. Google Scholar
  25. Stijn Heymans, Jos de Bruijn, Livia Predoiu, Cristina Feier, and Davy Van Nieuwenborgh. Guarded hybrid knowledge bases. Theory Pract. Log. Program., 8(3):411-429, 2008. Google Scholar
  26. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  27. David S. Johnson and Anthony C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci., 28(1):167-189, 1984. Google Scholar
  28. Vladimir Lifschitz. Action languages, answer sets, and planning. In APT, pages 357-374, 1999. Google Scholar
  29. David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv. Testing implications of data dependencies. ACM Trans. Database Syst., 4(4):455-469, 1979. Google Scholar
  30. Dániel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In STOC, pages 735-744, 2010. Google Scholar
  31. Riccardo Rosati. On the decidability and complexity of integrating ontologies and rules. J. Web Semant., 3(1):41-60, 2005. Google Scholar
  32. 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