Universal (and Existential) Nulls

• Autorzy: Grahne Gösta , Moallemi Ali

Identyfikatory

DOI

10.3233/FI-2019-1819

• Języki publikacji: EN

Abstrakty

EN

Incomplete Information research is quite mature when it comes to so called existential nulls, where an existential null is a value stored in the database, representing an unknown object. For some reason universal nulls, that is, values representing all possible objects, have received almost no attention. We remedy the situation in this paper, by showing that a suitable finite representation mechanism, called Star Cylinders, handling universal nulls can be developed based on the Cylindric Set Algebra of Henkin, Monk and Tarski. We provide a finitary version of the cylindric set algebra, called Cylindric Star Algebra, and show that our star-cylinders are closed under this algebra. Moreover, we show that any First Order Relational Calculus query over databases containing universal nulls can be translated into an equivalent expression in our cylindric star-algebra, and vice versa. All cylindric star-algebra expressions can be evaluated in time polynomial in the size of the database. The representation mechanism is then extended to Naive Star Cylinders, which are star-cylinders allowing existential nulls in addition to universal nulls. For positive queries (with universal quantification), the well known naive evaluation technique can still be applied on the existential nulls, thereby allowing polynomial time evaluation of certain answers on databases containing both universal and existential nulls. If precise answers are required, certain answer evaluation with universal and existential nulls remains in coNP. Note that the problem is coNP-hard, already for positive existential queries and databases with only existential nulls. If inequalities ¬(x_i ≈ x _j) are allowed, reasoning over existential databases is known to be ∏₂^p -complete, and it remains in ∏ ₂^pwhen universal nulls and full first order queries are allowed.

Słowa kluczowe

EN

relational algebra; cylindric set algebra; incomplete information; query languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 167, nr 4
• Strony: 287--321
• Opis fizyczny: Bibliogr. 26 poz., tab.

Twórcy

autor

Grahne Gösta

• Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada

autor

Moallemi Ali

• Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada

Bibliografia

• [1] Imielinski T, Lipski W. Incomplete Information in Relational Databases. J. ACM, 1984. 31(4):761-791.
• [2] Fagin R, Kolaitis PG, Popa L, Tan WC. Reverse data exchange: coping with nulls. In: PODS. 2009 pp.23-32.
• [3] Gheerbrant A, Libkin L, Sirangelo C. Naïve Evaluation of Queries over Incomplete Databases. ACM Trans. Database Syst., 2014. 39(4):31:1-31:42. doi:10.1145/2691190.2691194. URL http://doi.acm.org/10.1145/2691190.2691194.
• [4] Grahne G, Moallemi A, Onet A. Intuitionistic Data Exchange. In: Proc. of the 9th Alberto Mendelzon International Workshop on Foundations of Data Management, Lima, Peru, May 6-8, 2015. 2015.
• [5] Libkin L. Negative Knowledge for Certain Query Answers. In: Ortiz M, Schlobach S (eds.), Web Reasoning and Rule Systems-10th International Conference, RR 2016, Aberdeen, UK, September 9-11, 2016, Proceedings, volume 9898 of Lecture Notes in Computer Science. Springer. ISBN 978-3-319-45275-3, 2016 pp. 111-127. doi:10.1007/978-3-319-45276-0_9. URL https://doi.org/10.1007/978-3-319-45276-0_9.
• [6] Biskup J. Extending the Relational Algebra for Relations with Maybe Tuples and Existential and Universal Null Values. Fundam. Inform., 1984. 7(1):129-150.
• [7] Biskup J. A Foundation of Codd’s Relational Maybe-Operations. ACM Trans. Database Syst., 1983. 8(4):608-636. doi:10.1145/319996.320014. URL http://doi.acm.org/10.1145/319996.320014.
• [8] Imielinski T, Lipski W. The Relational Model of Data and Cylindric Algebras. J. Comput. Syst. Sci., 1984. 28(1):80-102. doi:10.1016/0022-0000(84)90077-1. URL https://doi.org/10.1016/0022-0000(84) 90077-1.
• [9] Henkin L, Monk JD, Tarski A. Cylindric Algebras-Part I, volume 64 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, 1971.
• [10] Henkin L, Monk JD, Tarski A. Cylindric Algebras-Part II, volume 115 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Company, 1985.
• [11] Sundarmurthy B, Koutris P, Lang W, Naughton JF, Tannen V. m-tables: Representing Missing Data. In: 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy. 2017 pp. 21:1-21:20. doi:10.4230/LIPIcs.ICDT.2017.21. URL https://doi.org/10.4230/LIPIcs.ICDT.2017.21.
• [12] den Bussche JV. Applications of Alfred Tarski’s Ideas in Database Theory. In: Fribourg L (ed.), Computer Science Logic, 15th International Workshop, CSL 2001. 10th Annual Conference of the EACSL, Paris, France, September 10-13, 2001, Proceedings, volume 2142 of Lecture Notes in Computer Science. Springer. ISBN 3-540-42554-3, 2001 pp. 20-37. doi:10.1007/3-540-44802-0_2. URL https://doi.org/10.1007/3-540-44802-0_2.
• [13] Abiteboul S, Hull R, Vianu V. Foundations of Databases. Addison-Wesley, 1995. ISBN 0-201-53771-0.
• [14] Abiteboul S, Kanellakis PC, Grahne G. On the Representation and Querying of Sets of Possible Worlds. Theor. Comput. Sci., 1991. 78(1):158-187. doi:10.1016/0304-3975(51)90007-2. URL https://doi.org/10.1016/0304-3975(51)90007-2.
• [15] Andréka H, Ferenczi M, Németi I. Cylindric-like Algebras and Algebraic Logic, volume 22. Springer Science & Business Media, 2014.
• [16] Yannakakis M, Papadimitriou CH. Algebraic Dependencies. J. Comput. Syst. Sci., 1982. 25(1):2-41. doi:10.1016/0022-0000(82)90008-3. URL https://doi.org/10.1016/0022-0000(82)90008-3.
• [17] Cosmadakis SS. Database Theory and Cylindric Lattices (Extended Abstract). In: 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987. 1987 pp.411-420. doi:10.1109/SFCS.1987.17. URL https://doi.org/10.1109/SFCS.1987.17.
• [18] Hodkinson I, Mikulás S. Axiomatizability of reducts of algebras of relations. Algebra Universalis, 2000. 43(2):127-156.
• [19] Düntsch I, Mikulás S. Cylindric structures and dependencies in relational databases. Theor. Comput. Sci., 2001. 269(1-2):451-468. doi:10.1016/S0304-3975(01)00016-0. URL https://doi.org/10.1016/S0304-3975(01)00016-0.
• [20] Kanellakis P, Kuper G, Revesz P. Constraint Query Languages. Journal of Computer and System Sciences, 1995. 51(1):26-52.
• [21] Bojańczyk M. Orbit-Finite Sets and Their Algorithms (Invited Talk). In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland. 2017 pp. 1:1-1:14. doi:10.4230/LIPIcs.ICALP.2017.1. URL https://doi.org/10.4230/LIPIcs.ICALP.2017.1.
• [22] Deutsch A, Nash A, Remmel JB. The chase revisited. In: Proceedings of the Twenty-Seventh ACMSIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, June 9-11, 2008, Vancouver, BC, Canada. 2008 pp. 149-158. doi:10.1145/1376916.1376938. URL http://doi.acm.org/10.1145/1376916.1376938.
• [23] Lyndon RC. Properties preserved under homomorphism. Pacific J. Math., 1959. 9(1):143-154. URL https://projecteuclid.org:443/euclid.pjm/1103039459.
• [24] Ajtai M, Gurevich Y. Monotone Versus Positive. J. ACM, 1987. 34(4):1004-1015. doi:10.1145/31846.31852. URL http://doi.acm.org/10.1145/31846.31852.
• [25] Stolboushkin AP. Finitely Monotone Properties. In: Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, LICS ’95. IEEE Computer Society, Washington, DC, USA. ISBN 0-8186-7050-6, 1995 pp. 324–. URL http://dl.acm.org/citation.cfm?id=788017.788758.
• [26] Grahne G. The Problem of Incomplete Information in Relational Databases, volume 554 of Lecture Notes in Computer Science. Springer, 1991. ISBN 3-540-54919-6. doi:10.1007/3-540-54919-6. URL https://doi.org/10.1007/3-540-54919-6.316.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).