A Rewrite Approach for Pattern Containment

Kordy, Barbara

Request a copy

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

A Rewrite Approach for Pattern Containment

Kordy, Barbara

2009 • In 19th International Workshop on Algebraic Development Techniques, WADT 2008

Peer reviewed

Permalink
https://hdl.handle.net/10993/25969

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

A Rewrite Approach for Pattern Containment.pdf

Author postprint (397.33 kB)

Request a copy

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Abstract :

[en] In this paper, we introduce an approach that allows us to handle the containment problem for the fragment XP(/,//,[ ],*) of XPath. Using rewriting techniques we define a necessary and sufficient condition for pattern containment. This rewrite view is then adapted to query evaluation on XML documents, and remains valid even if the documents are given in a compressed form, as dags.

Disciplines :

Computer science

Identifiers :

UNILU:UL-CONFERENCE-2010-034

Author, co-author :

Kordy, Barbara ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

External co-authors :

Language :

English

Title :

A Rewrite Approach for Pattern Containment

Publication date :

2009

Event name :

19th International Workshop on Algebraic Development Techniques, WADT 2008

Event place :

Pisa, Italy

Event date :

June 13-16, 2008

Audience :

International

Main work title :

19th International Workshop on Algebraic Development Techniques, WADT 2008

Publisher :

Springer

ISBN/EAN :

978-3-642-03428-2

Pages :

236-250

Peer reviewed :

Peer reviewed

Additional URL :

http://satoss.uni.lu/members/barbara/papers/KordyWadt08.pdf

Commentary :

volume 5486 of LNCS Recent Trends in Algebraic Development Techniques

Available on ORBilu :

since 17 March 2016

Statistics

Number of views

49 (0 by Unilu)

Number of downloads

0 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

WoS citations^™

Bibliography

Miklau, G., Suciu, D.: Containment and Equivalence for a Fragment of XPath. J. ACM 51(1), 2-45 (2004)
Neven, F., Schwentick, T.: XPath Containment in the Presence of Disjunction, DTDs, and Variables. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 312-326. Springer, Heidelberg (2002)
W3C: XML Path Language (1999), http://www.w3.org/TR/xpath
Wood, P.T.: On the Equivalence of XML Patterns. In: Palamidessi, C., Moniz Pereira, L., Lloyd, J.W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Sagiv, Y., Stuckey, P.J. (eds.) CL 2000. LNCS, vol. 1861, pp. 1152-1166. Springer, Heidelberg (2000)
Schwentick, T.: XPath Query Containment. SIGMOD Rec. 33(1), 101-109 (2004)
Gottlob, G., Koch, C., Pichler, R.: Efficient Algorithms for Processing XPath Queries. ACM Trans. Database Syst. 30(2), 444-491 (2005)
Flesca, S., Furfaro, F., Masciari, E.: On the Minimization of XPath Queries. J. ACM 55(1) (2008)
Amer-Yahia, S., Cho, S., Lakshmanan, L.V.S., Srivastava, D.: Tree Pattern Query Minimization. VLDB J. 11(4), 315-331 (2002)
Kimelfeld, B., Sagiv, Y.: Revisiting Redundancy and Minimization in an XPath Fragment. In: EDBT 2008: Proceedings of the 11th International Conference on Extending Database Technology, pp. 61-72. ACM, New York (2008)
Ramanan, P.: Efficient Algorithms for Minimizing Tree Pattern Queries. In: SIGMOD 2002: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 299-309. ACM, New York (2002)
Fila, B., Anantharaman, S.: Automata for Positive Core XPath Queries on Compressed Documents. In: Hermann, M., Voronkov, A. (eds.) LPAR 2006. LNCS (LNAI), vol. 4246, pp. 467-481. Springer, Heidelberg (2006)
Buneman, P., Grohe, M., Koch, C.: Path Queries on Compressed XML. In: VLDB 2003, pp. 141-152. Morgan Kaufmann, San Francisco (2003)
Marx, M.: XPath and Modal Logics of Finite DAG's. In: Cialdea Mayer, M., Pirri, F. (eds.) TABLEAUX 2003. LNCS (LNAI), vol. 2796, pp. 150-164. Springer, Heidelberg (2003)
Frick, M., Grohe, M., Koch, C.: Query Evaluation on Compressed Trees (Extended Abstract). In: LICS 2003: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, p. 188. IEEE Computer Society, Washington (2003)
Busatto, G., Lohrey, M., Maneth, S.: Efficient Memory Representation of XML Document Trees. Inf. Syst. 33(4-5), 456-474 (2008)
Niehren, J., Planque, L., Talbot, J.M., Tison, S.: N-ary Queries by Tree Automata. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 217-231. Springer, Heidelberg (2005)