skip to main content
10.1145/1645953.1645971acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Efficient processing of twig pattern matching in fuzzy XML

Published: 02 November 2009 Publication History

Abstract

In order to find all occurrences of a twig pattern in XML documents, a considerable amount of twig pattern matching algorithms have been proposed. At the same time, previous work mainly focuses on twig pattern query under the complete semantics. However, there is often a need to produce partial answers because XML data may have missing sub-elements. Furthermore, the existed works fall short in their ability to support twig pattern query under different semantics in fuzzy XML. In this paper, we study the problem of twig matches in fuzzy XML. We begin by introducing the extended region scheme to accurately and effectively represent nodes information in fuzzy XML. We then discuss the fuzzy query semantics and compute the membership information by using Einstein operator instead of Zadeh's min-max technique. On the basis, we propose two efficient algorithms for querying twig under complete and incomplete semantics in fuzzy XML. The experimental results show that our proposed algorithms can perform on the fuzzy twig pattern matching efficiently.

References

[1]
Abiteboul S., Segoufin L. and Vianu V. 2001. Representing and Querying XML with Incomplete Information. In Proceedings of 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 150--161.
[2]
Abiteboul S. and Senellart P. 2006. Querying and Updating Probabilistic Information in XML, In Proceedings of. EDBT, 1059--1068.
[3]
Al-Khalifa S., et al.2002. Structural Joins: A Primitive for Efficient XML Query Pattern Matching. In Proceedings of ICDE,141--152.
[4]
Bruno N., Koudas N. and Srivastava D.2002. Holistic Twig Joins: Optimal XML Pattern Matching, In Proceedings of SIGMOD, 310--321.
[5]
Gaurav A. and Alhajj R.2006. Incorporating Fuzziness in XML and Mapping Fuzzy Relational Data into Fuzzy XML. In Proceedings of the 2006 ACM Symposium on Applied Computing, 456--460.
[6]
Hung E., Getoor L.and Subrahmanian V.S.2003. PXML: A Probabilistic Semistructured Data Model and Algebra, In Proceedings of ICDE, 467--478.
[7]
Kanza Y., Nutt W. and Sagiv Y.2002. Querying incomplete information in semistructured data, Journal of Computer and System Sciences 64(3), 655--693.
[8]
Kimelfeld B., Kosharovshy Y. and Sagiv Y.2008. Query Efficiency in Probabilistic XML Models, In Proceedings of. SIGMOD, 701--714.
[9]
Kimelfeld B. and Sagiv Y.2007. Combining Incompleteness and Ranking in Tree Queries, In Proceedings of ICDT, 329--343.
[10]
Kimelfeld B. and Sagiv Y.2007. Matching Twigs in Probabilistic XML, In Proceedings of VLDB, 27--38.
[11]
Klir G., Folder T.1982. Fuzzy Sets, Uncertainty and Information. Prentice Hall.
[12]
Li Y. et al.2009. Holistically Twig Matching in Probabilistic XML, In Proceedings of ICDE, 1649--1656.
[13]
Lu J., Ling T.W., Chan C. and Chen T.2005. From Region Encoding to Extended Dewey: On Efficient Processing of XML Twig Pattern Matching, In Proceedings of VLDB, 193--204.
[14]
Ma Z.M. and. Yan L.2007. Fuzzy XML Data Modeling with the UML and Relational Data Models. Data&Knowledge Engineering. 63, 972--996
[15]
Nierrman A. and Jagadish H.V.2002. ProTDB: Probabilistic Data in XML. In Proceedings of VLDB, 646--657.
[16]
Smets P.1997. Imperfect Information: Imprecision-Uncertainty, Uncertainty Management in Information Systems: From Needs to Solutions. Kluwer Academic Publishers, 225--254.
[17]
Senellart P. and Abiteboul S.2007. On the Complexity of Managing Probabilistic XML Data, In Proceedings of PODS, 283--292.
[18]
Turowski K. and Weng U.2002. Representing and Processing Fuzzy Information-an XML-based Approach. Journal of Knowledge Based Systems, Vol 15, 67--75.
[19]
Van Keulen M., De Keijzer A. and Alink W.2005. A Probabilistic XML Approach to Data Integration. In Proceedings of ICDE, 459--470.
[20]
XMARK the XML--benchmark project. Available from http://monetdb.cwi.nl/xml/index.html.
[21]
Zadeh L. A.1978. Fuzzy Sets as a Basis for a Theory of Possibility. Fuzzy Sets and Systems, 1 (1), 3--28.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management
November 2009
2162 pages
ISBN:9781605585123
DOI:10.1145/1645953
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Einstein operator
  2. fuzzy XML
  3. query semantics
  4. twig matches

Qualifiers

  • Research-article

Conference

CIKM '09
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media