The proliferation of extensible markup language XML in the last decade has triggered an enormous amount of academic research and the development of commercial software tools for semi-structured data management. The use of XML as a data model has enhanced the representation of data and its extensibility, and the availability of  query languages such as XQuery and XPath has enhanced the expressiveness of user interests. XML documents are typically modeled as ordered labeled trees, and queries use twig patterns to denote the set of nodes to match in the documents. Finding twig pattern matches is a fundamental operation over XML data.

In this talk, I will introduce a novel sequencing paradigm for twig pattern matching by transforming XML data and twig patterns into sequences based on Prüfer's method. Two systems based on this sequencing paradigm will be presented, namely, PRIX and FiST. PRIX is an XML indexing and querying system that efficiently finds all occurrences of a given twig query in the database. FiST is a scalable XML document filtering system that enables selective dissemination of information (SDI) by finding those twig patterns that appear in an incoming document. I will describe the design of these two systems, and present our experimental results.

Biography:

Praveen Rao is currently a PhD student in Computer Science at the University of Arizona. He works in the area of database systems under the supervision of Prof. Bongki Moon.