Document Open Access Logo

Fragments of Bag Relational Algebra: Expressiveness and Certain Answers

Authors Marco Console, Paolo Guagliardo , Leonid Libkin

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2019.8.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

Marco Console
  • School of Informatics, University of Edinburgh, United Kingdom
Paolo Guagliardo
  • School of Informatics, University of Edinburgh, United Kingdom
Leonid Libkin
  • School of Informatics, University of Edinburgh, United Kingdom

Funding

Work supported by EPSRC grants M025268 and N023056.

Acknowledgements

The authors thank Etienne Toussaint and the referees for their helpful comments.

Cite AsGet BibTex

Marco Console, Paolo Guagliardo, and Leonid Libkin. Fragments of Bag Relational Algebra: Expressiveness and Certain Answers. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICDT.2019.8

Abstract

While all relational database systems are based on the bag data model, much of theoretical research still views relations as sets. Recent attempts to provide theoretical foundations for modern data management problems under the bag semantics concentrated on applications that need to deal with incomplete relations, i.e., relations populated by constants and nulls. Our goal is to provide a complete characterization of the complexity of query answering over such relations in fragments of bag relational algebra. The main challenges that we face are twofold. First, bag relational algebra has more operations than its set analog (e.g., additive union, max-union, min-intersection, duplicate elimination) and the relationship between various fragments is not fully known. Thus we first fill this gap. Second, we look at query answering over incomplete data, which again is more complex than in the set case: rather than certainty and possibility of answers, we now have numerical information about occurrences of tuples. We then fully classify the complexity of finding this information in all the fragments of bag relational algebra.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database theory
  • Theory of computation → Database query languages (principles)
  • Theory of computation → Incomplete, inconsistent, and uncertain databases
  • Information systems → Relational database query languages
  • Information systems → Structured Query Language
Keywords
  • bag semantics
  • relational algebra
  • expressivity
  • certain answers
  • complexity

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. Google Scholar
  2. Serge Abiteboul, Paris Kanellakis, and Gösta Grahne. On the representation and querying of sets of possible worlds. Theoretical Computer Science, 78(1):158-187, 1991. Google Scholar
  3. Shqiponja Ahmetaj, Magdalena Ortiz, and Mantas Simkus. Polynomial Datalog Rewritings for Expressive Description Logics with Closed Predicates. In IJCAI, pages 878-885, 2016. Google Scholar
  4. Joseph Albert. Algebraic Properties of Bag Data Types. In VLDB, pages 211-219, 1991. Google Scholar
  5. Giovanni Amendola, Nicola Leone, Marco Manna, and Pierfrancesco Veltri. Enhancing Existential Rules by Closed-World Variables. In IJCAI, pages 1676-1682, 2018. Google Scholar
  6. Marcelo Arenas, Pablo Barceló, Leonid Libkin, and Filip Murlak. Foundations of Data Exchange. Cambridge University Press, 2014. Google Scholar
  7. Leopoldo E. Bertossi, Georg Gottlob, and Reinhard Pichler. Datalog: Bag Semantics via Set Semantics. CoRR, abs/1803.06445, 2018. URL: http://arxiv.org/abs/1803.06445.
  8. Meghyn Bienvenu and Magdalena Ortiz. Ontology-Mediated Query Answering with Data-Tractable Description Logics. In Reasoning Web, pages 218-307, 2015. Google Scholar
  9. Peter Buneman, Shamim A. Naqvi, Val Tannen, and Limsoon Wong. Principles of Programming with Complex Objects and Collection Types. Theor. Comput. Sci., 149(1):3-48, 1995. Google Scholar
  10. R. G. G. Cattell. The Object Database Standard: ODMG-93. Morgan Kaufmann, 1993. Google Scholar
  11. Surajit Chaudhuri and Moshe Y. Vardi. Optimization of Real Conjunctive Queries. In PODS, pages 59-70, 1993. Google Scholar
  12. Sara Cohen. Equivalence of queries combining set and bag-set semantics. In PODS, pages 70-79, 2006. Google Scholar
  13. Latha S. Colby and Leonid Libkin. Tractable Iteration Mechanisms for Bag Languages. In ICDT, pages 461-475, 1997. Google Scholar
  14. Marco Console, Paolo Guagliardo, and Leonid Libkin. On Querying Incomplete Information in Databases under Bag Semantics. In IJCAI, pages 993-999. ijcai.org, 2017. Google Scholar
  15. C. J. Date and Hugh Darwen. A Guide to the SQL Standard. Addison-Wesley, 1996. Google Scholar
  16. Todd J. Green, Gregory Karvounarakis, and Val Tannen. Provenance semirings. In PODS, pages 31-40. ACM, 2007. Google Scholar
  17. Stéphane Grumbach, Leonid Libkin, Tova Milo, and Limsoon Wong. Query languages for bags: expressive power and complexity. SIGACT News, 27(2):30-44, 1996. Google Scholar
  18. Stéphane Grumbach and Tova Milo. Towards Tractable Algebras for Bags. J. Comput. Syst. Sci., 52(3):570-588, 1996. Google Scholar
  19. André Hernich. Answering Non-Monotonic Queries in Relational Data Exchange. Logical Methods in Computer Science, 7(3), 2011. Google Scholar
  20. André Hernich and Phokion G. Kolaitis. Foundations of information integration under bag semantics. In LICS, pages 1-12. IEEE Computer Society, 2017. Google Scholar
  21. André Hernich, Leonid Libkin, and Nicole Schweikardt. Closed world data exchange. ACM Trans. Database Syst., 36(2):14:1-14:40, 2011. Google Scholar
  22. Tomasz Imielinski and Witold Lipski. Incomplete information in relational databases. Journal of the ACM, 31(4):761-791, 1984. Google Scholar
  23. T. S. Jayram, Phokion G. Kolaitis, and Erik Vee. The containment problem for real conjunctive queries with inequalities. In PODS, pages 80-89, 2006. Google Scholar
  24. Phokion G. Kolaitis. The Query Containment Problem: Set Semantics vs. Bag Semantics. In AMW, 2013. Google Scholar
  25. Maurizio Lenzerini. Data integration: a theoretical perspective. In PODS, pages 233-246, 2002. Google Scholar
  26. Leonid Libkin and Limsoon Wong. Query Languages for Bags and Aggregate Functions. J. Comput. Syst. Sci., 55(2):241-272, 1997. Google Scholar
  27. Carsten Lutz, Inanç Seylan, and Frank Wolter. Ontology-Mediated Queries with Closed Predicates. In IJCAI, pages 3120-3126, 2015. Google Scholar
  28. Charalampos Nikolaou, Egor V. Kostylev, George Konstantinidis, Mark Kaminski, Bernardo Cuenca Grau, and Ian Horrocks. The Bag Semantics of Ontology-Based Data Access. In IJCAI, pages 1224-1230, 2017. Google Scholar
  29. Christos H. Papadimitriou and Mihalis Yannakakis. The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci., 28(2):244-259, 1984. Google Scholar
  30. Raghu Ramakrishnan and Johannes Gehrke. Database Management Systems. McGraw-Hill, 2003. 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