{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:04:47Z","timestamp":1754157887595,"version":"3.41.2"},"reference-count":36,"publisher":"Emerald","issue":"1","license":[{"start":{"date-parts":[[2008,4,4]],"date-time":"2008-04-04T00:00:00Z","timestamp":1207267200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.emerald.com\/insight\/site-policies"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,4,4]]},"abstract":"<jats:sec><jats:title content-type=\"abstract-heading\">Purpose<\/jats:title><jats:p>Estimating the sizes of query results and intermediate results is crucial to many aspects of query processing. All database systems rely on the use of cardinality estimates to choose the cheapest execution plan. In principle, the problem of cardinality estimation is more complicated in the Extensible Markup Language (XML) domain than the relational domain. The purpose of this paper is to present a novel framework for estimating the cardinality of XQuery expressions as well as their sub\u2010expressions. Additionally, this paper proposes a novel XQuery cardinality estimation benchmark. The main aim of this benchmark is to establish the basis of comparison between the different estimation approaches in the XQuery domain.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Design\/methodology\/approach<\/jats:title><jats:p>As a major innovation, the paper exploits the relational algebraic infrastructure to provide accurate estimation in the context of XML and XQuery domains. In the proposed framework, XQuery expressions are translated into an equivalent relational algebraic plans and then using a well defined set of inference rules and a set of special properties of the algebraic plan, this framework is able to provide high\u2010accurate estimation for XQuery expressions.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Findings<\/jats:title><jats:p>This paper is believed to be the first which provides a uniform framework to estimate the cardinality of more powerful XML querying capabilities using XQuery expressions as well as their sub\u2010expressions. It exploits the relational algebraic infrastructure to provide accurate estimation in the context of XML and XQuery domains. Moreover, the proposed framework can act as a meta\u2010model through its ability to incorporate different summarized XML structures and different histogram techniques which allows the model designers to achieve their targets by focusing their effort on designing or selecting the adequate techniques for them. In addition, this paper proposes benchmark for XQuery cardinality estimation systems. The proposed benchmark distinguishes itself from the other existing XML benchmarks in its focus on establishing the basis for comparing the different estimation approaches in the XML domain in terms of their accuracy of the estimations and their completeness in handling different XML querying features.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Research limitations\/implications<\/jats:title><jats:p>The current status of this proposed XQuery cardinality estimations framework does not support the estimation of the queries over the order information of the source XML documents and does not support non\u2010numeric predicates.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Practical implications<\/jats:title><jats:p>The experiments of this XQuery cardinality estimation system demonstrate its effectiveness and show high\u2010accurate estimation results. Utilizing the cardinality estimation properties during the SQL translation of XQuery expression results in an average improvement of 20 percent on the performance of their execution times.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Originality\/value<\/jats:title><jats:p>This paper presents a novel framework for estimating the cardinality of XQuery expressions as well as its sub\u2010expressions. A novel XQuery cardinality estimation benchmark is introduced to establish the basis of comparison between the different estimation approaches in the XQuery domain.<\/jats:p><\/jats:sec>","DOI":"10.1108\/17440080810865611","type":"journal-article","created":{"date-parts":[[2008,4,12]],"date-time":"2008-04-12T07:13:18Z","timestamp":1207984398000},"page":"6-47","source":"Crossref","is-referenced-by-count":4,"title":["Algebra\u2010based XQuery cardinality estimation"],"prefix":"10.1108","volume":"4","author":[{"given":"Sherif","family":"Sakr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","reference":[{"key":"key2022030920152568500_b3","unstructured":"Aboulnaga, A., Alameldeen, A.R. and Naughton, J.F. (2001), \u201cEstimating the selectivity of XML path expressions for internet scale applications\u201d, Proceedings of the 27th International Conference on Very Large Data Bases (VLDB), Roma, Italy, pp. 591\u2010600."},{"key":"key2022030920152568500_b4","unstructured":"Berleant, D. (1993), \u201cAutomatically verified reasoning with both intervals and probability density functions\u201d, Interval Computations, Vol. 2, pp. 48\u201070."},{"key":"key2022030920152568500_b5","unstructured":"Boag, S., Chamberlin, D., Fern\u00e1ndez, M.F., Florescu, D., Robie, J. and Sim\u00e9on, J. (2006), \u201cXQuery 1.0: an XML query language \u2013 world wide web consortium proposed recommendation\u201d, available at: www.w3.org\/TR\/xquery."},{"key":"key2022030920152568500_b6","doi-asserted-by":"crossref","unstructured":"B\u00f6hme, T. and Rahm, E. (2001), \u201cXMach\u20101: a benchmark for XML data management\u201d, Datenbanksysteme in B\u00fcro, Technik und Wissenschaft (BTW) 9, GI\u2010Fachtagung, London, UK, pp. 264\u201073.","DOI":"10.1007\/978-3-642-56687-5_20"},{"key":"key2022030920152568500_b7","unstructured":"Boncz, P.A. (2002), \u201cMonet: a next\u2010generation DBMS kernel for query\u2010intensive applications\u201d, PhD thesis, Universiteit van Amsterdam, Amsterdam."},{"key":"key2022030920152568500_b8","doi-asserted-by":"crossref","unstructured":"Boncz, P.A., Grust, T., Van Keulen, M., Manegold, S., Rittinger, J. and Teubner, J. (2006), \u201cMonetDB\/XQuery: a fast XQuery processor powered by a relational engine\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Chicago, IL, USA, pp. 479\u201090.","DOI":"10.1145\/1142473.1142527"},{"key":"key2022030920152568500_b9","unstructured":"Brantner, M., Helmer, S., Kanne, C\u2010C. and Moerkotte, G. (2005), \u201cFull\u2010fledged algebraic XPath processing in Natix\u201d, Proceedings of the 21st International Conference on Data Engineering (ICDE), Tokyo, Japan, pp. 705\u201016."},{"key":"key2022030920152568500_b10","unstructured":"Bray, T., Paoli, J., Sperberg\u2010McQueen, C.M., Maler, E. and Yergeau, F. (2006), \u201cWorld Wide Web Consortium, Extensible Markup Language (XML) 1.0\u201d, 4th ed., available at: www.w3.org\/TR\/xml."},{"key":"key2022030920152568500_b11","doi-asserted-by":"crossref","unstructured":"Chen, Z., Jagadish, H.V., Lakshmanan, L.V.S. and Paparizos, S. (2003), \u201cFrom tree patterns to generalized tree patterns: on efficient evaluation of XQuery\u201d, Proceedings of the 29th International Conference on Very Large Data Bases (VLDB), Berlin, Germany, pp. 237\u201048.","DOI":"10.1016\/B978-012722442-8\/50029-X"},{"key":"key2022030920152568500_b12","unstructured":"Fern\u00e1ndez, M.F., Malhotra, A., Marsh, J., Nagy, M. and Walsh, N. (2006), \u201cXQuery 1.0 and XPath 2.0 data model (XDM) \u2013 world wide web consortium proposed recommendation\u201d, available at: www.w3.org\/TR\/xpath\u2010datamodel."},{"key":"key2022030920152568500_b13","doi-asserted-by":"crossref","unstructured":"Fisher, D. and Maneth, S. (2007), \u201cStructural selectivity estimation for XML documents\u201d, Proceedings of the 23rd International Conference on Data Engineering (ICDE), Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367908"},{"key":"key2022030920152568500_b14","doi-asserted-by":"crossref","unstructured":"Freire, J., Haritsa, J.R., Ramanath, M., Roy, P. and Sim\u00e9on, J. (2002), \u201cStatiX: making XML count\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Madison, WI, USA, pp. 181\u201091.","DOI":"10.1145\/564691.564713"},{"key":"key2022030920152568500_b15","unstructured":"Goldman, R. and Widom, J. (1997), \u201cDataGuides: enabling query formulation and optimization in semistructured databases\u201d, Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB), Athens, Greece, pp. 436\u201045."},{"key":"key2022030920152568500_b16","doi-asserted-by":"crossref","unstructured":"Grust, T. (2002), \u201cAccelerating XPath location steps\u201d, Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, WI, USA, pp. 109\u201020.","DOI":"10.1145\/564691.564705"},{"key":"key2022030920152568500_b17","unstructured":"Grust, T. (2005), \u201cPurely relational FLWORs\u201d, Proceedings of the 2nd International Workshop on XQuery Implementation, Experience and Perspectives (XIME\u2010P), in Cooperation with ACM SIGMOD, Baltimore, MD, USA."},{"key":"key2022030920152568500_b18","doi-asserted-by":"crossref","unstructured":"Grust, T., Sakr, S. and Teubner, J. (2004), \u201cXQuery on SQL hosts\u201d, Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Toronto, Canada, pp. 252\u201063.","DOI":"10.1016\/B978-012088469-8.50025-5"},{"key":"key2022030920152568500_b19","doi-asserted-by":"crossref","unstructured":"Grust, T., Mayr, M., Rittinger, J., Sakr, S. and Teubner, J. (2007), \u201cA SQL: 1999 code generator for the Pathfinder XQuery compiler\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China.","DOI":"10.1145\/1247480.1247642"},{"key":"key2022030920152568500_b21","unstructured":"Ioannidis, Y.E. (1993), \u201cUniversality of serial histograms\u201d, Proceedings of the 19th International Conference on Very Large Data Bases (VLDB), San Francisco, CA, USA, pp. 256\u201067."},{"key":"key2022030920152568500_b22","doi-asserted-by":"crossref","unstructured":"Jagadish, H.V., Lakshmanan, L.V.S., Srivastava, D. and Thompson, K. (2001), \u201cTAX: a tree algebra for XML\u201d, Proceedings of the 8th International Workshop of Database Programming Languages (DBPL), Frascati, Italy, pp. 149\u201064.","DOI":"10.1007\/3-540-46093-4_9"},{"key":"key2022030920152568500_b23","unstructured":"Li, H., Lee, M\u2010L., Hsu, W. and Cong, G. (2006), \u201cAn estimation system for XPath expressions\u201d, Proceedings of the 22nd International Conference on Data Engineering (ICDE), Atlanta, GA, USA, p. 54."},{"key":"key2022030920152568500_b24","doi-asserted-by":"crossref","unstructured":"Lim, L., Wang, M., Padmanabhan, S., Vitter, J.S. and Parr, R. (2002), \u201cXPathlearner: an on\u2010line self\u2010tuning Markov histogram for XML path selectivity estimation\u201d, Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), Hong Kong, China, pp. 442\u201053.","DOI":"10.1016\/B978-155860869-6\/50046-9"},{"key":"key2022030920152568500_b25","doi-asserted-by":"crossref","unstructured":"Nicola, M., Kogan, I. and Schiefer, B. (2007), \u201cAn XML transaction processing benchmark\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, New York, NY, USA, pp. 937\u201048.","DOI":"10.1145\/1247480.1247590"},{"key":"key2022030920152568500_b26","unstructured":"Paparizos, S., Al\u2010Khalifa, S., Jagadish, H., Niermann, A. and Wu, Y. (2002), A Physical Algebra for XML, Technical Report, University of Michigan, Dearborn, MI."},{"key":"key2022030920152568500_b27","doi-asserted-by":"crossref","unstructured":"Poosala, V., Ioannidis, Y.E., Haas, P.J. and Shekita, E.J. (1996), \u201cImproved histograms for selectivity estimation of range predicates\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Quebec, pp. 294\u2010305.","DOI":"10.1145\/235968.233342"},{"key":"key2022030920152568500_b28","doi-asserted-by":"crossref","unstructured":"Re, C., Sim\u00e9on, J. and Fern\u00e1ndez, M.F. (2006), \u201cA complete and efficient algebraic compiler for XQuery\u201d, Proceedings of the 22nd International Conference on Data Engineering (ICDE), Atlanta, GA, USA, p. 14.","DOI":"10.1109\/ICDE.2006.6"},{"key":"key2022030920152568500_b29","unstructured":"Rittinger, J. (2005), \u201cPathfinder\/MonetDB: a relational runtime for XQuery\u201d, Master's thesis, Konstanz University, Konstanz."},{"key":"key2022030920152568500_b30","unstructured":"Sakr, S. (2007), \u201cCardinality\u2010aware and purely relational implementation of an XQuery processor\u201d, PhD thesis, University of Konstanz, Konstanz, available at: www.ub.uni\u2010konstanz.de\/kops\/volltexte\/2007\/3259."},{"key":"key2022030920152568500_b31","doi-asserted-by":"crossref","unstructured":"Sartiani, C. (2003), \u201cA general framework for estimating XML query cardinality\u201d, Proceedings of the 9th International Database Programming Languages Workshop (DBPL), Potsdam, Germany, pp. 257\u201077.","DOI":"10.1007\/978-3-540-24607-7_16"},{"key":"key2022030920152568500_b32","unstructured":"Sartiani, C. and Albano, A. (2002), \u201cYet another query algebra for XML data\u201d, Proceedings of the International Database Engineering & Applications Symposium (IDEAS), Edmonton, Canada, pp. 106\u201015."},{"key":"key2022030920152568500_b33","doi-asserted-by":"crossref","unstructured":"Schmidt, A., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I. and Busse, R. (2002), \u201cXMark: a benchmark for XML data management\u201d, Proceedings of the 28th International Conference on Very Large Data Bases (VLDB), Hong Kong, China, pp. 974\u201085.","DOI":"10.1016\/B978-155860869-6\/50096-2"},{"key":"key2022030920152568500_b34","doi-asserted-by":"crossref","unstructured":"Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A. and Price, T.G. (1979), \u201cAccess path selection in a relational database management system\u201d, Proceedings of the ACM SIGMOD International Conference on Management of Data, Boston, MA, USA, pp. 23\u201034.","DOI":"10.1145\/582095.582099"},{"key":"key2022030920152568500_b35","unstructured":"Teubner, J. (2006), \u201cPathfinder: XQuery compilation techniques for relational database targets\u201d, PhD thesis, Technical University of Munich, Munich."},{"key":"key2022030920152568500_b36","doi-asserted-by":"crossref","unstructured":"Wang, W., Jiang, H., Lu, H. and Yu, J.X. (2004), \u201cBloom histogram: path selectivity estimation for XML data with updates\u201d, Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), Toronto, Canada, pp. 240\u201051.","DOI":"10.1016\/B978-012088469-8\/50024-3"},{"key":"key2022030920152568500_b37","doi-asserted-by":"crossref","unstructured":"Yao, B.B., \u00d6zsu, M.T. and Keenleyside, J. (2003), \u201cXBench \u2013 a family of benchmarks for XML DBMSs\u201d, Proceedings of the VLDB 2002 Workshop EEXTT and CAiSE 2002 Workshop DTWeb on Efficiency and Effectiveness of XML Tools and Techniques and Data Integration over the Web\u2010Revised Papers, London, UK, pp. 162\u20104.","DOI":"10.1007\/3-540-36556-7_14"},{"key":"key2022030920152568500_b20","unstructured":"Zhang, H. and Tompa, F.W. (2003), \u201cXQuery rewriting at the algebraic level\u201d, Trends in XML Technology for the Global Information Infrastructure, a special issue of Journal of Computer Systems, Science, and Engineering, Vol. 18 No. 5, pp. 241\u201062."},{"key":"key2022030920152568500_b2","unstructured":"Zhang, N., \u00d6zsu, M.T., Aboulnaga, A. and Ilyas, I.F. (2006), \u201cXSeed: accurate and fast cardinality estimation for XPath queries\u201d, Proceedings of the 22nd International Conference on Data Engineering (ICDE), Atlanta, GA, USA, p. 61."}],"container-title":["International Journal of Web Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.emeraldinsight.com\/doi\/full-xml\/10.1108\/17440080810865611","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440080810865611\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440080810865611\/full\/html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T00:24:55Z","timestamp":1753403095000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.emerald.com\/ijwis\/article\/4\/1\/6-47\/163875"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,4]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,4,4]]}},"alternative-id":["10.1108\/17440080810865611"],"URL":"https:\/\/doi.org\/10.1108\/17440080810865611","relation":{},"ISSN":["1744-0084"],"issn-type":[{"type":"print","value":"1744-0084"}],"subject":[],"published":{"date-parts":[[2008,4,4]]}}}