Considerable effort has been devoted to minimizing XPath queries under the assumption that the minimal query is faster than the original query. However, little attention has been paid to the validity of the assumption. In this paper, we provide a detailed analysis on the effectiveness of XPath query minimization and present an extensive experimental evaluation on the effectiveness using six publicly available XQuery engines. To the best of our knowledge, this is the first work done towards this objective. Experiments on real and synthetic data sets show that although the assumption is valid for some cases, the performance of the minimal query is often lower than or almost equal to that of the original query.

XQuery has become the standard for querying XML. Just like SQL, XQuery allows nested expressions. To optimize XQuery processing, a lot of research has been done on normalization, i.e., transforming nested expressions to equivalent unnested ones. Previous normalization rules are classified into two categories—source-level/ and algebra-level/—depending on whether a construct is specified in the XQuery syntax or as equivalent algebraic expressions. From an implementation point of view, the former is preferable to the latter since it can be implemented in a variety of XQuery engines with different algebras. However, existing source-level rules have several problems: They do not handle quantified expressions, incur duplicated query results, and use many temporary files. In this paper, we propose new source-level normalization rules that solve these problems. Through analysis and experiments, we show that our normalization rules can reduce query execution time from hours to a few seconds and can be adapted to a variety of XQuery engines.

A data stream is a series of massive unbounded tuples continuously generated at a rapid rate. Continuous queries for data streams should be processed continuously, so that a strict time constraint is required. In most previous research studies, in order to guarantee this constraint, the evaluation order of join predicates in a continuous query is optimized using a greedy strategy. However, because a greedy strategy traces only the first promising plan, it often finds a suboptimal plan. To reduce the possibility of producing a suboptimal plan, in this paper, we propose an improved scheme, k-Extended Greedy Algorithm (k-EGA), that simultaneously examines a set of promising plans and reoptimize an execution plan adaptively. The number of promising plans is flexibly controlled by a user-defined range variable. The scheme verifies the performance of the current plan periodically. If the plan is no longer efficient, a newly optimized plan is generated. The performance of the proposed scheme is verified through various experiments to identify its various characteristics.

This paper discusses the relationships of two important program classes of linearly recursive programs, that is, decomposable programs and rule commutative programs. We prove that the decomposable programs are always rule commutative. Furthermore, the rule commutative programs that satisfy certain conditions are decomposable. These results are meaningful for integrating the related specified optimization algorithms.