Planning and Factorization for Graph Database Query Optimization and Evaluation

点击翻译按钮获取中文摘要

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.