Probabilistic interval XML

Abstract

Interest in XML databases has been expanding rapidly over the last few years. In this paper, we study the problem of incorporating probabilistic information into XML databases. We propose the Probabilistic Interval XML (PIXML for short) data model in this paper. Using this data model, users can express probabilistic information within XML markups. In addition, we provide two alternative formal model-theoretic semantics for PIXML data. The first semantics is a “global” semantics which is relatively intuitive, but is not directly amenable to computation. The second semantics is a “local” semantics which supports efficient computation. We prove several correspondence results between the two semantics. To our knowledge, this is the first formal model theoretic semantics for probabilistic interval XML. We then provide an operational semantics that may be used to compute answers to queries and that is correct for a large class of probabilistic instances.

References

1. Abellan, J. and Moral, S. 2003. Building classification trees using the total uncertainty criterion. Intl. J. Intell. Syst. 18, 12, 1215--1225.
2. Barbara, D., Garcia-Molina, H., and Porter, D. 1992. The management of probabilistic data. IEEE Trans. Knowl. Data Engin. 4, 487--502.
3. Boole, G. 1954. The Laws of Thought. Macmillan.
4. Bouwerman, B. and O'Connell, R. 2000. Forecasting and Time Series: An Applied Approach. Brooks/Cole Publishing.
5. Braz, R., Amir, E., and Roth, D. 2005. Lifted first-order probabilistic inference. In 19th International Joint Conference on Artificial Intelligence (IJCAI'05).
6. Cavallo, R. and Pittarelli, M. 1987. The theory of probabilistic databases. In Proceedings of the 13th International Conference on Very Large Data Bases. Brighton, England, 71--81.
7. Dekhtyar, A., Goldsmith, J., and Hawkes, S. 2001. Semistructured probabilistic databases. In Proceedings of the Conference on Statistical and Scientific Database Management (SSDBM). Fairfax, VA, USA, 36--45.
8. Dey, D. and Sarkar, S. 1996. A probabilistic relational model and algebra. ACM Trans. Datab. Syst. 21, 3, 339--369.
9. Dyreson, C. and Snodgrass, R. 1998. Supporting valid-time indeterminacy. ACM Trans. Datab. Syst. 23, 1, 1--57.
10. Eiter, T., Lu, J., Lukasiewicz, T., and Subrahmanian, V. 2001. Probabilistic object bases. ACM Trans. Datab. Syst. 26, 3 (Sept.).
11. Fagin, R., Halpern, J., and Megiddo, N. 1990. A logic for reasoning about probabilities. Inform. Computat., 78--128.
12. Friedman, N., Getoor, L., Koller, D., and Pfeffer, A. 2005. Learning probabilistic relational models. In Proceedings of the 16th International Joint Conference on Artificial Intelligence. 1300--1307.
13. Friedman, N. and Koller, D. 2003. Being bayesian about network structure. a bayesian approach to structure discovery in bayesian networks. Machine Learn. J. 50, 1-2, 95--125.
14. Getoor, L., Friedman, N., Koller, D., and Pfeffer, A. 2001. Learning probabilistic relational models. Relational Data Mining, Newsletter.
15. Goldman, S. and Rivest, R. 1986. A non-iterative maximum entropy algorithm. In Proceedings of the 2nd Annual Conference on Uncertainty in Artificial Intelligence (UAI'86). Elsevier Science Publishing Comapny, Inc., New York, NY, 133--148.
16. Goldsmith, J., Dekhtyar, A., and Zhao, W. 2003. Can probabilistic databases help elect qualified officials% In Proceedings of Florida Atlantic Artificial Intelligence Research Symposium (FLAIRS). St. Augustine, FL, 501--505.
17. Guntzer, U., Kiessling, W., and Thone, H. 1991. New directions for uncertainty reasoning in deductive databases. In Proceedings of ACM SIGMOD Conference. Denver, CO. 178--187.
18. Hung, E., Getoor, L., and Subrahmanian, V. 2003. PXML: A probabilistic semistructured data model and algebra. In Proceedings of 19th International Conference on Data Engineering (ICDE). Bangalore, India.
19. Kamberova, G. and Bajcsy, R. 1998. Stereo depth estimation: the confidence interval approach. In Proceedings of the International Conference on Computer Vision (ICCV'98). Bombay, India, 503--509.
20. Kersting, K. and Raedt, L. D. 2001. In Proceedings of the 11th Conference on Inductive Logic Programming.
21. Kiessling, W., Thone, H., and Guntzer, U. 1992. Database support for problematic knowledge. In Proceedings of International Conference on Extending Database Technology. Vienna, Austria. Lecture Notes in Computer Science, vol. 580, Springer, 421--436.
22. Koller, D. and Pfeffer, A. 1997. Object-oriented Bayesian networks. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. 302--313.
23. Koller, D. and Pfeffer, A. 1998. Probabilistic frame-based systems. Proceedings of the 15th National Conference on Artificial Intelligence, 580--587.
24. Lakshmanan, L. V., Leone, N., Ross, R., and Subrahmanian, V. 1997. ProbView: A flexible probabilistic database system. ACM Trans. Datab. Syst. 22, 3, 419--469.
25. Lakshmanan, L. V. and Sadri, F. 1994. Probabilistic deductive databases. In Proceedings of International Symposium on Logic Programming (SLP). Ithaca, New York, 254--268.
26. Lakshmanan, L. V. and Shiri, N. 1996. A parametric approach to deductive databases with uncertainty. In Proceedings of International Workshop on Logic In Databases. San Miniato, Italy, 61--81.
27. Laskey, K. 2005. First order Bayesian logic, research report. Tech. rep., George Mason University.
28. McHugh, J., Abiteboul, S., Goldman, R., Quass, D., and Widom, J. 1997. Lore: A database management system for semistructured data. SIGMOD Record 26, 3, 54--66.
29. Moral, S. and Cano, A. 2002. Strong conditional independence for credal sets. Ann. Math. AI 35, 1-4, 295--321.
30. Nierman, A. and Jagadish, H. 2002. ProTDB: Probabilistic data in XML. In Proceedings of the 28th International Conference on Very Large Data Bases. Hong Kong, China, 646--657.
31. Poole, D. 2003. First order probabilistic inference. In Proceedings of the International Joint Conference on Artificial Intelligence. 985--991.
32. Poole, D. and Zhang, L. 2003. Exploiting contextual independence in probabilistic inference. J. AI Resear. 18, 263--313.
33. Radev, D., Fan, W., and Qi, H. 2002. Probabilistic question answering from the web. In Proceedings of the 11th International World Wide Web Conference. Honolulu, Haiwaii, 408--419.
34. Ross, S. 1998. A First Course in Probability. Prentice Hall.
35. W3C. Extensible Markup Language (XML). http://www.w3.org/XML.
36. Zhao, W., Dekhtyar, A., and Goldsmith, J. 2003. Query algebra operations for interval probabilities. In Proceedings of the Iternational Conference on Database and Expert Systems Applications (DEXA). Prague, Czech Republic, 527--536.
37. Zhao, W., Dekhtyar, A., and Goldsmith, J. 2004. Databases for interval probabilities. Inter. J. Intelli. Syst. To appear.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

• Information systems

  • Data management systems

    • Database design and models

    • Query languages

• Theory of computation

  • Logic