An Efficient XML Search Engine Supporting Approximate Search

In this thesis we discuss the design and the realization of a novel XML search engine (XMLSE), which merge the exact-match search and the approximate match search paradigms. Our research focuses on developing innovative techniques, in terms of indexing structures and query processing methods, to efficiently and effectively support, beyond the exact-match search, the structure search and the similarity access also when huge XML data repositories are involved. This includes the construction of access methods especially conceived for XML, the development of efficient algorithms for the evaluation of queries and the extension of the standard query language XQuery. As for traditional databases, we have realized indexes that are efficient, i.e. the time needed to process a query as short as possible, and complete, i.e. all the objects satisfying the query appear in the result set. Most important, we have conceived a scalable search engine suitable to important multimedia applications. The essential steps of this research activity are: study and realization of special indexes for efficient XML query execution; extension of the XQuery syntax to support the approximate search; realization of a specific query processor for the new indexes; study and realization some query optimization techniques.