Efficient processing of twig query with compound predicates in fuzzy XML. (English) Zbl 1284.68232

Summary: In order to find all occurrences of a twig pattern in XML documents, a considerable number of twig pattern matching algorithms have been proposed. Previous algorithms mainly focus on the conjunctive twig queries whose sibling edges are only connected by AND connectives. However, meaningful twig queries typically contain arbitrarily specified compound predicates including AND, OR and NOT in practical applications. Moreover, as far as we know, none of these twig matching algorithms have examined the processing of twig queries which contain all the compound predicates over fuzzy XML data. In this paper, we present the first study on evaluating twig queries with AND, OR and NOT connectives in fuzzy XML. We propose a novel holistic twig matching algorithm called LTwig for answering these complex queries. Our algorithm guarantees that the answers can be obtained by scanning the relevant data of the data streams associated with the nodes appearing in the twig pattern only once. A comprehensive set of experiments is finally carried out to demonstrate the effectiveness and efficiency of our proposed approach.


68P15 Database theory


Full Text: DOI


[1] N. Bruno, N. Koudas, D. Srivastava, Holistic twig joins: optimal XML pattern matching, in: Proceedings of SIGMOD, 2002, pp. 310-321.
[2] H. Jiang, W. Wang, H. Lu, X.Y. Jeffrey, Holistic twig joins on indexed XML documents, in: Proceedings of VLDB, 2003, pp. 273-284.
[3] Koyuncu, M.; Yazici, A., Ifoodan intelligent fuzzy object-oriented database architecture, IEEE Trans. Knowl. Eng., 15, 5, 1137-1154, (2003)
[4] Zadeh, L. A., Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets Syst., 1, 1, 3-28, (1978) · Zbl 0377.04002
[5] Zadeh, L. A., Fuzzy sets, Inf. Control, 8, 3, 338-353, (1965) · Zbl 0139.24606
[6] Raju, K. V.S. V.N.; Majumdar, A. K., Fuzzy functional dependencies and lossless join decomposition of fuzzy relational database systems, ACM Trans. Database Syst., 13, 2, 129-166, (1988)
[7] Yager, R. R., Targeted E-commerce marketing using fuzzy intelligent agents, IEEE Intell. Syst., 15, 6, 42-45, (2000)
[8] S. Abiteboul, L. Segoufin, V. Vianu, Representing and querying XML with incomplete information, in: Proceedings of 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001, pp. 150-161.
[9] S. Abiteboul, P. Senellart, Querying and updating probabilistic information in XML, in: Proceedings of EDBT, 2006, pp. 1059-1068.
[10] E. Hung, L. Getoor, V.S. Subrahmanian. PXML: a probabilistic semistructured data model and algebra, in: Proceedings of ICDE, 2003, pp. 467-478.
[11] B. Kimelfeld, Y. Sagiv, Matching twigs in probabilistic XML, in: Proceedings of VLDB, 2007, pp. 27-38.
[12] A. Nierrman, H.V. Jagadish, ProTDB: probabilistic data in XML, in: Proceedings of VLDB, 2002, pp. 646-657.
[13] A. Gaurav, R. Alhajj, Incorporating fuzziness in XML and mapping fuzzy relational data into fuzzy XML, in: Proceedings of the 2006 ACM Symposium on Applied Computing, 2006, pp. 456-460.
[14] Damiani, E.; Tanca, L.; Arcelli Fontana, F., Fuzzy XML queries via context-based choice of aggregations, Kybernetika, 36, 635-655, (2000) · Zbl 1249.68059
[15] Lee, Edward T., Fuzzy tree automata and syntactic pattern recognition, IEEE Trans. Pattern Anal. Mach. Intell., 4, 4, 445-449, (1982) · Zbl 0483.68076
[16] S. Al-Khalifa, H.V. Jagadish, N. Koudas, et al., Structural joins: a primitive for efficient XML query pattern matching, in: Proceedings of ICDE, 2002, pp. 141-152.
[17] B. Kimelfeld, Y. Kosharovsky, Y. Sagiv, Query efficiency in probabilistic XML models, in: Proceedings of SIGMOD, 2008, pp. 701-714.
[18] Y. Li, G. Wang, J. Xin, et al., Holistically twig matching in probabilistic XML, in: Proceedings of ICDE, 2009, pp. 1649-1656.
[19] J. Liu, Z.M. Ma, L. Yan, Efficient processing of twig pattern matching in fuzzy XML, in: Proceedings of CIKM, 2009, pp. 117-126.
[20] J. Lu, T.W. Ling, C. Chan, T. Chen, From region encoding to extended Dewey: on efficient processing of XML twig pattern matching, in: Proceedings of VLDB, 2005, pp. 193-204.
[21] Cohen, S.; Sagiv, Y.; Nutt, W., Equivalences among aggregate queries with negation, ACM Trans. Comput. Logic, 6, 2, 28-360, (2005) · Zbl 1367.68085
[22] Dung, P.; Mancarella, P., Production systems with negation as failure, IEEE Trans. Knowl. Eng., 14, 2, 336-352, (2002)
[23] Flesca, S.; Greco, S., Rewriting queries using views, IEEE Trans. Knowl. Eng., 13, 6, 980-995, (2001)
[24] Mugnier, M.; Leclere, M., On querying simple conceptual graphs with negation, Data Knowl. Eng., 60, 3, 468-493, (2007)
[25] E. Jiao, T. W. Ling, C. Chan, Pathstack \(\neg\): a holistic path join algorithm for path query with NOT-predicates on XML data, in: Proceedings of DASFAA, 2005, pp. 113-124.
[26] H. Li, M. Lee, W. Hsu, L. Li, A path-based approach for efficient structural join with NOT-predicates, in: Proceedings of DASFAA, 2007, pp. 31-42.
[27] T. Yu, T.W. Ling, J. Lu, TwigStackList \(\neg\): a holistic twig join algorithm for twig query with NOT-predicates on XML data, in: proceedings of DASFAA, 2006, pp. 249-263.
[28] H. Jiang, H. Lu, W. Wang, Efficient processing of XML twig queries with OR-predicates, in: Proceedings of SIGMOD, 2006, pp. 59-70.
[29] D. Che, Holistically processing XML twig queries with AND, OR and NOT predicates, in: Proceedings of Infoscale, vol. 53, 2007.
[30] X. Xu, Y. Feng, F. Wang, Efficient processing of XML twig queries with all predicates, in: Proceedings of ACIS-ICIS, 2009, pp. 457-462.
[31] Ma, Z. M.; Liu, J.; Yan, L., Matching twigs in fuzzy XML, Inf. Sci., 181, 1, 184-200, (2011) · Zbl 1214.68068
[32] Benferhat, S.; Dubois, D.; Garcia, L.; Prade, H., On the transformation between possibilistic logic bases and possibilistic causal networks, Int. J. Approx. Reason., 29, 2, 135-173, (2002) · Zbl 1015.68204
[33] XMARK the XML-benchmark project, available from \(‹\)http://monetdb.cwi.nl/xml/index.html\(›\).
[34] W. Yang, Z. Hao, Matching of twig pattern with AND/OR predicates over XML streams, in: Zhongyu (Joan) Lu (Ed.), Design, Performance, and Analysis of Innovative Information Retrieval, 2013, pp. 60-72, accessed August 05, 2012. doi:10.4018/978-1-4666-1975-3.ch005.
[35] Klir, G.; Folder, T., Fuzzy sets, uncertainty and information, (1982), Prentice Hall
[36] K. Lee, K. Lee, J. Lee, H. Lee-Kwang, A fuzzy decision tree induction method for fuzzy data, in: Proceedings of IEEE International Fuzzy Systems Conference Proceedings, 1999, pp. 16-21.
[37] P. Billaudel, A. Devillez, G. Villermain Lecolier, Unsupervised fuzzy classification method based on a fuzzy proximity graph and on a graduated hierarchy, in: Proceedings of IEEE International Fuzzy Systems Conference Proceedings, 1999, pp. 1054-1058. · Zbl 1184.62105
[38] Benferhat, Salem; Smaoui, Salma, Hybrid possibilistic networks, Int. J. Approx. Reason., 44, 3, 224-243, (2007) · Zbl 1116.68094
[39] Turowski, K.; Weng, U., Representing and processing fuzzy information—an XML-based approach, Knowl. Based Syst., 15, 1, 67-75, (2002)
[40] J. Lee, Y.Y. Fanjiang, J. Kuo, Y. Lin, Modeling imprecise requirements with XML, in: Proceedings of IEEE International Fuzzy Systems Conference Proceedings, 2002, pp. 861-866.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.