Abstract
Abstract As the increasing need for streaming applications, management of these unbounded and unpredicted data becomes an urgent issue. Many Data Stream Management Systems (DSMSs) are proposed to accommodate to different streaming environments and data types. One kind of these DSMSs focuses on the XML data type. XML is widely used in many kinds of applications such as information exchange and web services. Therefore, it is an important problem to efficiently process XML queries over data streams. Among various optimization techniques of query processing, selectivity estimation is important in the traditional database researches. In the streaming environment, to determine the selectivity of some condition clauses is also important for query optimization, especially the case of join operation. In the XML streams, the estimation of path selectivity is more complex and difficult. Therefore, a novel selectivity estimation approach based on data summarization is proposed for XML path expressions over streaming data. This approach is combined with both path tree approach and Markov-based approach. The newly arrived data are processed and recorded in the summary tree, and the unimportant data are archived in a preference matrix. Based on the summary structures, the selectivity of the query paths can be efficiently estimated. We also propose a prototype of query relaxation system for XML path queries, which is based on the proposed selectivity estimation method. This system is used to automatically relax the user query such that the number of query results will reach the user requirement. In the experiment results, we show that the selectivity of various path queries can be efficiently estimated from different kinds of data. The performance under different memory limits and the node deletion policies are also discussed. Keywords: XML, XPath, Stream data, selectivity estimation, summarization