|
 ABSTRACT
XPath is a simple language for navigating an XML document and selecting a set of element nodes. XPath expressions are used to query XML data, describe key constraints, express transformations, and reference elements in remote documents. This paper studies the containment and equivalence problems for a fragment of the XPath query language, with applications in all these contexts.In particular, we study a class of XPath queries that contain branching, label wildcards and can express descendant relationships between nodes. Prior work has shown that languages which combine any two of these three features have efficient containment algorithms. However, we show that for the combination of features, containment is coNP-complete. We provide a sound and complete EXPTIME algorithm for containment, and study parameterized PTIME special cases. While we identify two parameterized classes of queries for which containment can be decided efficiently, we also show that even with some bounded parameters, containment is coNP-complete. In response to these negative results, we describe a sound algorithm which is efficient for all queries, but may return false negatives in some cases.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
|
| |
2
|
P. Buneman, S. Davidson, W. Fan, C. Hara, and W. Tan. Reasoning about keys for xml, 2000.
|
| |
3
|
D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. View-based query answering and query containment over semistructured data. Submitted for publication, 2001.
|
| |
4
|
D. Chamberlin, J. Clark, D. Florescu, J. Robie, J. Simeon, and M. Stefanascu. XQuery 1.0: An XML query language. http://www.w3.org/TR/xquery/, 07 June 2001. W3C working draft.
|
| |
5
|
|
| |
6
|
|
| |
7
|
Richard Cole , Ramesh Hariharan , Piotr Indyk, Tree pattern matching and subset matching in deterministic O(n log3 n)-time, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.245-254, January 17-19, 1999, Baltimore, Maryland, United States
|
| |
8
|
S. DeRose, R. D. Jr., and E. Maler. XML pointer language (XPointer) working draft. http://www.w3.org/TR/1999/WD-xptr-19991206, December 1999.
|
| |
9
|
S. DeRose, E. Maler, and D. Orchard. Xml linking language (Xlink). http://www.w3.org/TR/2000/REC-xlink-20010627, June 2001.
|
| |
10
|
A. Deutsch and V. Tannen. Containment and Integrity Constraints for XPath Fragments. In KRDB 2001, 2001.
|
| |
11
|
Daniela Florescu , Alon Levy , Dan Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 01-04, 1998, Seattle, Washington, United States
[doi> 10.1145/275487.275503]
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
Kosaraju. Efficient tree pattern matching. In FOCS: IEEE Symposium on Foundations of Computer Science (FOCS), 1989.
|
| |
16
|
G. Miklau and D. Suciu. Containment and equivalence of tree patterns. University of Washington Technical Report (TR 02-02-03), February 2002. http://www.cs.washington.edu/homes/gerome.
|
| |
17
|
|
| |
18
|
H. Seidl. Personal communication, August 2001.
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
| |
22
|
M. Vardi. Why is modal logic so robustly decidable, 1997.
|
| |
23
|
|
| |
24
|
|
| |
25
|
P. T. Wood. Minimizing simple xpath expressions. Fourth International Workshop on the Web and Databases (WebDB'2001), 2001.
|
| |
26
|
XML Schema part 1: Structures. http://www.w3.org/TR/1999/WD-xmlschema-1-19991217/, 17 December 1999. W3C Working Draft.
|
| |
27
|
M. Yannakakis. Algorithms for acyclic database schemes. In Proceedings of the 7th Conference on Very Large Databases, Morgan Kaufman pubs. (Los Altos CA), Zaniolo and Detobel(eds), 1981.
|
CITED BY 69
|
|
|
|
|
|
|
|
Serge Abiteboul , Omar Benjelloun , Bogdan Cautis , Ioana Manolescu , Tova Milo , Nicoleta Preda, Lazy query evaluation for Active XML, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Bo Luo , Dongwon Lee , Wang-Chien Lee , Peng Liu, QFilter: fine-grained run-time XML access control via NFA-based query rewriting, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
|
|
|
|
|
|
|
|
|
|
|
|
Liang Huai Yang , Mong Li Lee , Wynne Hsu , Xinyu Guo, 2PXMiner: an efficient two pass mining of frequent XML query patterns, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Luc Bouganim , Cosmin Cremarenco , François Dang Ngoc , Nicolas Dieu , Philippe Pucheral, Safe data sharing and data dissemination on smart devices, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nicola Onose , Alin Deutsch , Yannis Papakonstantinou , Emiran Curtmola, Rewriting nested XML queries using nested views, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
|
|
|
Dimitri Theodoratos , Stefanos Souldatos , Theodore Dalamagas , Pawel Placek , Timos Sellis, Heuristic containment check of partial tree-pattern queries in the presence of index graphs, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Laks V. S. Lakshmanan , Ganesh Ramesh , Hui Wang , Zheng Zhao, On testing satisfiability of tree pattern queries, Proceedings of the Thirtieth international conference on Very large data bases, p.120-131, August 31-September 03, 2004, Toronto, Canada
|
|
|
Zhimin Chen , H. V. Jagadish , Laks V. S. Lakshmanan , Stelios Paparizos, From tree patterns to generalized tree patterns: on efficient evaluation of XQuery, Proceedings of the 29th international conference on Very large data bases, p.237-248, September 09-12, 2003, Berlin, Germany
|
|
|
|
|
|
|
|
|
|
|
|
Andrey Balmin , Fatma Özcan , Kevin S. Beyer , Roberta J. Cochrane , Hamid Pirahesh, A framework for using materialized XPath views in XML query processing, Proceedings of the Thirtieth international conference on Very large data bases, p.60-71, August 31-September 03, 2004, Toronto, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Liang Huai Yang , Mong Li Lee , Wynne Hsu , Decai Huang , Limsoon Wong, Efficient mining of frequent XML query patterns with repeating-siblings, Information and Software Technology, v.50 n.5, p.375-389, April, 2008
|
|
|
Jianhua Feng , Na Ta , Guoliang Li , Yu Liu , Dapeng Lv, A framework of semantic cache for secure XML query answering: an interesting joint and novel perspective, Proceedings of the 2nd international conference on Scalable information systems, June 06-08, 2007, Suzhou, China
|
|
|
Marcos Antonio Vaz Salles , Jens-Peter Dittrich , Shant Kirakos Karakashian , Olivier René Girard , Lukas Blunschi, iTrails: pay-as-you-go information integration in dataspaces, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
|
|
|
|
|
|
Pawel Placek , Dimitri Theodoratos , Stefanos Souldatos , Theodore Dalamagas , Timos Sellis, A heuristic approach for checking containment of generalized tree-pattern queries, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
I.7