In this paper, we present a novel and complementary technique to optimize XML twig pattern queries with wildcards(*). Our approach is based on utilizing a new axis called AD-dis, to equivalently rewrite a query with wildcards (non-branching as well as branching wildcards) into a single query without any wildcards. We present efficient rewriting algorithms and also twig pattern matching algorithms to process the rewritten queries with AD-dis, which is proven to be I/O and CPU optimal. In addition, the experimental results not only verify the scalability and efficiency of our extended matching algorithms, but also demonstrate the effectiveness of our rewriting algorithms.
展开▼
