Score region algebra: building a transparent XML-R database

ABSTRACT

A unified database framework that will enable better comprehension of ranked XML retrieval is still a challenge in the XML database field. We propose a logical algebra, named score region algebra, that enables transparent specification of information retrieval (IR) models for XML databases. The transparency is achieved by a possibility to instantiate various retrieval models, using abstract score functions within algebra operators, while logical query plan and operator definitions remain unchanged. Our algebra operators model three important aspects of XML retrieval: element relevance score computation, element score propagation, and element score combination. To illustrate the usefulness of our algebra we instantiate four different, well known IR scoring models, and combine them with different score propagation and combination functions. We implemented the algebra operators in a prototype system on top of a low-level database kernel. The evaluation of the system is performed on a collection of IEEE articles in XML format provided by INEX. We argue that state of the art XML IR models can be transparently implemented using our score region algebra framework on top of any low-level physical database engine or existing RDBMS, allowing a more systematic investigation of retrieval model behavior.

REFERENCES

• 1: S. Amer-Yahia , C. Botev , J. Shanmugasundaram, Texquery: a full-text search extension to xquery, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988751]
• 2: Gonzalo Navarro , Ricardo Baeza-Yates, Proximal nodes: a model to query document databases by content and structure, ACM Transactions on Information Systems (TOIS), v.15 n.4, p.400-435, Oct. 1997 [doi>10.1145/263479.263482]
• 3: S. Boag, D. Chamberlin, M.F. Fernandez, D. Florescu, J. Robie, and J. Simeon. XQuery 1.0: An XML Query Language. Technical report, W3C, 2002.
• 4: P. Boncz. Monet: a Next Generation Database Kernel for Query Intensive Applications. PhD thesis, CWI, 2002.
• 5: Forbes J. Burkowski, Retrieval activities in a database consisting of heterogeneous collections of structured text, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.112-125, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133185]
• 6: S. Buxton and M. Rys. XQuery and XPath Full-Text Requirements. Technical report, W3C, 2003.
• 7: J. P. Callan, W. B. Croft, and S. M. Harding. The INQUERY Retrieval System. In Proceedings of the 3rd DEXA Conference, 1992.
• 8: J. Clark and S. DeRose. XML Path Language XPath Version 1.0. Technical report, W3C, 1999.
• 9: C.L.A. Clarke, G.V. Cormack, and F.J. Burkowski. An Algebra for Structured Text Search and a Framework for its Implementation. The Computer Journal, 38(1), 1995.
• 10: Mariano P. Consens , Tova Milo, Algebras for querying text regions (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-22, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212437]
• 11: Daniela Florescu , Donald Kossmann , Ioana Manolescu, Integrating keyword search into XML query processing, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.119-135, June 2000, Amsterdam, The Netherlands
• 12: N. Fuhr. Models for Integrated Information Retrieval and Database Systems. IEEE Data Engineering Bulletin, 19(1), 1996.
• 13: Norbert Fuhr , Kai Großjohann, XIRQL: a query language for information retrieval in XML documents, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-180, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383985]
• 14: Norbert Fuhr , Kai Groβjohann, XIRQL: An XML query language based on information retrieval concepts, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.313-356, April 2004 [doi>10.1145/984321.984326]
• 15: N. Fuhr, M. Lalmas, and S. Malik, editors. Proceedings of the 2nd INEX Workshop, ERCIM Publications, 2004.
• 16: S. Geva. GPX - Gardens Point XML Information Retrieval at INEX 2004. In Proceedings of the 3rd INEX Workshop, LNCS 3493, Springer, 2005.
• 17: N. Gövert, M. Abolhassani, N. Fuhr, and K. Großjohan. Content-oriented XML Retrieval with HyRex. In Proceedings of the 1st INEX Workshop, ERCIM Publications, 2003.
• 18: T. Grabs and H.-J. Shek. Generating Vector Spaces On-the-y for Flexible XML Retrieval. In Proceedings of the XML and Information Retrieval Workshop at 25th ACM SIGIR, 2002.
• 19: David A. Grossman , Ophir Frieder, Information Retrieval: Algorithms and Heuristics, Kluwer Academic Publishers, Norwell, MA, 1998
• 20: T. Grust, S. Sakr, and J. Teubner. XQuery on SQL Hosts. In Proceedings of the 30th VLDB Conference, 2004.
• 21: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 22: D. Hiemstra. Using Language Models for Information Retrieval. PhD thesis, University of Twente, Twente, The Netherlands, 2001.
• 23: Jaap Kamps , Maarten de Rijke , Börkur Sigurbjörnsson, Length normalization in XML retrieval, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009009]
• 24: J. List, V. Mihajlović, A. de Vries, G. Ramirez, and D. Hiemstra. The TIJAH XML-IR System at INEX 2003. In Proceedings of the 2nd INEX Workshop, ERCIM Publications, 2004.
• 25: Y. Mass and M. Mandelbrod. Component Ranking and Automatic Query Refinement for XML Retrieval. InProceedings of the 3rd INEX Workshop, LNCS 3493, Springer, 2005.
• 26: V. Mihajlović, D. Hiemstra, H. E. Blok, and P. M. G. Apers. An XML-IR-DB Sandwich: Is it Better with an Algebra in Between? In Proceedings of the SIGIR Workshop on Information Retrieval and Databases (WIRD'04), 2004.
• 27: V. Mihajlović, G. Ramírez, A. P. de Vries, D. Hiemstra, and H. E. Blok. TIJAH at INEX 2004: Modeling Phrasesm and Relevance Feedback. In Proceedings of the 3rd INEX Workshop, LNCS 3493, Springer, 2005.
• 28: P. Ogilvie and J. Callan. Using Language Models for Flat Text Queries in XML Retrieval. In Proceedings of the 2nd INEX Workshop, ERCIM Publications, 2004.
• 29: J. Pehcevski, J. A. Thom, and A-M. Vercoustre. RMIT INEX Experiments: XML Retrieval Using Lucy/eXist. In Proceedings of the 2nd INEX Workshop, ERCIM Publications, 2004.
• 30: S. E. Robertson , S. Walker, Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.232-241, July 03-06, 1994, Dublin, Ireland
• 31: A. Salminen and F.W. Tompa. PAT Expressions: An Algebra for Text Search. In Proceedings of COMPLEX, 1992.
• 32: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 33: A. Trotman and R. A. O'Keefe. The Simplest Query Language That Could Possibly Work. In Proceedings of the 2nd INEX Workshop, ERCIM Publications, 2004.
• 34: D. Tsichritzis and A. Klug. The ANSI/X3/SPARC DBMS Framework Report of the Study Group on Database Management Systems. Information systems, 3, 1978.
• 35: S. R. Vasanthakumar, J. P. Callan, and W. Bruce Croft. Integrating INQUERY with an RDBMS to Support Text Retrieval. IEEE Data Engineering Bulletin, 19(1), 1996.
• 36: Arjen P. de Vries , Mark G. L. M. van Doorn , Henk M. Blanken , Peter M. G. Apers, The Mirror MMDBMS Architecture, Proceedings of the 25th International Conference on Very Large Data Bases, p.758-761, September 07-10, 1999
• 37: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Design, Experimentation, Performance, Theory, Verification

Keywords:
XML, databases, information retrieval, region algebra, structured documents