×

zbMATH — the first resource for mathematics

Matching twigs in fuzzy XML. (English) Zbl 1214.68068
Summary: A considerable amount of twig pattern matching algorithms have been proposed to holistically process a twig query. Those algorithms mainly focus on twig pattern query with the AND-logic. However, there is often a need to process a twig query with the OR-predicates. Furthermore, the existing algorithms fall short in their ability to support twig query with OR-logic in fuzzy XML. To overcome this limitation, in this paper, we first introduce a novel encoding scheme to represent node information in fuzzy XML. Based on the encoding scheme, we then propose an effective algorithm for matching a twig pattern query with the AND/OR-logic in fuzzy XML. Our approach adopts a compact stack technique to process the complicated twig query consisting of both AND-logic and OR-logic. More importantly, our method eliminates re-scanning unnecessary portions of XML documents and redundant intermediate results. Finally, the experimental results demonstrate the performance advantages of our approach.

MSC:
68M11 Internet topics
68P05 Data structures
Software:
ProTDB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Abiteboul, L. Segoufin, V. Vianu, Representing and querying XML with incomplete information, in: Proceedings of the 20th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001, pp. 150-161.
[2] S. Abiteboul, P. Senellart, Querying and updating probabilistic information in XML, in: Proceedings of the 10th International Conference on Extending Database Technology, 2006, pp. 1059-1068.
[3] S. Al-Khalifa et al., Structural Joins: a primitive for efficient XML query pattern matching, in: Proceedings of 18th International Conference on Data Engineering, 2002, pp.141-152.
[4] N. Bruno, N.Koudas, D. Srivastava, Holistic twig joins: optimal XML pattern matching, in: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, 2002, pp.310-321.
[5] T. Chen et al., Twig^{2}stack: bottom-up processing of generalized-tree-pattern queries over XML documents, in: Proceedings of the 32nd International Conference on Very Large Data Bases, 2006, pp. 283-294.
[6] T. Chen, J. Lu, Tok Wang Ling, On boosting holism in XML twig pattern matching using structural indexing techniques, in: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, 2005, pp. 455-466.
[7] 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.
[8] E. Hung, L. Getoor, V.S. Subrahmanian, PXML: a probabilistic semistructured data model and algebra, in: Proceedings of 19th International Conference on Data Engineering, 2003, pp. 467-478.
[9] H. Jiang, H. Lu, W. Wang, Efficient processing of XML twig queries with OR-predicates, in: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, 2004, pp. 59-70.
[10] H. Jiang, W. Wang, H. Lu, J. Yu. Holistic twig joins on indexed XML documents, in: Proceedings of the 29th International Conference on Vary large Data Bases, 2003, pp. 273-284.
[11] Kanza, Y.; Nutt, W.; Sagiv, Y., Querying incomplete information in semistructured data, Journal of computer and system sciences, 64, 3, 655-693, (2002) · Zbl 1015.68063
[12] B. Kimelfeld, Y. Kosharovshy, Y. Sagiv, Query efficiency in probabilistic XML models, in: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, 2008, pp. 701-714.
[13] B. Kimelfeld, Y. Sagiv, Combining incompleteness and ranking in tree queries, in: Proceedings of the 11th International Conference on Database Theory, 2007, pp. 329-343.
[14] B. Kimelfeld, Y. Sagiv, Matching twigs in probabilistic XML, in: Proceedings of the 33rd International Conference on Vary large Data Bases, 2007, pp. 27-38.
[15] Klir, G.; Folder, T., Fuzzy sets, uncertainty and information, (1982), Prentice Hall
[16] Y. Li et al., Holistically twig matching in probabilistic XML, in: Proceedings of 25th International Conference on Data Engineering, 2009, pp. 1649-1656.
[17] J. Liu, Z.M. Ma, L. Yan, Efficient processing of twig pattern matching in fuzzy XML, in: Proceedings of the 18th ACM Conference on Information and Knowledge Management, 2009, pp. 193-204.
[18] J. Lu, T. Chen, T.W. Ling, Efficient processing of XML twig patterns with parent child edges: a look-ahead approach, in: Proceedings of the 13th ACM International Conference on Information and Knowledge Management, 2004, pp. 533-542.
[19] 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 the 31st International Conference on Vary large Data Bases, 2005, pp. 193-204.
[20] Ma, Z.M.; Yan, L., Fuzzy XML data modeling with the UML and relational data models, Data & knowledge engineering., 63, 972-996, (2007)
[21] C. Mathis, T. Harder, M. Haustein, Locking-aware structural join operators for XML query processing, in: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, 2006, pp. 467-478.
[22] A. Nierrman, H.V. Jagadish, ProTDB: probabilistic data in XML, in: Proceedings of the 28th International Conference on Vary large Data Bases, 2002, pp. 646-657.
[23] B. Oliboni, G. Pozzani, Representing fuzzy information by using XML schema, in: Proceedings of the 19th International Conference on Database and Expert Systems Application, 2008, pp. 683-687.
[24] Smets, P., Imperfect information: imprecision-uncertainty, uncertainty management in information systems: from needs to solutions, (1997), Kluwer Academic Publishers., pp. 225-254
[25] P. Senellart, S. Abiteboul, On the complexity of managing probabilistic XML data, in: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007, pp. 283-292.
[26] Turowski, K.; Weng, U., Representing and processing fuzzy information-an XML-based approach, Journal of knowledge based systems, 15, 67-75, (2002)
[27] M. Van Keulen, A. De Keijzer, W. Alink, A probabilistic XML approach to data integration, in: Proceedings of 21st International Conference on Data Engineering, 2005, pp. 459-470.
[28] XMARK the XML-benchmark project. Available from <http://monetdb.cwi.nl/xml/index.html>.
[29] L. Yan, Z.M. Ma, J. Liu, Fuzzy data modeling based on XML schema, in: Proceedings of 2009 ACM Symposium on Applied Computing, 2009, pp. 1563-1567.
[30] Zadeh, L.A., Fuzzy sets as a basis for a theory of possibility, Fuzzy sets and systems, 1, 1, 3-28, (1978) · Zbl 0377.04002
[31] Zadeh, L.A., Is there a need for fuzzy logic?, Information sciences, 178, 13, 2751-2779, (2008) · Zbl 1148.68047
[32] Zadeh, L.A., Toward a generalized theory of uncertainty (gtu)-an outline, Information sciences, 172, 1-2, 1-40, (2005) · Zbl 1074.94021
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.