SACS | Belnap-Dunn Logic and Query Answering in Inconsistent Databases with Null Values

Published in Volume XXXIII, Issue 2, 2023, pages 159-192, doi: 10.7561/SACS.2023.2.159

Authors: C. A. Middelburg

Abstract

This paper concerns an expansion of first-order Belnap-Dunn logic, called BD_⊥^⊃,F, and an application of this logic in the area of relational database theory. The notion of a relational database, the notion of a query applicable to a relational database, and several notions of an answer to a query with respect to a relational database are considered from the perspective of this logic, taking into account that a database may be an inconsistent database and/or a database with null values. The chosen perspective enables among other things the definition of a notion of a consistent answer to a query with respect to a possibly inconsistent database without resort to database repairs. For each of the notions of an answer considered, being an answer to a query with respect to a database of the kind considered is decidable.

Full Text (PDF)

References

[1] Alan Anderson and Nuel Belnap. First degree entailments. Mathematische Annalen, 149(4):302-319, 1963. doi:10.1007/BF01471125.

[2] Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In Victor Vianu and Christos H. Papadimitriou, editors, 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1999, pages 68-79. ACM Press, 1999. doi:10.1145/303976.303983.

[3] Ofer Arieli and Arnon Avron. Four-valued paradefinite logics. Studia Logica, 105(6):1087-1122, 2017. doi:10.1007/s11225-017-9721-4.

[4] Leopoldo E. Bertossi. Database repairs and consistent query answering: Origins and further developments. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, pages 48-58. ACM Press, 2019. doi:10.1145/3294052.3322190.

[5] Joachim Biskup. A foundation of Codd’s relational maybe-operations. ACM Transactions on Database Systems, 8(4):608-636, 1983. doi:10.1145/319996.320014.

[6] François Bry. Query answering in information systems with integrity constraints. In Sushil Jajodia, William List, Graeme W. McGregor, and Leon Strous, editors, 1st Working Conference on Integrity and Internal Control in Information Systems, IICIS 1997, volume 109 of IFIP Conference Proceedings, pages 113-130. Chapman and Hall, 1997. doi:10.1007/978-0-387-35317-3_6.

[7] Marco Calautti, Leonid Libkin, and Andreas Pieris. An operational approach to consistent query answering. In Jan Van den Bussche and Marcelo Arenas, editors, 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2018, pages 239-251. ACM Press, 2018. doi:10.1145/3196959.3196966.

[8] Roberto Ciuni and Massimiliano Carrara. Normality operators and classical recapture in many-valued logic. Logic Journal of the IGPL, 28(5):657-683, 2020. doi:10.1093/jigpal/jzy055.

[9] Edgar F. Codd. Relational completeness of data base sublanguage. Technical Report RJ 987, IBM, 1972.

[10] Edgar F. Codd. Extending the database relational model to capture more meaning. ACM Transactions on Database Systems, 4(4):397-434, 1979. doi:10.1145/320107.320109.

[11] Hervé Gallaire, Jack Minker, and Jean-Marie Nicolas. Logic and databases: A deductive approach. Computing Surveys, 16(2):153-185, 1984. doi:10.1145/356924.356929.

[12] G. H. Gessert. Four valued logic for relational database systems. ACM SIGMOD Record, 19(3):29-35, 1990. doi:10.1145/382274.382401.

[13] Sergio Greco and Cristian Molinaro. Consistent query answering over inconsistent databases. International Journal of Knowledge-based and Intelligent Engineering Systems, 15(3):119-129, 2011. doi:10.3233/KES-2011-0216.

[14] Tomasz Imielinski and Witold Lipski Jr. Incomplete information in relational databases. Journal of the ACM, 31(4):761-791, 1984. doi:10.1145/1634.1886.

[15] Stephen Cole Kleene. Introduction to Metamathematics. North-Holland, Amsterdam, 1952.

[16] Hans-Joachim Klein. Null values in relational databases and sure information answers. In Leopoldo E. Bertossi, Gyula O. H. Katona, Klaus-Dieter Schewe, and Bernhard Thalheim, editors, 2nd International Workshop on Semantics in Databases, volume 2582 of Lecture Notes in Computer Science, pages 119-138. Springer-Verlag, 2001.
doi:10.1007/3-540-36596-6\_7.

[17] Karel Lambert. Free logic and the concept of existence. Notre Dame Journal of Formal Logic, 8(1-2):133-144, 1967. doi:10.1305/ndjfl/1093956251.

[18] Leonid Libkin. SQL’s three-valued logic and certain answers. ACM Transactions on Database Systems, 41(1):Article 1, 2016. doi:10.1145/2877206.

[19] Andrei Lopatenko and Leopoldo E. Bertossi. Consistent query answering by minimal-size repairs. In 17th International Workshop on Database and Expert Systems Applications, DEXA 2006, pages 558-562. IEEE, 2006. doi:10.1109/DEXA.2006.43.

[20] Cornelis A. Middelburg. On the strongest three-valued paraconsistent logic contained in classical logic and its dual. Journal of Logic and Computation, 31(2):597-611, 2021. doi:10.1093/logcom/exaa084.

[21] Cornelis A. Middelburg. Paraconsistent logic and query answering in inconsistent databases. CoRR, abs/2208.12976, 2022. arXiv:2208.12976.

[22] Cornelis A. Middelburg. A conventional expansion of first-order Belnap-Dunn logic. CoRR, abs/2301.10555, 2023. arXiv:2301.10555.

[23] John Nolt. Free logics. In Dale Jacquette, editor, Philosophy of Logic, Handbook of the Philosophy of Science, pages 1023-1060. Elsevier, 2007. doi:10.1016/B978-044451541-4/50027-0.

[24] Lavinia Marı́a Picollo. Truth in a logic of formal inconsistency: How classical can it get? Logic Journal of the IGPL, 28(5):771-806, 2020. doi:10.1093/jigpal/jzy059.

[25] Graham Priest. The logic of paradox. Journal of Philosophical Logic, 8(1):219-241, 1979. doi:10.1007/BF00258428.

[26] Raymond Reiter. Towards a logical reconstruction of relational database theory. In Michael L. Brodie, John Mylopoulos, and Joachim W. Schmidt, editors, On Conceptual Modelling, Topics in
information systems, pages 191-238. Springer-Verlag, 1984. doi:10.1007/978-1-4612-5196-5_8.

[27] Katsuhiko Sano and Hitoshi Omori. An expansion of first-order Belnap-Dunn logic. Logic Journal of the IGPL, 22(3):458-481, 2014. doi:10.1093/jigpal/jzt044.

[28] Balder ten Cate, Gaëlle Fontaine, and Phokion G. Kolaitis. On the data complexity of consistent query answering. Theory of Computing Systems, 57(4):843-891, 2015. doi:10.1007/s00224-014-9586-0.

[29] Moshe Y. Vardi. Querying logical databases. Journal of Computer and System Sciences, 33(2):142-160, 1986. doi:10.1016/0022-0000(86)90016-4.

[30] Yannis Vassiliou. Null values in data base management: A denotational semantics approach. In Philip A. Bernstein, editor, 1979 ACM SIGMOD International Conference on Management of Data, pages 162-169. ACM
Press, 1979. doi:10.1145/582095.582123.

[31] Carlo Zaniolo. Database relations with null values. Journal of Computer and System Sciences, 28(1):142-166, 1984. doi:10.1016/0022-0000(84)90080-1.

Bibtex

@article{sacscuza:kees2023bdlqaidnv,
  title={Belnap-Dunn Logic and Query Answering in Inconsistent Databases with Null Values},
  author={C.A. Middelburg},
  journal={Scientific Annals of Computer Science},
  volume={33},
  number={2},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2023},
  pages={159-192},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2023.2.159}
}