A logical account of uncertain databases based on linear logic

ABSTRACT

A formal semantics of uncertain databases typically takes an algebraic approach by mapping an uncertain database to a set of relational databases, or possible worlds. We present a new semantics for uncertain databases which takes a logical approach by translating uncertain databases into logical theories. A characteristic feature of our semantics is that it uses linear logic, instead of propositional logic, as its logical foundation. Linear logic lends itself well to a logical interpretation of uncertain information because unlike propositional logic, it treats logical formulae not as persistent facts but as consumable resources.

We motivate our development by arguing that propositional logic is inadequate as a logical foundation for uncertain databases. As the main result, we show that our semantics is faithful to the operational account of uncertain databases in the algebraic approach.

REFERENCES

• 1: Serge Abiteboul , Paris Kanellakis , Gosta Grahne, On the representation and querying of sets of possible worlds, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.34-48, May 27-29, 1987, San Francisco, California, United States
• 2: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: W Bibel, A deductive solution for plan generation, New Generation Computing, v.4 n.2, p.115-132, 1986 [doi>10.1007/BF03037438]
• 4: N. Bidoit, S. Cerrito, and C. Froidevaux. A linear logic approach to consistency preserving updates. Journal of Logic and Computation, 6(3):439--463, 1996.
• 5: A. J. Bonner and M. Kifer. The state of change: A survey. Lecture Notes in Computer Science, 1472:1--36, 1998.
• 6: B. Chang, K. Chaudhuri, and F. Pfenning. A judgmental analysis of linear logic. Technical Report CMU-CS-03-131, School of Computer Science, Carnegie Mellon University, 2003.
• 7: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 8: L. G. DeMichiel, Resolving Database Incompatibility: An Approach to Performing Relational Operations over Mismatched Domains, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.485-493, December 1989 [doi>10.1109/69.43423]
• 9: Jean-Yves Girard, Linear logic, Theoretical Computer Science, v.50 n.1, p.1-102, Jan. 30, 1987 [doi>10.1016/0304-3975(87)90045-4]
• 10: G. Grahne, Horn tables-an efficient tool for handling incomplete information in databases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.75-82, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73728]
• 11: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 12: Tomasz Imielinski , Shamim Naqvi , Kumar Vadaparty, Incomplete object—a data model for design and planning applications, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.288-297, May 29-31, 1991, Denver, Colorado, United States
• 13: Gilles Kahn, Natural Semantics, Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, p.22-39, February 19-21, 1987
• 14: Dong-Tsan Lee , C. P. Tsang, Linear logic for deductive databases, New Generation Computing, v.17 n.2, p.201-228, 1999 [doi>10.1007/BF03037436]
• 15: Leonid Libkin , Limsoon Wong, Semantic representations and query languages for or-sets, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.37-48, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153854]
• 16: P. Lincoln, J. Mitchell, A. Scedrov, and N. Shankar. Decision problems for propositional linear logic. Annals of Pure and Applied Logic, 56:239--311, Apr. 1992.
• 17: Ken-Chih Liu , Rajshekhar Sunderraman, Indefinite and maybe information in relational databases, ACM Transactions on Database Systems (TODS), v.15 n.1, p.1-39, March 1990 [doi>10.1145/77643.77644]
• 18: K. -C. Liu , R. Sunderraman, A Generalized Relational Model for Indefinite and Maybe Information, IEEE Transactions on Knowledge and Data Engineering, v.3 n.1, p.65-77, March 1991 [doi>10.1109/69.75890]
• 19: M. Masseron , C. Tollu , J. Vauzeilles, Generating plans in linear logic I: actions as proofs, Theoretical Computer Science, v.113 n.2, p.349-370, June 7, 1993 [doi>10.1016/0304-3975(93)90007-G]
• 20: R. Reiter. Towards a logical reconstruction of relational database theory. In M. L. Brodie, J. Mylopoulos, and J. W. Schmidt, editors, On Conceptual Modelling: Perspectives from Artificial Intelligence, Databases, and Programming Languages, pages 191--233. Springer, 1984.
• 21: Raymond Reiter, A sound and sometimes complete query evaluation algorithm for relational databases with null values, Journal of the ACM (JACM), v.33 n.2, p.349-370, April 1986 [doi>10.1145/5383.5388]
• 22: Raymond Reiter, The frame problem in situation the calculus: a simple solution (sometimes) and a completeness result for goal regression, Artificial intelligence and mathematical theory of computation: papers in honor of John McCarthy, Academic Press Professional, Inc., San Diego, CA, 1991
• 23: Anish Das Sarma , Omar Benjelloun , Alon Halevy , Jennifer Widom, Working Models for Uncertain Data, Proceedings of the 22nd International Conference on Data Engineering, p.7, April 03-07, 2006 [doi>10.1109/ICDE.2006.174]
• 24: A. S. Troelstra and D. van Dalen. Constructivism in Mathematics: An Introduction. North-Holland, 1988.
• 25: Ron van der Meyden, Logical approaches to incomplete information: a survey, Logics for databases and information systems, Kluwer Academic Publishers, Norwell, MA, 1998
• 26: Moshe Y. Vardi, Querying logical databases, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.57-65, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325413]
• 27: E. Zimányi. Incomplete and Uncertain Information in Relational Databases. PhD thesis, Université Libre de Bruxelles, Brussels, Belgium, October 1992.