A Sequencing Paradigm for XML Twig Pattern Matching

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 Prufer's method. 
The design of the PRIX system based on this sequencing paradigm will be presented. 
PRIX is an XML indexing and query processing system that finds all occurrences of 
a given twig query in an XML database. I will briefly talk about our FiST system that 
is also based on our sequencing paradigm. 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.

Finally, I will briefly discuss my ongoing research work on locating and disseminating 
XML data in peer-to-peer systems.