TY - CHAP
T1 - On Testing Satisfiability of Tree Pattern Queries
AU - Lakshmanan, Laks V.S.
AU - Ramesh, Ganesh
AU - Wang, Hui(wendy)
AU - Zhao, Zheng(Jessica) J.
N1 - Publisher Copyright:
© 2004 Elsevier Inc. All rights reserved.
PY - 2004/1/1
Y1 - 2004/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=34948903143&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34948903143&partnerID=8YFLogxK
U2 - 10.1016/B978-012088469-8.50014-0
DO - 10.1016/B978-012088469-8.50014-0
M3 - Chapter
AN - SCOPUS:34948903143
SP - 120
EP - 131
BT - Proceedings 2004 VLDB Conference
ER -