Answering ordered tree pattern queries over fuzzy XML data

详细信息    查看全文

• 作者：Jian Liu (1)
  Z. M. Ma (1)
  Xue Feng (2)
  
  1. School of Information Science and Engineering ; Northeastern University ; Shenyang ; 110004 ; China
  2. The General Hospital of Shenyang Military Command ; Shenyang ; 110004 ; China
  
• 关键词：Tree pattern ; Fuzzy XML ; Order ; based queries ; Matching
• 刊名：Knowledge and Information Systems
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：43
• 期：2
• 页码：473-495
• 全文大小：1,550 KB
• 参考文献：1. Abiteboul S, Segoufin L, Vianu V (2001) Representing and querying XML with incomplete information. In: Proceedings of the ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, pp 150鈥?61
  2. Abiteboul S, Senellart P (2006) Querying and updating probabilistic information in XML. In: Proceedings of the international conference on extending database technology, pp 1059鈥?068
  3. Al-Khalifa S, Jagadish H, Koudas N et al (2002) Structural joins: a primitive for efficient XML query pattern matching. In: Proceedings of the IEEE international conference on data engineering, pp 141鈥?52
  4. Bruno N, Koudas N, Srivastava D (2002) Holistic twig joins: optimal XML pattern matching. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 310鈥?21
  5. Cohen S, Kimelfeld B, Sagiv Y (2008) Incorporating constraints in probabilistic XML. In: Proceedings of the ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, pp 109鈥?18
  6. Damiani, E, Tanca, L, Arcelli, F (2000) Fuzzy XML queries via context-based choice of aggregations. Kybernetika 36: pp. 635-655
  7. El-Sayed, M, Dimitrova, K, Rundensteiner, E (2005) Efficiently supporting order in XML query processing. Data Knowl Eng 54: pp. 355-390 CrossRef
  8. Gaurav A, 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, pp 456鈥?60
  9. Hung E, Getoor L, Subrahmanian VS (2003) PXML: a probabilistic semistructured data model and algebra. In: Proceedings of the IEEE international conference on data, engineering, pp 467鈥?78
  10. Jampani R, Xu F, Wu M (2008) MCDB: a Monte Carlo approach to managing uncertain data. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 687鈥?00
  11. Jiang H, Wang W, Lu H et al (2003) Holistic twig joins on indexed XML socuments. In: Proceedings of the ACM international conference on very large data bases, pp 273鈥?84
  12. Kimelfeld B, Kosharovsky Y, Sagiv Y (2008) Query efficiency in probabilistic XML models. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 701鈥?14
  13. Kimelfeld B, Sagiv Y (2007) Matching twigs in probabilistic XML. In: Proceedings of the ACM international conference on very large data, bases, pp 27鈥?8
  14. Klir, G, Folder, T (1982) Fuzzy sets, uncertainty and information. Prentice-Hall, Englewood Cliffs
  15. Koyuncu, M, Yazici, A (2003) IFOOD: an intelligent fuzzy object-oriented database architecture. IEEE Trans Knowl Eng 15: pp. 1137-1154 CrossRef
  16. Lee J, Fanjiang Y, Kuo J et al (2002) Modeling imprecise requirements with XML. In: Proceedings of IEEE international fuzzy systems conference proceedings, pp 861鈥?66
  17. Li Y, Wang G, Xin J et al (2009) Holistically twig matching in probabilistic XML. In : Proceedings of the IEEE international conference on data engineering, pp 1649鈥?656
  18. Liu J, Ma ZM, Yan L (2009) Efficient processing of twig pattern matching in fuzzy XML. In: Proceedings of the ACM international conference on information and knowledge management, pp 117鈥?26
  19. Liu, J, Ma, ZM, Yan, L (2013) Querying and ranking incomplete twigs in probabilistic XML. World Wide Web 16: pp. 325-353 CrossRef
  20. Lu J, Ling T W, Chan C et al (2005) From region encoding to extended dewey: on efficient processing of XML twig pattern matching. In: Proceedings of the ACM international conference on very large data bases, pp 193鈥?04
  21. Lu J, Ling T W, Yu T et al (2005) Efficient processing of ordered XML twig pattern. In: Proceedings of the international conference on database and expert systems applications, pp 300鈥?09
  22. Ma, ZM, Liu, J, Yan, L (2011) Matching twigs in fuzzy XML. Inf Sci 181: pp. 184-200 CrossRef
  23. Moro M, Vagena Z, Tsotras V (2005) Tree-pattern queries on a lightweight XML processor. In: Proceedings of the ACM international conference on very large sata, bases, pp 205鈥?16
  24. Nierrman A, Jagadish HV (2002) ProTDB: probabilistic data in XML. In: Proceedings of the ACM international conference on very large data, bases, pp 646鈥?57
  25. Pei J, Jiang B, Lin X et al (2007) Probabilistic skylines on uncertain data. In: Proceedings of the ACM international conference on very large data bases, pp 15鈥?6
  26. Raju, K, Majumdar, A (1988) Fuzzy functional dependencies and lossless join decomposition of fuzzy relational database systems. ACM Trans Database Syst 13: pp. 129-166 CrossRef
  27. Senellart P, Abiteboul S (2007) On the complexity of managing probabilistic XML data. In: Proceedings of the ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, pp 283鈥?92
  28. Tatarinov I, Viglas S, Beyer K et al (2002) Storing and querying ordered XML using a relational database system. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 204鈥?15
  29. Turowskia, K, Weng, U (2002) Representing and processing fuzzy information-an XML-based approach. Knowl Based Syst 15: pp. 67-75 CrossRef
  30. University of Washington XML Repository. http://www.cs.washington.edu/research/xmldatasets/
  31. XMARK the XML-benchmark project. http://monetdb.cwi.nl/xml/index.html
  32. Yager R (2000) Targeted E-commerce marketing using fuzzy intelligent agents. IEEE Intell Syst 15(6): 42鈥?5
  33. Zadeh, LA (1965) Fuzzy sets. Inf Control 8: pp. 338-353 CrossRef
  34. Zadeh, LA (1978) Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets Syst 1: pp. 3-28 CrossRef
  
• 刊物类别：Computer Science
• 刊物主题：Information Systems and Communication Service
  Business Information Systems
  
• 出版者：Springer London
• ISSN：0219-3116

文摘

The widespread employment of XML requires the development of efficient methods to support advanced tree pattern queries. In addition, in real-world applications that involve analysis and management of databases, uncertainty is often an inherent property of data. Although a large number of researches have been dedicated to modeling uncertain XML and answering queries over uncertain XML data, how to conduct order-based tree pattern queries on fuzzy XML data remains an open problem. In this work, we aim to fill this gap and tackle the problem of order-based queries on fuzzy XML data. Based on the node encoding, we propose efficient tree pattern matching algorithms serving for ordered queries over fuzzy XML data. In particular, our algorithms adopt a two-phase processing technique: the first phase generates the root-to-leaf path solutions, and the second phase merges these path solutions for producing the desired matches to the ordered tree pattern. Typically, our approach only needs to access data related to the query nodes in the tree pattern once to obtain all the matching answers. Finally, a comprehensive experimental evaluation is carried out to investigate the performance of the proposed approaches.