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/