Interconnection semantics for keyword search in XML

ABSTRACT

A framework for describing semantic relationships among nodes in XML documents is presented. In contrast to earlier work, the XML documents may have ID references (i.e., they correspond to graphs and not just trees). A specific interconnection semantics in this framework can be defined explicitly or derived automatically. The main advantage of interconnection semantics is the ability to pose queries on XML data in the style of keyword search. Several methods for automatically deriving interconnection semantics are presented. The complexity of the evaluation and the satisfiability problems under the derived semantics is analyzed. For many important cases, the complexity is tractable and hence, the proposed interconnection semantics can be efficiently applied to real-world XML documents.

REFERENCES

• 1: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 2: Michael Barg , Raymond K. Wong, Structural proximity searching for large collections of semi-structured data, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502615]
• 3: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 4: S. Cohen, Y. Kanza, J. Mamou, and Y. Sagiv. XSEarch: a semantic search engine for XML. In VLDB, pages 45--56, 2003.
• 5: Sara Cohen , Yaron Kanza , Yehoshua Sagiv, Generating Relations from XML Documents, Proceedings of the 9th International Conference on Database Theory, p.285-299, January 08-10, 2003
• 6: S. Dreyfus and R. Wagner. The Steiner problem in graphs. Networks, 1:195--207, 1972.
• 7: S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:11--121, 1980.
• 8: Roy Goldman , Narayanan Shivakumar , Suresh Venkatasubramanian , Hector Garcia-Molina, Proximity Search in Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.26-37, August 24-27, 1998
• 9: V. Hristidis and Y. Papakonstantinou. DISCOVER: Keyword search in relational databases. In VLDB, pages 670--681, 2002.
• 10: V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keyword proximity search on XML graphs. In ICDE, pages 367--378, 2003.
• 11: F. Hwang, D. Richards, and P. Winter. The Steiner Tree Problem, volume 53 of Annals of Discrete Mathematics. North-Holland, 1992.
• 12: David S. Johnson , Christos H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, v.27 n.3, p.119-123, March 25, 1988 [doi>10.1016/0020-0190(88)90065-8]
• 13: R. Karp. On the complexity of combinatorial problems. Networks, 5:44--68, 1975.
• 14: B. Kimelfeld. Interconnection semantics for XML. Master's thesis, The Hebrew University of Jerusalem, 2004. Available at the author's home page (http://www.cs.huji.ac.il/~bennyk).
• 15: B. Kimelfeld and Y. Sagiv. Efficient engines for keyword proximity search. In WebDB, pages 67--72, 2005.
• 16: B. Kimelfeld and Y. Sagiv. Efficiently enumerating results of keyword search. In DBPL, 2005.
• 17: Y. Li, C. Yu, and H. V. Jagadish. Schema-free XQuery. In VLDB, 2004.
• 18: Anand Rajaraman , Jeffrey D. Ullmann, Querying websites using compact skeletons, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.16-27, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375556]
• 19: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 20: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 21: M. Yannakakis. Algorithms for acyclic database schemas. In VLDB, pages 82--94, 1981.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms

Keywords:
XML, interconnection semantics, keyword search