White Papers

View Full Paper

Abstract

Reflexive-Transitive Closure (RTC) tables, when used to persist hierarchical data, present many advantages over alternative persistence strategies such as path enumeration. Such advantages include, but are not limited to, referential integrity and a simple structure for data queries. However, RTC tables grow exponentially and present a concern with scaling both operational performance of the RTC table and volume of the RTC data. Discovering these practical performance boundaries involves understanding the growth patterns of reflexive and transitive binary relations and observing sample data for large hierarchical models.

Contents

1 Introduction
2 Reflexive-Transitive Closure Properties
2.1 Reflexivity
2.2 Transitivity
2.3 Closure
3 Scalability Analysis
3.1 Rate of Growth
3.1.1 Depth-Wise Growth
3.1.2 Breadthwise Growth
3.1.3 Assessing Practical Growth Constraints
3.2 Time per Depth-Wise Growth
3.3 Space Consumption per RTC Table Growth
4 Conclusion
5 Appendix
5.1 Sampling Environment Specifications
7 References

Tagged: closure table, data, hierarchy, PCG, whitepaper