Processamento de consultas baseadas em palavras-chave sobre fluxos XML

Abstract

XML streams have become a relevant research topic due to the widespread use of appli-cations such as online news, RSS feeds, and dissemination systems. Such streams must be processed rapidly and without retention. Retaining streams could cause data loss due to the large data traffic in continuous processing. This context becomes more com-plex when thousands of queries must be evaluated simultaneously. Different approaches explore simultaneous multiple query processing. However, they are based on structured languages such as XPath and XQuery, which require knowledge of their syntax and the data structure to formulate queries. Keyword-based language is a usual approach tosubmit queries informally, because they require minimal or no schema knowledge to formulate queries. Some approaches focus on improving search performance, but only in archived XML documents. More recent techniques have focused on keyword-based search algorithms for XML streams, but they only run one query at a time. Most of the keyword-based algorithms consider the lowest common ancestor (LCA) semantics. Themost popular LCA-based algorithms use the smallest LCA (SLCA) and the exclusive LCA (ELCA) semantics. Particularly, ELCA handles the ambiguity that might exist in an XML document since the same content can occur at different levels, such as key-words that correspond to XML labels occurring in different schema elements. Thus, ELCA is considered one of the most effective semantics because it returns a larger number of results. However, previous approaches do not support the major challenges in the new stream application scenarios. These challenges involve (i) the efficient pro-cessing of thousands of user queries over XML streams and (ii) the relief of users from knowing the source schemas when accessing ambiguous or heterogeneous data sources. To address these challenges, in this thesis, we propose new algorithms for processing multiple keyword queries over XML streams. The algorithms explore stream process-ing properties based on the LCA semantics and provide optimized methods to improve the overall performance. In addition, we propose strategies for ranking query results over XML streams. A comprehensive set of experiments thoroughly evaluates several aspects related to performance, scalability and accuracy of our algorithms, showing that our algorithms are efficient alternatives to search services over XML streams.