Scalability of Reflexive-Transitive Closure Tables

Scalability of Reflexive-Transitive Closure Tables as Hierarchical Data Solutions

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

Advertisements

No comments yet... Be the first to leave a reply!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: