摘要：Satisfiability is an important problem of queries for XML documents. This paper focuses on
the satisfiability of tree pattern queries for Active XML(AXML for short) documents conforming to a
given AXML schema. An AXML document is an XML document where some data is given explicitly
and other parts are defined intensionally by means of embedded calls to Web services, which can be
invoked to generate data. For the efficient evaluation of a query over an AXML document, one should
check whether there exists an (A)XML document obtained from the original one by invoking some Web
services, on which the query has a non-empty answer. An algorithm for checking satisfiability of tree
pattern queries for AXML documents that runs polynomial time is proposed based on tree automata
theory. Then experiments were made to verify the utility of satisfiability checking as a preprocessing
step in queries procession. Our results show that the check takes a negligible fraction of the time needed
for processing the query while often yielding substantial savings.
关键词：Active XML, tree pattern queries, tree automata, satisfiability.
