Planning and Factorization for Graph Database Query Optimization and Evaluation

只要人们一直在看星星，文化就会描绘出连接它们的线。一些相互关联的恒星群如此突出，人们将意义赋予这些星座，将它们与其世界内的事物联系起来。这并不令人意外。这种模拟世界的方式是相当自然的。我们绘制出我们世界中的事物是如何联系在一起的，它们之间的“概念线”。我们在脑海中行走我们构建的这些概念图，以回答关于我们世界的问题，并从我们的地图中概括和提取知识。这也是一个用于捕获计算机信息的有用模型，也就是我们所说的数据库。这些东西，实体，就是我们想要存储的信息。我们可以在相关的实体(事物)之间放置边，用它们是如何相关的来标记它们。所以我们的数据库是一个很大的图表。然后用正确的语言提出问题，查询，我们可以在需要的时候从图表中提取有用的信息。也就是说，计算机遍历图表以查找查询的信息。假设我们构建了一个用于接触跟踪的图形数据库。人是实体。当两个人亲密接触时，我们在两个人之间的图表中放入一条标记的边。注两个People实体之间可能有很多边，每次它们靠近时都有一条边。每条边都可以标上他们所做的时间。这样的图形数据库可以用于接触者追踪：每当有人生病时，我们可以查询图形来发现他们在一段时间内与谁接触过。图形数据库对于以自然的方式收集数据非常有用。我们开始看到组织建立极大的图形数据库。例如，截至最近，UniProt SPARQL端点(数据集)由63,376,853,475条边组成。UniProt(通用蛋白质资源)是生物学家使用的免费访问的、受欢迎的蛋白质数据存储库。但是，这样的图形数据库只有在我们可以使用它们来获取有用信息的情况下才有用。由于图形数据库可能非常大，因此对它们的查询可能很难回答，也很难有效地进行评估。如果您必须等待多年才能得到答案，那么查询就没有用处了！图形数据库是一项相当新的技术。因此，我们正处于学习如何有效使用和使用它们的开始阶段。这包括如何有效地评估针对它们的查询。其他类型的数据库存在的时间要长得多；我们对如何使用它们有更深刻的经验。在这项工作中，我们采用了查询优化的方法来更有效地对图数据库进行查询评估。图形数据库的合取查询(一个有用的类)本身就是小图形。我们也将查询的答案建模为一个图，一个答案图。这是一种因子化技术，对于图形数据看起来很有前途。因此，让图形数据库真正有用。

As long as people have looked at the stars, cultures have imaged lines connecting them. Some groups of so connected stars so stood out, people ascribed meaning to these constellations, relating them to things within their world. This is not so surprising. This way of modelling the world comes rather naturally. We map out how things in our world are related, the "conceptual lines" between them. We mentally walk these conceptual graphs we have constructed to answer questions about our world, and to generalize, to extract knowledge from our map. This is a useful model to use to capture information for computers, too, what we call a database. The things, entities, are whatever we are wanting to store information about. And we can put edges between entities (things) that are related, labelled with how they are related. So our database is a large graph. Then with the right language to ask questions, queries, we can extract useful information from the graph when needed. That is the computer walking the graph to find the queried information. Imagine we build a graph database for contact tracing. People are the entities. And we put a labelled edge into the graph between two people whenever the two come into close physical contact. Note two people entities might have lots of edges between them, one for each time they came in close proximity. Each edge can be labelled with the time that they did. Such a graph database could be used for contact tracing: whenever someone became ill, we could query the graph to discover with whom they had been in contact over a range of time. Graph databases are quite useful for collecting data in a natural way. And we are beginning to see organizations build extremely large graph databases. For example, the Uniprot SPARQL Endpoint (dataset) consists of 63,376,853,475 edges as of a recent time. Uniprot (UNIversal PROTein resource) is a freely accessible, popular repository of protein data used by biologists. But such graph databases are only as useful as, well, however we can use them to get useful information back out. Because of the immense size graph databases can be, queries over them can be hard to answer, to evaluate efficiently. A query is not useful if you have to wait years for the answer! Graph databases are a fairly new technology. So we are at the start of learning how to use and work with them efficiently. This includes how to evaluate queries over them efficiently. Other types of databases have been around much longer; we have much deeper experience how to work with them. In this work, we adapt methods of query optimization for more efficient query evaluation for graph databases. Conjunctive queries (a useful class) for graph databases are small graphs themselves. We model the answers to a query as a graph too, an answer graph. This is a _factorization_ technique that looks to be quite promising for graph data. And so towards making graph databases truly useful.