Evaluating Universal Quantification in XML

Queries posed to database systems often involve Universal Quantification. Such queries are typically expensive to evaluate. Although they can be handled by basic access methods, for selection, grouping, and so forth, new access methods specifically tailored to evaluate universal quantification can greatly decrease the computational cost. This paper studies the efficient evaluation of universal quantification in an XML database. Specifically, a small taxonomy of universal quantification types is developed and a family of algorithms is defined suitable for handling each.