×

zbMATH — the first resource for mathematics

Dynamically querying possibilistic XML data. (English) Zbl 1328.68051
Summary: Traditional databases mainly focus on the processing of deterministic data. However, information is often uncertain in practical applications. This paper aims to provide a basic framework for managing possibilistic XML (Extensible Markup Language) data queries in a dynamic environment. Existing efforts are mainly made on querying XML data towards the representation of crisp concepts based on the static labeling schemes. Once an updating operation is involved, these static labeling scheme approaches often need to search the whole original XML document again to relabel all the labels of the nodes. This re-labeling obviously sacrifices the processing performance. Different from the prior work, we adopt a novel dynamic encoding scheme which is tailored for both static and dynamic possibilistic XML documents to effectively avoid re-labeling after updates. On this basis, we propose an efficient algorithm to handle the problem of dynamic twig queries in possibilistic XML documents. Finally, we report our experimental results to show that our algorithm is superior to previous approaches.

MSC:
68P15 Database theory
Software:
ProTDB; XPath
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 PODS, 2001, pp. 150-161.
[2] S. Abiteboul, P. Senellart, Querying and updating probabilistic information in XML, in: Proceedings of EDBT, 2006, pp. 1059-1068.
[3] S. Al-Khalifa et al., Structural joins: a primitive for efficient XML query pattern matching, in: Proceedings of ICDE, 2002, pp. 141-152.
[4] T. Amagasa, M. Yoshikawa, S. Uemura, QRS: a robust numbering scheme for XML documents, in: Proceedings of ICDE, 2003, pp. 705-707.
[5] de Baets, Bernard; de Cooman, Gert; Kerre, Etienne E., The construction of possibility measures from samples on T-semi-partitions, Information Sciences, 106, 3-24, (1998) · Zbl 1031.94555
[6] N. Bruno, N. Koudas, D. Srivastava, Holistic twig joins: optimal XML pattern matching, in: Proceedings of SIGMOD, 2002, pp. 310-321.
[7] Buche, P.; Dibie-Barthelemy, J.; Haemmerle, O.; Hignette, G., Fuzzy semantic tagging and flexible querying of XML documents extracted from the web, Journal of Intelligent Information Systems, 26, 1, 25-40, (2006)
[8] Campi, A.; Damiani, E.; Guinea, S., A fuzzy extension of the xpath query language, Journal of Intelligent Information Systems, 33, 3, 285-305, (2008)
[9] B. Catania et al., Lazy XML updates: laziness as a virtue of update and structural join efficiency, in: Proceedings of SIGMOD, 2005, pp. 515-526.
[10] P. Ceravolo, M.C. Nocerino, M. Viviani, Knowledge extraction from semi-structured data based on fuzzy techniques, in: Proceedings of KES, 2004, pp. 328-334.
[11] E. Cohen, H. Kaplan, T. Milo, Labeling dynamic XML trees, in: Proceedings of PODS, 2002, pp. 271-281. · Zbl 1207.68157
[12] de Cooman, Gert., Possibility theory I: the measure- and integral-theoretic groundwork, International Journal of General Systems, 25, 291-323, (1997) · Zbl 0955.28012
[13] Damiani, E.; Tanca, L.; Arcelli Fontana, F., Fuzzy XML queries via context-based choice of aggregations, Kybernetika, 36, 635-655, (2000) · Zbl 1249.68059
[14] Dubois, D.; Prade, H., Possibility theory, (1988), Plenum New York · Zbl 0645.68108
[15] T. Eda, Y. Sakurai, T. Amagasa, Dynamic range labeling for XML trees, in: Proceedings of EDBT, 2004, pp. 230-239.
[16] B. Fazzinga, S. Flesca, A. Pugliiese, Top-k answers to fuzzy XPath queries, in: Proceedings of DEXA, 2009, pp. 822-829.
[17] 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.
[18] E.S. Hollander, M. van Keulen, Storing and querying probabilistic XML using a probabilistic relational DBMS, in: Proceedings of the 4th International Workshop on Management of Uncertain Data (MUD 2010), 2010, pp. 35-49.
[19] E. Hung, L. Getoor, V.S. Subrahmanian, PXML: a probabilistic semistructured data model and algebra, in: Proceedings of ICDE, 2003, pp. 467-478.
[20] Janssen, Hugo J.; de Cooman, Gert; Kerre, Etienne E., A daniell-Kolmogorov theorem for supremum preserving upper probabilities, Fuzzy Sets and Systems, 102, 429-444, (1999) · Zbl 0941.60005
[21] B. Kimelfeld, Y. Kosharovshy, Y. Sagiv, Query efficiency in probabilistic XML models, in: Proceedings of SIGMOD, 2008, pp. 701-714.
[22] Kimelfeld, B.; Kosharovsky, Y.; Sagiv, Y., Query evaluation over probabilistic XML, The VLDB Journal, 18, 5, 1117-1140, (2009)
[23] B. Kimelfeld, Y. Sagiv, Matching twigs in probabilistic XML, in: Proceedings of VLDB, 2007, pp. 27-38.
[24] C. Li et al., Efficient processing of updates in dynamic XML data, in: Proceedings of ICDE, 2006, pp. 13-13.
[25] Y. Li et al., Holistically twig matching in probabilistic XML, in: Proceedings of ICDE, 2009, pp. 1649-1656.
[26] J. Liu et al., Efficient processing of twig pattern matching in fuzzy XML, in: Proceedings of CIKM, 2009, pp. 193-204.
[27] J. Lu et al., From region encoding to extended Dewey: on efficient processing of XML twig pattern matching, in: Proceedings of VLDB, 2005, pp. 193-204.
[28] Ma, Z. M.; Liu, J.; Yan, Li, Matching twigs in fuzzy XML, Information Sciences, 181, 1, 184-200, (2011) · Zbl 1214.68068
[29] Ma, Z. M.; Yan, L., Fuzzy XML data modeling with the UML and relational data models, Data & Knowledge Engineering, 63, 972-996, (2007)
[30] A. Nierrman, H.V. Jagadish, ProTDB: probabilistic data in XML, in: Proc VLDB, 2002, pp. 646-657.
[31] P. O’Neil et al., ORDPATHs: insert-friendly XML node labels, in: Proceedings of SIGMOD, 2004, pp. 903-908.
[32] J. Pei et al., Probabilistic skylines on uncertain data, in: Proceedings of VLDB, 2007, pp. 15-26.
[33] Sans, V.; Laurent, D., Prefix based numbering schemes for XML: techniques, application and performances, Proceedings of the VLDB Endowment, 1, 2, 1564-1573, (2008)
[34] S. Subramaniam, S.C. Haw, P.K. Hoong, Mapping and labeling XML data for dynamic update, in: Proceedings of the 2nd International Conference on Computer Research and, Development, 2010, pp. 781-786.
[35] ToX XML generator. <http://www.cs.toronto.edu/tox/toxgene>.
[36] Turowski, K.; Weng, U., Representing and processing fuzzy information an XML-based approach, Journal of Knowledge Based Systems, 15, 67-75, (2002)
[37] M. van Keulen, A. de Keijzer, W. Alink, A probabilistic XML approach to data integration, in: Proceedings of ICDE, 2005, pp. 459-470.
[38] X. Wu, M.L. Lee, W. Hsu, A prime number labeling scheme for dynamic ordered XML trees, in: Proceedings of ICDE, 2004, pp. 66-78.
[39] L. Xu et al., DDE: from dewey to a fully dynamic XML labeling scheme, in: Proceedings of SIGMOD, 2009, pp. 719-730.
[40] 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
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.