TY - GEN
T1 - Containment of partially specified tree-pattern queries
AU - Theodoratos, Dimitri
AU - Dalamagas, Theodore
AU - Placek, Pawel
AU - Souldatos, Stefanos
AU - Sellis, Timos
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2006
Y1 - 2006
N2 - Nowadays, huge volumes of data, including scientific data, are organized or exported in tree-structured form. Querying capabilities are provided through tree-pattern queries. The need for integrating multiple data sources with different tree structures has driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In this paper we adopt a query language with partially specified tree-pattern queries. A central feature of this type of queries is that the structure can be specified fully, partially, or not at all in a query. Important issues in query optimization require solving the query containment problem. We study the containment problem for partially specified tree-pattern queries. To support the evaluation of such queries, we use semantically rich constructs, called dimension graphs, which abstract structural information of the tree-structured data. We address the problem of query containment in the absence (absolute query containment) and in the presence (relative query containment) of dimension graphs, and we provide necessary and sufficient conditions for each type of query containment. We suggest a technique for relative query containment checking based on structural information extracted in advance from the dimension graph. Our approach is implemented and validated through extensive experimental evaluation.
AB - Nowadays, huge volumes of data, including scientific data, are organized or exported in tree-structured form. Querying capabilities are provided through tree-pattern queries. The need for integrating multiple data sources with different tree structures has driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In this paper we adopt a query language with partially specified tree-pattern queries. A central feature of this type of queries is that the structure can be specified fully, partially, or not at all in a query. Important issues in query optimization require solving the query containment problem. We study the containment problem for partially specified tree-pattern queries. To support the evaluation of such queries, we use semantically rich constructs, called dimension graphs, which abstract structural information of the tree-structured data. We address the problem of query containment in the absence (absolute query containment) and in the presence (relative query containment) of dimension graphs, and we provide necessary and sufficient conditions for each type of query containment. We suggest a technique for relative query containment checking based on structural information extracted in advance from the dimension graph. Our approach is implemented and validated through extensive experimental evaluation.
UR - http://www.scopus.com/inward/record.url?scp=45149093240&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=45149093240&partnerID=8YFLogxK
U2 - 10.1109/SSDBM.2006.16
DO - 10.1109/SSDBM.2006.16
M3 - Conference contribution
AN - SCOPUS:45149093240
SN - 0769525903
SN - 9780769525907
T3 - Proceedings of the International Conference on Scientific and Statistical Database Management, SSDBM
SP - 3
EP - 12
BT - Proceedings - 18th International Conference on Scientific and Statistical Database Management, SSDBM 2006
T2 - 18th International Conference on Scientific and Statistical Database Management, SSDBM 2006
Y2 - 3 July 2006 through 5 July 2006
ER -