Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/60723

Download PDF (Accepted manuscript) (Adobe Acrobat PDF, -1 bytes)

Title

Containment between unions of XPath queries

Author(s)

Zhou, Rui;  Liu, Chengfei;  Wang, Junhu;  Li, Jianxin

Abstract

In this paper, we address the containment problem for unions of XPath queries with and without schema. We find the problem can be always reduced into containment problem between one single query and a union of queries. When schema is not available, the problem can be further reduced into checking containment between pairwise queries(each from one union), but this only holds for some XPath subsets, such as XP{/,//,[]}, but not for XP{/,//,[],∗}. We then show the problem is still solvable in XP{/,//,[],∗}, though no efficient algorithm exists. When schema is at hand, we propose a strategy to rewrite a query into a union of simplified queries based on schema information, and then apply methods developed when schema is not taken into account. The problem is then reduced into checking containment between unions of queries in XP{/,[]}without schema.

Publication type

Conference paper

Research centre

Swinburne University of Technology.

Source

Lecture notes in computer science: proceedings of the 14th International Conference on Database Systems for Advanced Applications (DASFAA 2009), Brisbane, Queensland, Australia, 21-23 April 2009 / Xiaofang Zhou, Haruo Yokota, Ke Deng, Qing Liu (eds.), Vol. 5463, pp. 405-420

Publication year

2009

FOR Code(s)

080404 Markup Languages;  080505 Web Technologies (excl. Web Search);  080604 Database Management

Keyword(s)

Algorithms;  Boolean tree patterns;  Query containment;  Schema;  Wildcards;  XPath queries

Publisher

Springer

ISSN

0302-9743 (series ISSN)

ISBN

9783642008863, 3642008860

Publisher URL

http://dx.doi.org/10.1007/978-3-642-00887-0_36

Copyright

Copyright © Springer-Verlag Berlin Heidelberg 2009. The accepted manuscript is reproduced in accordance with the copyright policy of the publisher. The definitive version of the publication is available at www.springer.com.

Full text

Peer reviewed