A probabilistic relational algebra for the integration of information retrieval and database systems

ABSTRACT

We present a probabilistic relational algebra (PRA) which is a generalization of standard relational algebra. In PRA, tuples are assigned probabilistic weights giving the probability that a tuple belongs to a relation. Based on intensional semantics, the tuple weights of the result of a PRA expression always conform to the underlying probabilistic model. We also show for which expressions extensional semantics yields the same results. Furthermore, we discuss complexity issues and indicate possibilities for optimization. With regard to databases, the approach allows for representing imprecise attribute values, whereas for information retrieval, probabilistic document indexing and probabilistic search term weighting can be modeled. We introduce the concept of vague predicates which yield probabilistic weights instead of Boolean values, thus allowing for queries with vague selection conditions. With these features, PRA implements uncertainty and vagueness in combination with the relational model.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Barbará , H. Garcia-Molina , D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.487-502, October 1992 [doi>10.1109/69.166990]
	2	BILLINGSLEY, P. 1979. Probability and Measure. John Wiley and Sons, New York.
	3	David C. Blair, An extended relational document retrieval model, Information Processing and Management: an International Journal, v.24 n.3, p.349-371, May 1988 [doi>10.1016/0306-4573(88)90101-X]
	4	Chris Buckley, Implementation of the SMART Information Retrieval System, Cornell University, Ithaca, NY, 1985
	5	Roger Cavallo , Michael Pittarelli, The Theory of Probabilistic Databases, Proceedings of the 13th International Conference on Very Large Data Bases, p.71-81, September 01-04, 1987
	6	E. F. Codd, Missing information (applicable and inapplicable) in relational databases, ACM SIGMOD Record, v.15 n.4, p.53-53, Dec. 1986 [doi>10.1145/16301.16303]
	7	W. Bruce Croft , Howard R. Turtle , David D. Lewis, The use of phrases and structured queries in information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.32-45, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122864]
	8	B. C. Desai , P. Goyal , F. Sadri, Non-first normal form universal relations: an application to information retrieval systems, Information Systems, v.12 n.1, p.49-55, Jan. 1987 [doi>10.1016/0306-4379(87)90017-2]
	9	Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
	10	Norbert Fuhr, A probabilistic framework for vague queries and imprecise information in databases, Proceedings of the sixteenth international conference on Very large databases, p.696-707, September 1990, Brisbane, Australia
	11	Norbert Fuhr, Integration of probabilistic fact and text retrieval, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.211-222, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133202]
	12	Norbert Fuhr, Probabilistic models in information retrieval, The Computer Journal, v.35 n.3, p.243-255, June 1992 [doi>10.1093/comjnl/35.3.243]
	13	Norbert Fuhr, A probabilistic relational model for the integration of IR and databases, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.309-317, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160754]
	14	Norbert Fuhr, Probabilistic Datalog—a logic for powerful retrieval methods, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.282-290, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215372]
	15	Norbert Fuhr , Chris Buckley, A probabilistic learning approach for document indexing, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.223-248, July 1991 [doi>10.1145/125187.125189]
	16	FUHR, N. AND ROLLEKE, T. 1996. A probabilistic NF2 relational algebra for integrated information retrieval and database systems. In Proceedings of the 2nd World Conference on Integrated Design and Process Technology (IDPT). Soc. for Design and Process Science, Austin, Tex.
	17	G. H. Gessert, Four valued logic for relational database systems, ACM SIGMOD Record, v.19 n.1, p.29-35, March 1990 [doi>10.1145/382274.382401]
	18	GU, J., THIEL, U., AND ZHAO, J. 1993. Efficient retrieval of complex objects: Query processing in a hybrid DB and IR system. In Proceedings 1. GI-Fachtagung Information Retrieval. Universit#tsverlag Konstanz, Konstanz, Germany.
	19	David Haines , W. Bruce Croft, Relevance feedback and inference networks, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.2-11, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160689]
	20	Donna Harman, Overview of the second text retrieval conference (TREC-2), Information Processing and Management: an International Journal, v.31 n.3, p.271-289, May-June 1995
	21	IMIELINSKI, T. 1989. Incomplete information in logical databases. Data Eng. Bull. 12, 2, 29-40.
	22	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]
	23	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
	24	KIM, W., Ed. 1989. Special issue on imprecision in databases. Data Eng. Bull. 12, 2.
	25	Do Heon Lee , Myoung Ho Kim, Accommodating subjective vagueness through a fuzzy extension to the relational data model, Information Systems, v.18 n.6, p.363-374, Sept. 1993 [doi>10.1016/0306-4379(93)90013-Q]
	26	Suk Kyoon Lee, An Extended Relational Database Model for Uncertain and Imprecise Information, Proceedings of the 18th International Conference on Very Large Data Bases, p.211-220, August 23-27, 1992
	27	Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
	28	Arjan Loeffen, Text databases: a survey of text models and systems, ACM SIGMOD Record, v.23 n.1, p.97-106, March 1994 [doi>10.1145/181550.181565]
	29	MACLEOD, I. 1991. Text retrieval and the relational model. J. Am. Soc. Inf. Sci. 42, 3, 155-165.
	30	Amihai Motro, VAGUE: a user interface to relational databases that permits vague queries, ACM Transactions on Information Systems (TOIS), v.6 n.3, p.187-214, July 1988 [doi>10.1145/45945.48027]
	31	Amihai Motro, Accommodating imprecision in database systems: issues and solutions, ACM SIGMOD Record, v.19 n.4, p.69-74, Dec. 1990 [doi>10.1145/122058.122066]
	32	Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	33	Ulrich Pfeifer , Norbert Fuhr, Efficient processing of vague queries using a data stream approach, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.189-197, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215359]
	34	Ulrich Pfeifer , Norbert Fuhr , Tung Huynh, Searching structured documents with the enhanced retrieval functionality of free WAIS-sf and SFgate, Proceedings of the Third International World-Wide Web conference on Technology, tools and applications, p.1027-1036, April 1995, Darmstadt, Germany
	35	PRADE, H. AND TESTEMALE, C. 1984. Generalizing database relational algebra for the treatment of incomplete/uncertain information and vague queries. Inf. Sci. 34, 115-143.
	36	F. Rabitti , P. Savino, Retrieval of multimedia documents by imprecise query specification, Proceedings of the international conference on extending database technology on Advances in database technology, p.203-218, March 1990, Venice, Italy
	37	RAGHAVAN, V., SAXTON, L., WONG, S., AND TING, S. 1986. A unified architecture for the integration of data base management and information retrieval systems. In Information Processing 86, H.-J. Kugler, Ed. Elsevier, Amsterdam, 1049-1054.
	38	REITER, R. 1984. Towards a logical reconstruction of relational database theory. In On Conceptual Modelling, M. Brodie, J. Mylopoulous, and J. Schmidt, Eds. Springer, New York.
	39	ROLLEKE, T. 1994. Equivalences of the probabilistic relational algebra. Tech. Rep., Dept. of Computer Science, Univ. of Dortmund, Dortmund, Germany.
	40	Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
	41	L. V. Saxton , V. V. Raghavan, Design of an Integrated Information Retrieval/Database Management System, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.210-219, June 1990 [doi>10.1109/69.54720]
	42	Hans-Jörg Schek , Peter Pistor, Data Structures for an Integrated Data Base Management and Information Retrieval System, Proceedings of the 8th International Conference on Very Large Data Bases, p.197-207, September 08-10, 1982
	43	Y. Takahashi, Fuzzy Database Query Languages and Their Relational Completeness Theorem, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.122-125, February 1993 [doi>10.1109/69.204096]
	44	VAN RIJSBERGEN, C.J. 1986. A non-classical logic for information retrieval. Comput. J. 29, 6, 481-485.
	45	Yannis Vassiliou, Null values in data base management a denotational semantics approach, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582123]
	46	Gottfried Vossen, Data models, database languages and database management systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	47	Kwok-bun Yue, A more general model for handling missing information in relational databases using a 3-valued logic, ACM SIGMOD Record, v.20 n.3, p.43-49, Sept. 1991 [doi>10.1145/126482.126487]
	48	Maria Zemankova , Abraham Kandel, Implementing imprecision in information systems, Information Sciences: an International Journal, v.37 n.1-3, p.107-141, Dec. 1985 [doi>10.1016/0020-0255(85)90008-8]