OLAPing Graph Data

Abstract

Online Analytical Processing (OLAP) comprises tools and algorithms that allow querying multi- dimensional databases. It is based on the multidimensional model, where data can be seen as a cube such that each cell contains one or more measures that can be aggregated along dimensions. In a “Big Data” scenario, traditional data warehousing and OLAP operations on cubes are clearly not sufficient to address the current data analysis requirements, for example, for social network analysis. Furthermore, OLAP operations and models can expand the possibilities of graph analysis beyond the traditional graph-based computation, like shortest-path, centrality analysis and so on. In spite of this, there is not much work on the problem of taking OLAP analysis to the graph data model. In this paper, we propose a formal multidimensional data model for graph analysis, that consid- ers not only the basic graph data, but background information in the form of dimension hierarchies as well. The graphs in our model are node- and edge-labelled directed multi-hypergraphs, called graphoids, which can be defined at several different levels of granularity using the dimensions associ- ated with them. We define operations over this model, like the ones used in typical OLAP on cubes. We show that this model is more powerful than the traditional cube model, since hyperedges can connect a variable number of nodes, possibly of different types. This feature is not easy to represent in the OLAP cube model. Finally, we show that the classic data cube model is a particular case of the graphoid data model. As one of our main results, we prove that the graphoid-based operations are at least as powerful as the classical OLAP operations on cubes.