Document Open Access Logo

Conjunctive Queries: Unique Characterizations and Exact Learnability

Authors Balder ten Cate , Victor Dalmau

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2021.9.pdf
  • Filesize: 0.85 MB
  • 24 pages

Document Identifiers

Author Details

Balder ten Cate
  • Google, Mountain View, CA, USA
Victor Dalmau
  • Universitat Pompeu Fabra, Barcelona, Spain

Funding

  • Dalmau, Victor: Victor Dalmau was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22.

Acknowledgements

This paper largely grew out of discussions at Dagstuhl Seminar 19361 ("Logic and Learning") in Sept. 2019. We thank Carsten Lutz and Phokion Kolaitis for helpful discussions.

Cite As Get BibTex

Balder ten Cate and Victor Dalmau. Conjunctive Queries: Unique Characterizations and Exact Learnability. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICDT.2021.9

Abstract

We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples, and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts.

Subject Classification

ACM Subject Classification
  • Theory of computation → Machine learning theory
  • Theory of computation → Logic
  • Information systems → Query languages
Keywords
  • Conjunctive Queries
  • Homomorphisms
  • Frontiers
  • Unique Characterizations
  • Exact Learnability
  • Schema Mappings
  • Description Logic

Metrics

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

Related Versions

References

  1. Bogdan Alexe, Balder ten Cate, Phokion G. Kolaitis, and Wang-Chiew Tan. Characterizing schema mappings via data examples. ACM Trans. Database Syst., 36(4):23:1-23:48, December 2011. URL: https://doi.org/10.1145/2043652.2043656.
  2. Dana Angluin. Queries and concept learning. Mach. Learn., 2(4):319–342, April 1988. URL: https://doi.org/10.1023/A:1022821128753.
  3. Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler. An Introduction to Description Logic. Cambridge University Press, 2017. Google Scholar
  4. Franz Baader and Werner Nutt. Basic Description Logics, page 43–95. Cambridge University Press, USA, 2003. Google Scholar
  5. Vince Bárány, Georg Gottlob, and Martin Otto. Querying the guarded fragment. Logical Methods in Computer Science, 10(2), 2014. URL: https://doi.org/10.2168/LMCS-10(2:3)2014.
  6. Pablo Barceló and Miguel Romero. The complexity of reverse engineering problems for conjunctive queries. 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 7:1-7:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  7. Google Blog. A reintroduction to our knowledge graph and knowledge panels, 2020. URL: https://blog.google/products/search/about-knowledge-graph-and-knowledge-panels/.
  8. Angela Bonifati, Radu Ciucanu, and Aurélien Lemay. Learning path queries on graph databases. In Gustavo Alonso, Floris Geerts, Lucian Popa, Pablo Barceló, Jens Teubner, Martín Ugarte, Jan Van den Bussche, and Jan Paredaens, editors, Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, March 23-27, 2015, pages 109-120. OpenProceedings.org, 2015. Google Scholar
  9. Angela Bonifati, Radu Ciucanu, and Slawek Staworko. Learning join queries from user examples. ACM Trans. Database Syst., 40(4):24:1-24:38, 2016. Google Scholar
  10. Ashok K. Chandra Chandra and Philip M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In ACM Symposium on Theory of Computing (STOC), pages 77-90, 1977. Google Scholar
  11. William W. Cohen. Cryptographic limitations on learning one-clause logic programs. In Richard Fikes and Wendy G. Lehnert, editors, Proceedings of the 11th National Conference on Artificial Intelligence. Washington, DC, USA, July 11-15, 1993, pages 80-85. AAAI Press / The MIT Press, 1993. Google Scholar
  12. William W. Cohen. Pac-learning nondeterminate clauses. In Barbara Hayes-Roth and Richard E. Korf, editors, Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, USA, July 31 - August 4, 1994, Volume 1, pages 676-681. AAAI Press / The MIT Press, 1994. Google Scholar
  13. William W. Cohen. Pac-learning non-recursive prolog clauses. Artif. Intell., 79(1):1-38, 1995. Google Scholar
  14. Ronald Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM, 30(3):514–550, July 1983. URL: https://doi.org/10.1145/2402.322390.
  15. Ronald Fagin, Phokion Kolaitis, Alan Nash, and Lucian Popa. Towards a theory of schema-mapping optimization. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 33-42, January 2008. URL: https://doi.org/10.1145/1376916.1376922.
  16. Jan Foniok, Jaroslav Nesetril, and Claude Tardif. Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. Eur. J. Comb., 29(4):881-899, 2008. Google Scholar
  17. Maurice Funk, Jean Christoph Jung, and Carsten Lutz. Actively learning el-concepts and queries in the presence of an ontology. Manuscript, 2020. Google Scholar
  18. Georg Gottlob and Pierre Senellart. Schema mapping discovery from data instances. J. ACM, 57(2):6:1-6:37, 2010. URL: https://doi.org/10.1145/1667053.1667055.
  19. David Haussler. Learning conjunctive concepts in structural domains. Mach. Learn., 4:7-40, 1989. Google Scholar
  20. Pavol Hell and Jaroslav Nešetřil. The Core of a Graph. Discrete Mathematics, 109:117-126, 1992. Google Scholar
  21. Pavol Hell and Jaroslav Nešetřil. Graphs and homomorphisms, volume 28 of Oxford lecture series in mathematics and its applications. Oxford University Press, 2004. Google Scholar
  22. Kouichi Hirata. On the hardness of learning acyclic conjunctive queries. In Hiroki Arimura, Sanjay Jain, and Arun Sharma, editors, Algorithmic Learning Theory, 11th International Conference, ALT 2000, Sydney, Australia, December 11-13, 2000, Proceedings, volume 1968 of Lecture Notes in Computer Science, pages 238-251. Springer, 2000. Google Scholar
  23. Wojtek Kazana and Luc Segoufin. First-order queries on classes of structures with bounded expansion. Logical Methods in Computer Science, Volume 16, Issue 1, February 2020. URL: https://lmcs.episciences.org/6156.
  24. Phokion G. Kolaitis. Schema mappings, data exchange, and metadata management. In Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’05, page 61–75, New York, NY, USA, 2005. Association for Computing Machinery. URL: https://doi.org/10.1145/1065167.1065176.
  25. Carsten Lutz and Frank Wolter. The data complexity of description logic ontologies. Logical Methods in Computer Science, 13, November 2016. URL: https://doi.org/10.23638/LMCS-13(4:7)2017.
  26. Maarten Marx. Narcissists, stepmothers and spies. In Ian Horrocks and Sergio Tessaris, editors, Proceedings of the 2002 International Workshop on Description Logics (DL2002), Toulouse, France, April 19-21, 2002, volume 53 of CEUR Workshop Proceedings. CEUR-WS.org, 2002. URL: http://ceur-ws.org/Vol-53/narcists.pdf.
  27. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion iii. restricted graph homomorphism dualities. European Journal of Combinatorics, 29(4):1012-1024, 2008. Homomorphisms: Structure and Highlights. URL: https://doi.org/10.1016/j.ejc.2007.11.019.
  28. Jaroslav Nešetřil and Patrice Ossona de Mendez. Grad and classes with bounded expansion i. decompositions. European Journal of Combinatorics, 29(3):760-776, 2008. URL: https://doi.org/10.1016/j.ejc.2006.07.013.
  29. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28. Springer, January 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  30. Jaroslav Nešetřil and Claude Tardif. Duality theorems for finite structures (characterising gaps and good characterisations). Journal of Combinatorial Theory, Series B, 80(1):80-97, 2000. URL: https://doi.org/10.1006/jctb.2000.1970.
  31. Jaroslav Nešetřil and Claude Tardif. Short answers to exponentially long questions: Extremal aspects of homomorphism duality. SIAM J. Discret. Math., 19(4):914-920, August 2005. URL: https://doi.org/10.1137/S0895480104445630.
  32. Ana Ozaki. Learning description logic ontologies: Five approaches. where do they stand? KI - Künstliche Intelligenz, April 2020. URL: https://doi.org/10.1007/s13218-020-00656-9.
  33. Slawek Staworko and Piotr Wieczorek. Learning twig and path queries. In Alin Deutsch, editor, 15th International Conference on Database Theory, ICDT '12, Berlin, Germany, March 26-29, 2012, pages 140-154. ACM, 2012. Google Scholar
  34. Balder ten Cate, Laura Chiticariu, Phokion Kolaitis, and Wang-Chiew Tan. Laconic schema mappings: Computing the core with sql queries. Proc. VLDB Endow., 2(1):1006–1017, August 2009. URL: https://doi.org/10.14778/1687627.1687741.
  35. Balder ten Cate and Víctor Dalmau. The product homomorphism problem and applications. In Marcelo Arenas and Martín Ugarte, editors, 18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium, volume 31 of LIPIcs, pages 161-176. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  36. Balder ten Cate, Víctor Dalmau, and Phokion G. Kolaitis. Learning schema mappings. ACM Trans. Database Syst., 38(4):28:1-28:31, 2013. URL: https://doi.org/10.1145/2539032.2539035.
  37. Balder ten Cate, Phokion G. Kolaitis, Kun Qian, and Wang-Chiew Tan. Active learning of GAV schema mappings. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pages 355-368. ACM, 2018. URL: https://doi.org/10.1145/3196959.3196974.
  38. Yaacov Y. Weiss and Sara Cohen. Reverse engineering spj-queries from examples. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 151-166. ACM, 2017. Google Scholar
  39. Ross Willard. Testing expressibility is hard. In David Cohen, editor, Principles and Practice of Constraint Programming - CP 2010 - 16th International Conference, CP 2010, St. Andrews, Scotland, UK, September 6-10, 2010. Proceedings, volume 6308 of Lecture Notes in Computer Science, pages 9-23. Springer, 2010. 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