III: Small: From Regular Expressions to Nested Words in Complex Event and Semistructured Information Processing

对于在存储序列和数据流中发现复杂模式的更强大和高效的查询语言的需求被广泛的应用所共享，包括软件分析、复杂事件处理、RNA结构识别、时态数据库和XML查询。这个项目的目标是开发一个统一的框架，以支持非常强大的模式语言及其针对不同应用领域的查询优化技术。为了实现这一目标，该项目遵循以下方法：(I)嵌套Kleene闭包(K*)构造以获得更高级别的查询语言的表达能力，以及(Ii)嵌套单词和明显的下推自动机作为其在不同应用领域的统一实现和查询优化的基础。这种基于K*的方法以前被成功地应用于关系序列，现在被推广到不同的计算环境和应用领域。通过统一的框架，该项目设计并演示了在表达能力和性能方面与现有语言相媲美的XML和时态查询语言。然后演示了统一框架在新的应用领域中的使用。特别是，它为RNA结构和软件分析开发了高效的查询语言。这些研究成果将对软件分析、基因组数据库、复杂事件处理、数字政府和科学研究等应用产生重大影响。该项目支持博士生在高级查询语言和数据流管理系统领域进行研究。课程中引入了一门涵盖这些领域的新研究生课程，并将该项目的研究成果纳入课程。这项研究的出版物、技术报告、软件和实验数据可通过该项目的网站获得：http://yellowstone.cs.ucla.edu/nsf-projects/RegExpr2NestedWords.html.

The need for more powerful and efficient query languages to find complex patterns in stored sequences and data streams is shared by a wide spectrum of applications, including software analysis, complex event processing, identification of RNA structures, temporal databases and XML queries. The goal of this project is to develop a unified framework to support very powerful pattern languages and their query optimization techniques for different application domains. To achieve this goal, the project follows the approach of using (i) nested Kleene-closure (K*) constructs to achieve greater levels of expressive power for the query languages, and (ii) Nested Words and Visibly Pushdown Automata as the basis for their unified implementation and query optimization over different application domains. This K*-based approach was previously applied successfully to relational sequences and are now generalized to different computing environments and application domains. Through the unified framework, the project designs and demonstrates XML and temporal query languages that compare favorably in terms of expressive power and performance with existing ones. It then demonstrates the use of the unified framework in new application areas. In particular, it develops efficient query languages for RNA structures and software analysis. These research results will have great impacts on many applications, such as software analysis, genomic databases, complex event processing, digital government and scientific studies. This project supports Ph.D. students to pursue research in the areas of advanced query languages and data stream management systems. A new graduate-level course covering these areas and integrating the research results from the project are introduced into the curriculum. Publications, technical reports, software and experimental data from this research are available via the project web site at: http://yellowstone.cs.ucla.edu/nsf-projects/RegExpr2NestedWords.html.