SGER: PQL: A Path Query Language

该方案通过设计、开发和评估面向图数据的通用查询语言PQL，将当前创建起源查询语言的研究扩展到广泛的应用领域。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/