On Testing Satisfiability of Tree Pattern Queries

Laks V.S. Lakshmanan, Ganesh Ramesh, Hui(wendy) Wang, Zheng(Jessica) J. Zhao

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

48 Scopus citations

Abstract

This chapter presents a systematic analysis of satisfiability of tree pattern queries that capture a useful fragment of XPath together with additional constraints, with or without a schema. XPath and XQuery are the two major query languages for XML. An important issue arising in an efficient evaluation of queries expressed in these languages is satisfiability. The satisfiability check can affect substantial savings in query evaluation. The chapter also investigates cases in which the problem can be solved in polynomial time and develops novel efficient algorithms for this purpose. In several cases, the problem is NP-complete. A comprehensive set of investigations to verify the utility of satisfiability check as a preprocessing step in query processing were carried out. The results show that this check takes a negligible fraction of the time needed for processing the query while often yielding substantial savings.

Original languageEnglish
Title of host publicationProceedings 2004 VLDB Conference
Subtitle of host publicationThe 30th International Conference on Very Large Databases (VLDB)
Pages120-131
Number of pages12
ISBN (Electronic)9780120884698
DOIs
StatePublished - 1 Jan 2004

Fingerprint

Dive into the research topics of 'On Testing Satisfiability of Tree Pattern Queries'. Together they form a unique fingerprint.

Cite this