SGER: PQL: A Path Query Language

该方案通过设计、开发和评估面向图形的数据的通用查询语言，将现有的研究扩展到广泛的应用领域。路径查询语言PQL被设计用于解决在表达对起源或谱系数据的查询时遇到的挑战，但它被认为是操作任何类型的面向图形的数据的通用数据模型和查询语言的基础。面向图的数据产生于许多学科，包括计算机网络、信息检索、生物学、网络搜索、社交网络、谱系学等。将所有这些领域结合在一起的一个特征是需要通过图来表达路径上的查询。今天大多数现有的解决方案要么是微弱的路径概念，要么是不存在的路径概念，这些路径是可以命名、比较、操纵和构建的第一类实体。PQL解决了这一问题。PQL源于半结构化数据库语言Lorel，它对半结构化数据进行操作，这些数据可以被视为链接在一起的对象的集合。在PQL中，这些链接是单向的，尽管我们支持跨这些链接的向前和向后查询。查询通过选择和过滤图中的一条或多条路径来表示，其中路径可以用正则表达式来描述。因此，在起源域中，人们可以谈论“在调用编译器和生成可执行文件之间的图中的所有路径。”在生物学中，人们可能会提出这样一个问题：“从基因表达的特定组合到最终产生胰岛素的所有路径。”这项建议中描述的工作扩展了PQL，包括更新的语法和语义，以及产生查询结果的能力，这些查询结果是由原始组件构造的图形。这项工作的结果将以机器可检查的语言形式规范和开放源码的PQL实现来获取，并包括(可替换的)后端实现。有关该项目的更多信息可以在项目网页上找到：http://www.eecs.harvard.edu/~syrah/pass/

This proposal extends current research in creating a query languagefor provenance to a broad range of application domains by designing,developing, and evaluating a general-purpose query language forgraph-oriented data.PQL, the path query language, was designed to address the challengesencountered in expressing queries on provenance or lineage data,but it was conceived to be the foundation for a general purposedata model and query language for manipulating any type ofgraph-oriented data. Graph-oriented data arises in many disciplinesincluding computer networking, information retrieval, biology, websearch, social networking, genealogy, etc. A characteristic thatunites all these domains is that need for expressing queries onpaths through a graph. Most existing solutions today have eithera weak or non-existent notion of paths as first-class entities thatcan be named, compared, manipulated and constructed. PQL addressesthis problem.Derived from the semi-structured database language, Lorel, PQLoperates on semi-structured data, which can be viewed as a collectionof objects linked together. In PQL, these links are unidirectional,although we support both forward and backward queries across theselinks. Queries are expressed by selecting and filtering one ormore paths in the graph, where paths can be described by regularexpressions. Thus, in the provenance domain, one can talk about,''all paths in the graph between invocations of a compiler and theresulting executables.'' In biology, one might pose a query about,''all paths from a particular combination of gene expressions toresulting insulin production.''The work described in this proposal extends PQL to include updatesyntax and semantics and the ability to produce query results thatare graphs constructed from components of the original. The resultof this work will be captured in both a machine-checkable formalspecification of the language and an open source PQL implementation,complete with a (replaceable) back-end implementation.Further information on the project can be found at the project web page:http://www.eecs.harvard.edu/~syrah/pass/