Querying Graphs with Data
Querying Graphs with Data
复制标题
DOI：
10.1145/2850413
复制
发表时间：
2016-05-01
影响因子：
2.5
通讯作者：
Vrgoc, Domagoj
中科院分区：
文献类型：
--
作者：
Libkin, Leonid;Martens, Wim;Vrgoc, Domagoj
图数据库最近受到了很多关注，这是因为在许多应用中，数据被自然地视为图;这些应用包括社交网络、RDF和语义Web、生物数据库以及许多其他应用。有许多关于图数据库的查询语言的建议，主要分为两类。一种是将图视为一种特殊的关系数据，并使用传统的关系机制进行查询。另一个集中在查询图的拓扑结构。然而，这些方法缺乏将数据和拓扑结构相结合的能力，这将允许查询询问数据如何沿着包围它的路径和模式变化。在这篇文章中，我们提出了一个全面的研究语言，使这种数据和拓扑结构的组合查询。这些语言有两种类型。第一个遵循路径查询的标准方法，指定边的标签如何沿路径沿着变化，但现在我们扩展它们，指定标签和数据如何变化。从复杂性的角度来看，正确的形式主义类型是寄存器自动机的子类。然而，这些并不适合查询。为了克服这一点，我们开发了几种类型的扩展正则表达式来指定数据路径，并研究它们的查询能力和复杂性。第二种方法采用流行的XML语言XML，并将其从XML文档扩展到图形。根据允许的功能的确切集合，我们有一个语言家族，我们的研究表明，它包括高效和高度表达的形式主义查询数据的结构和数据本身。
Graph databases have received much attention as of late due to numerous applications in which data is naturally viewed as a graph; these include social networks, RDF and the Semantic Web, biological databases, and many others. There are many proposals for query languages for graph databases that mainly fall into two categories. One views graphs as a particular kind of relational data and uses traditional relational mechanisms for querying. The other concentrates on querying the topology of the graph. These approaches, however, lack the ability to combine data and topology, which would allow queries asking how data changes along paths and patterns enveloping it.In this article, we present a comprehensive study of languages that enable such combination of data and topology querying. These languages come in two flavors. The first follows the standard approach of path queries, which specify how labels of edges change along a path, but now we extend them with ways of specifying how both labels and data change. From the complexity point of view, the right type of formalisms are subclasses of register automata. These, however, are not well suited for querying. To overcome this, we develop several types of extended regular expressions to specify paths with data and study their querying power and complexity. The second approach adopts the popular XML language XPath and extends it from XML documents to graphs. Depending on the exact set of allowed features, we have a family of languages, and our study shows that it includes efficient and highly expressive formalisms for querying both the structure of the data and the data itself.