Project

Scalable Graph Algorithms in Main Memory Databases

Principal Investigator

Alfons Kemper, Thomas Neumann

TU Munchen

Oracle Fellowship Recipient

Manuel Then

Oracle Principal Investigator

Hassan Chafi, Vice President, Research and Advanced Development
Sungpack Hong, Vice President, Oracle Labs

Summary

In this project we plan to develop algorithms and data structures that foster efficient query evaluation in RDF and graph database systems. This benefits not only production-ready systems such as Oracle RDF but also research projects like Oracle Labs's PGX. Current-generation database systems are disk-based: they primarily operate on disk-resident data and use main memory mainly for data caching. This wastes the potential of modern server machines with large amounts of main memory, as this caching logic is very expensive. However, as most customers' data is still larger than the available memory, main memory-only database systems are still not feasible. Thus, we want to develop compressed graph data structures that are primarily designed for main memory use, hence, leverage the properties of modern server machines but also gracefully fallback to on-disk processing when necessary. Further, we plan to research how pattern matching and graph analysis algorithms can benefit from such data structures. Doing so we will not only apply code generation for graph operators but also dynamic re-optimization based on runtime knowledge about the processed (sub-)graph.