Pith. sign in

REVIEW 2 major objections 6 minor 18 references

Online Analytical Processsing on Graph Data

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the classical OLAP cube operations Roll-Up, Drill-Down, Slice and Dice can be simulated by operations on node- and edge-labelled directed multi-hypergraphs called graphoids, making the data cube a special case of…

desk verdict Genuine formal model with a load-bearing Drill-Down gap in Theorem 1; fixable, but the central expressiveness claim is not proven as stated. read the letter →

arxiv 1909.01216 v1 pith:GG726O5N submitted 2019-09-03 cs.DB

Leticia Gómez , Bart Kuijpers , Alejandro Vaisman This is my paper · ORCID
classification cs.DB
keywords OLAPgraphoidmulti-hypergraphdatacubedimensionhierarchiesgraphdatabasesroll-updrill-down
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes graphoids, node- and edge-labelled directed multi-hypergraphs, as a formal multidimensional model for OLAP on graphs, with dimension hierarchies as background information. It defines graph analogues of the classic cube operations, including Climb, Group, Aggregate, Roll-Up, Drill-Down, Slice, Dice, and n-Delete, and proves that the standard cube operations Roll-Up, Drill-Down, Slice, and Dice can be simulated by graphoid operations. The consequence is that the classical data cube is a particular case of the graphoid data model, so any analysis expressible in multidimensional OLAP is expressible on graphoids. The reported experiments indicate that for classic OLAP queries the graphoid implementation stays competitive with relational OLAP, while for graph-metric aggregations such as shortest-path queries it succeeds where relational OLAP does not terminate.

What carries the argument

The central object is the graphoid: a directed multi-hypergraph whose nodes and hyperedges carry labels made of attribute-value pairs, where attribute values are members of dimension levels. The load-bearing operation is Roll-Up, defined as $\mathrm{Aggr}(\mathrm{Minimize}(\mathrm{Climb}(G,\ldots,D_c.(\ell_c\to\ell'_c))),\#e,M,F)$: Climb replaces dimension values by their roll-up along a hierarchy, Minimize contracts nodes with identical non-identifier labels, and Aggr merges parallel hyperedges by applying an aggregation function to a measure attribute. The star-graphoid encoding, in which each cube cell is one hyperedge incident to all coordinate nodes, is what makes the simulation argument work.

What would settle it

Construct a base graphoid with two parallel hyperedges that differ only in their Date and Duration attributes, apply Aggr with Sum to merge them, discard the base graphoid, and apply the paper's Drill-Down operation to the merged graphoid along Time; because Drill-Down is defined as $\mathrm{Aggr}(\mathrm{Minimize}(\mathrm{Climb}(G,\ldots,D_d.(\mathrm{Bottom}\to\ell'_d))),\#e,M,F)$, it cannot restore the discarded Date and Duration values, so the result is not the original base graphoid and the inverse relationship fails.

Watch

Extended reading notes

Core claim

Section 5 encodes each classical data cube $C$ as a star-graphoid $\mathrm{Star}(C)$: nodes represent dimension members and each measure cell becomes a hyperedge whose target set contains the coordinate nodes. Theorem 1 then proves that cube Roll-Up is simulated by graphoid Roll-Up, decomposed as Climb, Minimize, and Aggr; Slice is simulated by rolling up to All and then deleting the dimension nodes with n-Delete; Dice is simulated by the strong Dice operation; and Drill-Down is treated as a roll-up from the Bottom level of the descending dimension. The proof establishes that the graphoid OLAP operations are at least as powerful as the classical cube OLAP operations.

Load-bearing premise

The proof hinges on the assumption that roll-up and drill-down are inverse operations, stated in Section 4.5 as a simplicity assumption; once Aggregate merges fine-grained edges into one edge, the original attribute values are gone, so drill-down cannot recover them from the coarse graphoid alone.

Editorial extensions

If this is right

  • Every classical cube OLAP query can be expressed in the graphoid OLAP model, so the cube is a limiting case of graphoids.
  • OLAP-style aggregation along dimension hierarchies applies directly to graph-shaped data without flattening n-ary facts into fixed-width relational tables.
  • For classic OLAP queries on the tested call datasets, the graphoid implementation is competitive with relational OLAP, and for aggregations over graph metrics such as shortest paths it completes queries the relational alternative does not finish within the time limit.
  • Users of cube OLAP can keep the conceptual cube semantics while the underlying data is stored and queried as a graph, because the graphoid operations mirror the cube operations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Theorem 1's Drill-Down case only goes through under the paper's stated assumption that roll-up and drill-down are inverses; after Aggr has merged edges, the original attribute values no longer exist in the coarse graphoid, so a practical drill-down implementation must retain the base graphoid or a change log.
  • The star-graphoid encoding suggests a broader correspondence: any aggregation semilattice over a hypergraph could simulate the cube algebra; extending the simulation to non-decomposable aggregates such as average or median would require checking whether the Aggr step still preserves the semantics.
  • The experiments leave open whether graph-metric aggregations scale to much larger graphs, since the larger dataset already makes one shortest-path aggregation time out; indexing or approximate shortest-path algorithms would be the natural test.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper proposes a formal multidimensional graph data model called graphoids: node- and edge-labelled directed multi-hypergraphs whose labels are drawn from dimension hierarchies, together with operations Climb, Group, Aggr, Roll-Up, Drill-Down, Dice, Slice, and n-Delete. The central theoretical claim, stated as Theorem 1 in Section 5.2, is that the classical cube OLAP operations Roll-Up, Drill-Down, Slice, and Dice can be simulated by graphoid OLAP operations, making the classic data cube a special case of the graphoid model. The paper also reports a case study comparing a Neo4j graphoid-style implementation with two PostgreSQL relational OLAP representations on group-call data, arguing that graphoids are competitive for classic OLAP queries and clearly better for graph-metric aggregations such as shortest-path queries.

Significance. If Theorem 1 were fully supported, the paper would make a useful formal contribution: it gives a precise algebraic embedding of a substantial fragment of multidimensional OLAP into a hypergraph model, and it provides an explicit star representation of cubes as graphoids. The formal framework is coherent and the Roll-Up and Slice simulations are convincing. The case study is also valuable as evidence of feasibility, and the authors are appropriately careful to present it as a plausibility study rather than an exhaustive benchmark. However, the Drill-Down case of Theorem 1 is not proved and, as stated, is not a valid simulation; the Dice case also relies on an unstated restriction on the levels at which filter conditions can be evaluated. These issues affect the main expressiveness claim and need to be repaired before the theorem can be accepted.

major comments (2)
  1. [Section 4.5 and Section 5.2, Theorem 1] The Drill-Down case of Theorem 1 is unsupported. The definition in Section 4.5 reads Drill-Down(G, ..., D_d.(l_d -> l'_d)) = Aggr(Minimize(Climb(G, ..., D_d.(Bottom -> l'_d)))). This expression is not a well-defined operation on a graphoid that is already at level l_d: such a graphoid contains no labels in dom(D_d.Bottom), so the Climb operation has no source values to replace. The footnote in Section 4.5 attempts to justify this by assuming that roll-up and drill-down are inverse operations 'for the sake of simplicity, and without loss of generality.' That assumption is false after Aggr: once several fine-grained edges are replaced by one aggregate edge, the individual values no longer exist in the graphoid and cannot be reconstructed from it. The sentence in the proof of Theorem 1 that 'no proof is needed' for Drill-Down therefore hides a dependency on access to the base graphoid. If the intended meaning is that drill-down is evaluated on the base graphoid, then the operation is not an operation on the graphoid being drilled, and Theorem 1 must be restated and proved accordingly.
  2. [Section 4.6 and Section 5.2, Dice simulation] The Dice simulation in Theorem 1 only works for conditions evaluated at the granularity already present in the graphoid, but Definition 10 explicitly allows conditions at levels higher than the graphoid's current levels. The proof of the Dice case asserts that the unique adjacent node in a star graphoid 'contains information on D.l' and that the atomic condition is true there. However, if the star graphoid is at the Bottom level and phi refers to a higher level l, the adjacent node contains a Bottom-level value, not a level-l value, so the condition is merely 'not false' under the weak semantics of Section 4.6. The graphoid operation s-Dice(Star(C), phi) may therefore keep edges that the cube Dice(C, phi) would filter out, because conditions over rolled-up levels are never actually tested. The theorem and proof need either to restrict phi to the current granularity or to give a precise roll-up semantics that evaluates higher-level conditions correctly.
minor comments (6)
  1. [Title and Section 1] The word 'Processsing' in the title is misspelled; it should be 'Processing.'
  2. [Section 3.1] The sentence 'In thses graphs, rolling-up...' contains a typo: 'thses' should be 'these.'
  3. [Section 4.2, Definition 7] In the definition of edge-grouping, the text says 'Climb(G, #n, D_k.(l_k -> l'_k))' where the operation is on hyperedges of type #e; this should presumably be 'Climb(G, #e, D_k.(l_k -> l'_k)).'
  4. [Section 6.1 and Table 3] In Table 3 the repeated column headers 'Calls Calls Calls Calls-alt Calls-alt Calls-alt' are hard to parse, and the meaning of 'N/A' and the infinity symbol '∞' should be stated explicitly in the caption or text.
  5. [Section 6.4, Query 1] The text refers to 'Figure ??' for the recursive SQL query, but no such figure is included; the reference should be removed or the figure supplied.
  6. [Reference [16]] Reference [16] is listed with year 2017, but the conference ADBIS 2019 is mentioned in the text; please check and correct the year.

Circularity Check

1 steps flagged · score 6.0 of 10

Theorem 1's Drill-Down case is definitional: the graphoid drill-down is stipulated as a Climb from Bottom, then declared to need no proof.

  1. self definitional [Section 4.5 (Drill-Down definition) and Section 5.2 (Theorem 1 proof, Drill-Down paragraph)]
    "Note also that, descending from a level 𝓁_d down to a level 𝓁'_d along a dimension D_d is equivalent to climbing from the bottom level of D_d, D_d.Bottom, to the level 𝓁'_d along D_d. Thus, the drill-down of G ... is defined as Aggr(Minimize(Climb(G,...,D_d.(Bottom→𝓁'_d)))) ... As mentioned above, the drill-down to level 𝓁 can be seen as a roll-up from the Bottom level to level 𝓁. Therefore, no proof is needed."

    The claimed simulation of classical Drill-Down is not proved; it is assumed in the definition of the graphoid operation. The expression Climb(G,...,D_d.(Bottom→𝓁'_d)) can only relabel attributes that already carry Bottom-level values, and after Aggr/Minimize these fine values have been replaced by one aggregate value, so a coarse graphoid contains no information from which Drill-Down could reconstruct them. The footnote admits that roll-up and drill-down are 'assumed' to be inverse 'without loss of generality', but aggregation is lossy, so this assumption is not harmless. When Theorem 1's proof says 'no proof is needed', it is because the conclusion was placed in the operation's definition, not because a graphoid expression was shown equivalent to the cube semantics of [11].

full rationale

Most of the paper is a straightforward formal embedding: the star-graphoid encodes cube cells as hyperedges, Roll-Up is verified by unpacking Climb/Minimize/Aggr over the encoding, Slice reduces to Roll-Up to All plus n-Delete, and Dice is checked edge-by-edge with the 'not false' convention. These are translation proofs with independent content; they do not merely restate the definitions. The principal circular (or definitional) step is the Drill-Down case of Theorem 1, where the operation is stipulated to be Aggr(Minimize(Climb(G,...,Bottom→𝓁'_d)))) and the proof then dismisses the case as needing no proof; no derivation connects this to the classical inverse-of-roll-up semantics. I do not count the citation to [11] for cube semantics as load-bearing circularity: it supplies the reference semantics rather than an unverified uniqueness theorem, and it is not used to forbid alternatives. The experimental comparison is empirical and not a fitted prediction. Overall this is partial circularity confined to one of the four operations, so a moderate score is appropriate.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

No free parameters: the formal model contains no fitted constants. The graphoid is the one invented entity. The axioms are mostly standard OLAP and domain assumptions; the roll-up and drill-down inverse assumption is the only clearly ad hoc one. The expressiveness theorem inherits its cube semantics from the authors' earlier OLAP algebra [11], a self-citation that supplies definitions rather than evidence.

assumptions (4)
  • domain assumption Dimension schemas are lattices with unique All and Bottom; hierarchy instances are trees and sound, meaning rollup along different paths gives the same result.
    Invoked in Section 3.2 ('sound dimension graphs are assumed') and needed so that Climb and Minimize are well-defined for all dimensions.
  • ad hoc to paper Roll-up and drill-down are inverse operations when no slice or dice intervenes.
    Assumed in Section 4.5 to justify Drill-Down as a roll-up from Bottom; not generally true after aggregation and load-bearing for Theorem 1's Drill-Down case.
  • standard math A data cube is a partial function from dimension domains to measure domains; cells exist only where the function is defined.
    Used in Section 5.2 to construct Star(C) and state Theorem 1; this is the standard semantics of OLAP cubes.
  • domain assumption The base graphoid contains all facts at the lowest granularity and is the input to all OLAP operations.
    Section 3.2, Definition 4; the model assumes a single base graph at Bottom level, which is why drill-down can be simulated only by returning to base data, but that return is not provided.
invented entities (1)
  • Graphoid
    purpose: Core data structure: a node- and edge-labelled directed multi-hypergraph with dimension-valued attributes, used to run OLAP operations over graphs.
    It is a formal modeling construct with no externally falsifiable prediction; its value is judged by expressiveness and usability, not by empirical fit.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Analytical Processsing on Graph Data." pith.science (2026). https://pith.science/paper/GG726O5N

@misc{pith2026190901216,
  author       = {Pith},
  title        = {Pith review of: Online Analytical Processsing on Graph Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GG726O5N}},
  note         = {Machine review of arXiv:1909.01216}
}
read the original abstract

Online Analytical Processing (OLAP) comprises tools and algorithms that allow querying multidimensional 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 are clearly not sufficient to address current data analysis requirements, for example, social network analysis. Furthermore, OLAP operations and models can expand the possibilities of graph analysis beyond the traditional graph-based computation. Nevertheless, there is not much work on the problem of taking OLAP analysis to the graph data model. This paper proposes a formal multidimensional model for graph analysis, that considers the basic graph data, and also background information in the form of dimension hierarchies. The graphs in this model are node- and edge-labelled directed multi-hypergraphs, called graphoids, which can be defined at several different levels of granularity using the dimensions associated with them. Operations analogous to the ones used in typical OLAP over cubes are defined over graphoids. The paper presents a formal definition of the graphoid model for OLAP, proves that the typical OLAP operations on cubes can be expressed over the graphoid model, and shows that the classic data cube model is a particular case of the graphoid data model. Finally, a case study supports the claim that, for many kinds of OLAP-like analysis on graphs, the graphoid model works better than the typical relational OLAP alternative, and for the classic OLAP queries, it remains competitive.

Figures

Figures reproduced from arXiv: 1909.01216 by the authors.

Figure 1
Figure 1. Dimension schemas for the dimensions Time ( [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. An example of a dimension instance I(σ(P hone)) for the dimen￾sion P hone. In what follows, “sound” dimension graphs are assumed. In thses graphs, rolling-up from the Bottom level, to the same element along different paths, gives the same result [11], typical in so-called balanced (or homogeneous) dimensions [15]. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Basic phone call data as a base graph. ut Note that, although the base graph plays the role of a multi-dimensional cube in classical OLAP (or a fact table in relational OLAP), a key difference is that this cube has a variable number of “axes”, since it can represent facts including a variable number of dimensions. The next example discusses two graphoids whose dimensions are at different levels of granularity. Later… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: A (Time.Day,Phone.Operator)-graphoid, based on the data shown in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: An alternative (Time.Day,Phone.Operator)-graphoid, based on the data shown in [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: (a) A node with label [#Phone, 11,Ph1, 880], where 880 expresses the expected bill. (b) An edgification of this node, where the expected billing information is moved to an edge that is labelled #HasExpectedBill. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: The result of the operation Roll-Up(G, {#Phone}, Time.(Day → Year); #Call, Duration, Sum) applied to the graphoid of [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]
Figure 8
Figure 8. Figure 8: An example of a Sales data cube with one measure: µ1 = sales [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. Figure 9: Star-representation of the fact (Lego, Antwerp, 1/1/2014; 10) (a). Petal-representation of the fact (Lego, Antwerp, 1/1/2014; 10) (b). dom(µ1) × · · · × dom(µm). This function maps each “cell” of the cube to m values for the measures. A cell of the cube with coordinate…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

  1. [1]

    R. Angles. A Comparison of Current Graph Database Models. In Proceedings of ICDE Workshops, pages 171–177, Arlington, VA, USA, 2012

    work page 2012

  2. [2]

    Angles, M

    R. Angles, M. Arenas, P. Barcel´ o, A. Hogan, J. L. Reutter, and D. Vr- goc. Foundations of modern query languages for graph databases. ACM Comput. Surv., 50(5):68:1–68:40, 2017

    work page 2017

  3. [3]

    C. Chen, X. Yan, F. Zhu, J. Han, and P. Yu. Graph OLAP: a multi- dimensional framework for graph data analysis. Knowl. Inf. Syst. , 21(1):41–63, 2009

    work page 2009

  4. [4]

    Cohen, B

    J. Cohen, B. Dolan, M. Dunlap, J.M. Hellerstein, and C. Welton. MAD Skills: New analysis practices for big data. Proceedings of the VLDB Endowment, 2(2):1481–1492, 2009

    work page 2009

  5. [5]

    Data Ware- housing and OLAP over Big Data: Current Challenges and Future Re- search Directions

    Alfredo Cuzzocrea, Ladjel Bellatreche, and Il-Yeol Song. Data Ware- housing and OLAP over Big Data: Current Challenges and Future Re- search Directions. In Proceedings of DOLAP, pages 67–70, New York, NY, USA, 2013. ACM

    work page 2013

  6. [6]

    G´ omez, Bart Kuijpers, and Alejandro A

    Leticia I. G´ omez, Bart Kuijpers, and Alejandro A. Vaisman. Performing OLAP over graph data: Query language, implementation, and a case study. In Proceedings of BIRTE, Munich, Germany, August 28, 2017 , pages 6:1–6:8, 2017

    work page 2017

  7. [7]

    G´ omez, Bart Kuijpers, and Alejandro A

    Leticia I. G´ omez, Bart Kuijpers, and Alejandro A. Vaisman. Analytical queries on semantic trajectories using graph databases. TGIS Trans. Geog. Inf. Syst., 23(5), 2019

    work page 2019

  8. [8]

    O. Hartig. Reconciliation of RDF* and property graphs. CoRR, abs/1409.3288, 2014

    arXiv 2014

Show all 18 references
  1. [9]

    The Data Warehouse Toolkit

    Ralph Kimball. The Data Warehouse Toolkit. J. Wiley and Sons, 1996. 32

    1996

  2. [10]

    M. B. Kraiem, J. Feki, K. Khrouf, F. Ravat, and O. Teste. Modeling and OLAPing social media: the case of twitter. Social Netw. Analys. Mining, 5(1):47:1–47:15, 2015

    2015

  3. [11]

    Bart Kuijpers and Alejandro A. Vaisman. An algebra for OLAP. In- telligent Data Analysis , 21(5), 2017

    2017

  4. [12]

    N. U. Rehman, A. Weiler, and M. H. Scholl. OLAPing social media: the case of twitter. In Advances in Social Networks Analysis and Mining 2013, ASONAM ’13 , pages 1139–1146, Niagara, ON, Canada, 2013

    2013

  5. [13]

    Robinson, J

    I. Robinson, J. Webber, and Emil Eifr´ em. Graph Databases. O’Reilly Media, 2013

    2013

  6. [14]

    Extracting top-k insights from multi-dimensional data

    Bo Tang, Shi Han, Man Lung Yiu, Rui Ding, and Dongmei Zhang. Extracting top-k insights from multi-dimensional data. In Proceedings of ACM SIGMOD, Chicago, IL, USA, May 14-19, 2017 , pages 1509– 1524, 2017

    2017

  7. [15]

    A. A. Vaisman and E. Zim´ anyi.Data Warehouse Systems: Design and Implementation. Springer, 2014

    2014

  8. [16]

    modelling and querying star and snowflake warehouses using graph databases

    Alejandro Vaisman, Florencia Besteiro, and Maximiliano Valverde. modelling and querying star and snowflake warehouses using graph databases. In Proceedings of ADBIS Conference 2019, Bled, Slovenia, Sept. 8-11, 2019 , 2017

    2019

  9. [17]

    Z. Wang, Q. Fan, H. Wang, K-L. Tan, D. Agrawal, and A. El Abbadi. Pagrol: Parallel graph OLAP over large-scale attributed graphs. In Proceeding of IEEE ICDE, pages 496–507, 2014

    2014

  10. [18]

    Graph Cube: on warehousing and OLAP multidimensional networks

    Peixiang Zhao, Xiaolei Li, Dong Xin, and Jiawei Han. Graph Cube: on warehousing and OLAP multidimensional networks. In Proceedings of ACM SIGMOD, pages 853–864. ACM, 2011. 33

    2011

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.