Document Open Access Logo

Preserving Constraints with the Stable Chase

Authors David Carral, Markus Krötzsch, Maximilian Marx, Ana Ozaki, Sebastian Rudolph

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2018.12.pdf
  • Filesize: 0.51 MB
  • 19 pages

Document Identifiers

Author Details

David Carral
Markus Krötzsch
Maximilian Marx
Ana Ozaki
Sebastian Rudolph

Cite AsGet BibTex

David Carral, Markus Krötzsch, Maximilian Marx, Ana Ozaki, and Sebastian Rudolph. Preserving Constraints with the Stable Chase. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICDT.2018.12

Abstract

Conjunctive query answering over databases with constraints – also known as (tuple-generating) dependencies – is considered a central database task. To this end, several versions of a construction called chase have been described. Given a set Sigma of dependencies, it is interesting to ask which constraints not contained in Sigma that are initially satisfied in a given database instance are preserved when computing a chase over Sigma. Such constraints are an example for the more general class of incidental constraints, which when added to Sigma as new dependencies do not affect certain answers and might even speed up query answering. After formally introducing incidental constraints, we show that deciding incidentality is undecidable for tuple-generating dependencies, even in cases for which query entailment is decidable. For dependency sets with a finite universal model, the core chase can be used to decide incidentality. For the infinite case, we propose the stable chase, which generalises the core chase, and study its relation to incidental constraints.
Keywords
  • Incidental constraints
  • Tuple-generating dependencies
  • Infinite core chase
  • Universal Model
  • BCQ entailment

Metrics

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

References

  1. Serge Abiteboul and Richard Hull. Data functions, datalog and negation. In Proc. SIGMOD Int. Conf. on Management of Data (SIGMOD'88), pages 143-153. ACM, 1988. Google Scholar
  2. Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. Extending decidable cases for rules with existential variables. In Craig Boutilier, editor, Proc. 21st Int. Joint Conf. on Artificial Intelligence (IJCAI'09), pages 677-682. IJCAI, 2009. Google Scholar
  3. Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with existential variables: Walking the decidability line. Artificial Intelligence, 175(9-10):1620-1654, 2011. Google Scholar
  4. Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph, and Michaël Thomazo. Walking the complexity lines for generalized guarded existential rules. In Toby Walsh, editor, Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI'11), pages 712-717. AAAI Press/IJCAI, 2011. Google Scholar
  5. Bruce L. Bauslaugh. Core-like properties of infinite graphs and structures. Discrete Mathematics, 138(1):101-111, 1995. Google Scholar
  6. Bruce L. Bauslaugh. Cores and compactness of infinite directed graphs. J. of Comb. Theory Ser. B, 68(2), 1996. Google Scholar
  7. Catriel Beeri and Moshe Y. Vardi. A proof procedure for data dependencies. J. ACM, 31(4):718-741, 1984. Google Scholar
  8. Manuel Bodirsky. The core of a countably categorical structure. In Volker Diekert and Bruno Durand, editors, Proc. 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS'05), volume 3404 of Lecture Notes in Computer Science, pages 110-120. Springer, 2005. Google Scholar
  9. Pierre Bourhis, Markus Krötzsch, and Sebastian Rudolph. Reasonable highly expressive query languages. In Qiang Yang and Michael Wooldridge, editors, Proc. 24th Int. Joint Conf. on Artificial Intelligence (IJCAI'15), pages 2826-2832. AAAI Press, 2015. Google Scholar
  10. Andrea Calì, Georg Gottlob, and Andreas Pieris. Towards more expressive ontology languages: The query answering problem. J. of Artif. Intell., 193:87-128, 2012. Google Scholar
  11. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Reasoning on regular path queries. SIGMOD Record, 32(4):83-92, 2003. Google Scholar
  12. Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, and Moshe Y. Vardi. Decidable optimization problems for database logic programs (preliminary report). In Janos Simon, editor, Proc. 20th Annual ACM Symposium on Theory of Computing (STOC'88), pages 477-490. ACM, 1988. Google Scholar
  13. Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, and Zhe Wang. Acyclicity notions for existential rules and their application to query answering in ontologies. J. of Artificial Intelligence Research, 47:741-808, 2013. Google Scholar
  14. Alin Deutsch, Alan Nash, and Jeffrey B. Remmel. The chase revisited. In Maurizio Lenzerini and Domenico Lembo, editors, Proc. 27th Symposium on Principles of Database Systems (PODS'08), pages 149-158. ACM, 2008. Google Scholar
  15. Alin Deutsch and Val Tannen. Reformulation of XML queries and constraints. In Diego Calvanese, Maurizio Lenzerini, and Rajeev Motwani, editors, Proc. 9th Int. Conf. on Database Theory (ICDT'03), volume 2572 of LNCS, pages 225-241. Springer, 2003. Google Scholar
  16. Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: semantics and query answering. Theoretical Computer Science, 336(1):89-124, 2005. Google Scholar
  17. Ronald Fagin, Phokion G. Kolaitis, and Lucian Popa. Data exchange: Getting to the core. ACM Trans. Database Syst., 30(1):174-210, 2005. Google Scholar
  18. Daniela Florescu, Alon Levy, and Dan Suciu. Query containment for conjunctive queries with regular expressions. In Alberto O. Mendelzon and Jan Paredaens, editors, Proc. 17th Symposium on Principles of Database Systems (PODS'98), pages 139-148. ACM, 1998. Google Scholar
  19. Georg Gottlob and Christos H. Papadimitriou. On the complexity of single-rule datalog queries. Inf. Comput., 183(1):104-122, 2003. Google Scholar
  20. Pavol Hell and Jaroslav Nešetřil. The core of a graph. Discrete Mathematics, 109:117-126, 1992. Google Scholar
  21. Markus Krötzsch and Sebastian Rudolph. Extending decidable existential rules by joining acyclicity and guardedness. In Toby Walsh, editor, Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI'11), pages 963-968. AAAI Press/IJCAI, 2011. Google Scholar
  22. Markus Krötzsch and Veronika Thost. Ontologies for knowledge graphs: Breaking the rules. In Yolanda Gil, Elena Simperl, Paul Groth, Freddy Lecue, Markus Krötzsch, Alasdair Gray, Marta Sabou, Fabian Flöck, and Hideaki Takeda, editors, Proc. 15th Int. Semantic Web Conf. (ISWC'16), volume 9981 of LNCS, pages 376-392. Springer, 2016. Google Scholar
  23. David Maier, Alberto O. Mendelzon, and Yehoshua Sagiv. Testing implications of data dependencies. ACM Transactions on Database Systems, 4:455-469, 1979. Google Scholar
  24. Bruno Marnette. Generalized schema-mappings: from termination to tractability. In Jan Paredaens and Jianwen Su, editors, Proc. 28th Symposium on Principles of Database Systems (PODS'09), pages 13-22. ACM, 2009. Google Scholar
  25. Mariano Rodriguez-Muro, Roman Kontchakov, and Michael Zakharyaschev. Ontology-based data access: Ontop of databases. In Harith Alani, Lalana Kagal, Achille Fokoue, Paul T. Groth, Chris Biemann, Josiane Xavier Parreira, Lora Aroyo, Natasha F. Noy, Chris Welty, and Krzysztof Janowicz, editors, Proc. 12th Int. Semantic Web Conf. (ISWC'13), volume 8218 of Lecture Notes in Computer Science, pages 558-573. Springer, 2013. Google Scholar
  26. Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. MIT Press, paperback edition edition, 1987. Google Scholar
  27. Sebastian Rudolph and Markus Krötzsch. Flag & check: Data access with monadically defined queries. In Richard Hull and Wenfei Fan, editors, Proc. 32nd Symposium on Principles of Database Systems (PODS'13), pages 151-162. ACM, 2013. Google Scholar
  28. Yehoshua Sagiv. Optimizing datalog programs. In Moshe Y. Vardi, editor, Proc. Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'87), pages 349-362. ACM, 1987. Google Scholar
  29. Ke Wang and Li-Yan Yuan. Preservation of integrity constraints in definite DATALOG programs. Inf. Process. Lett., 44(4):185-193, 1992. 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 Imprint Privacy Contact