Geodesic
Binary coding of hierarchical structures
Vestnik KRAUNC. Fiziko-matematičeskie nauki, Tome 43 (2023) no. 2, pp. 44-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

This article presents an algorithm that provides enhanced capabilities for representing keys in hierarchical structures. By using a binary representation of the materialized path, it allows efficient sorting of nodes through bitwise comparison and rapid computation of upper and lower bounds for all keys within the subtree. This methodology finds widespread application in database design and information filtering tasks. The study compares this algorithm with various approaches used in well-known database servers. The research findings confirm the effectiveness of the proposed method and its advantages over alternative approaches. It enables faster execution of sorting operations and computation of key bounds, which are critical for the efficient functioning of databases and processing large volumes of information. Therefore, the presented algorithm holds significant practical relevance and can serve as a valuable tool in the development and optimization of databases, as well as in other tasks related to information processing and filtering.
Keywords: trees data, hierarchies, relational database & models. 
@article{VKAM_2023_43_2_a3,
     author = {V. S. Kirillov},
     title = {Binary coding of hierarchical structures},
     journal = {Vestnik KRAUNC. Fiziko-matemati\v{c}eskie nauki},
     pages = {44--54},
     year = {2023},
     volume = {43},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VKAM_2023_43_2_a3/}
}
TY  - JOUR
AU  - V. S. Kirillov
TI  - Binary coding of hierarchical structures
JO  - Vestnik KRAUNC. Fiziko-matematičeskie nauki
PY  - 2023
SP  - 44
EP  - 54
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VKAM_2023_43_2_a3/
LA  - ru
ID  - VKAM_2023_43_2_a3
ER  - 
%0 Journal Article
%A V. S. Kirillov
%T Binary coding of hierarchical structures
%J Vestnik KRAUNC. Fiziko-matematičeskie nauki
%D 2023
%P 44-54
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/VKAM_2023_43_2_a3/
%G ru
%F VKAM_2023_43_2_a3
V. S. Kirillov. Binary coding of hierarchical structures. Vestnik KRAUNC. Fiziko-matematičeskie nauki, Tome 43 (2023) no. 2, pp. 44-54. http://geodesic.mathdoc.fr/item/VKAM_2023_43_2_a3/

[1] O'Neil P., O'Neil E., Pal S., Cseri I., Schaller G., Westbury N., “ORDPATHs: Insert-Friendly XML Node Labels”, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004, 903–908 http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2014/2007/Papers/ordpath.pdf | DOI

[2] PostgreSQL index - ltree URL: https://www.postgresql.org

[3] Guttman A., “R-trees: A dynamic index structure for spatial searching”, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, 47-57

[4] Zabavskyy A., Closure Table Pattern to Model Hierarchies in NoSQL URL: https://towardsdatascience.com

[5] Oracle - Hierarchical Queries URL: https://docs.oracle.com

[6] Abdelali E., Mazouz S. et al., “Different approaches to modeling the trees data in relational database”, International Journal of Computer Applications, 53:18 (2012) | DOI

[7] Tropashko V., Nested Intervals Tree Encoding with Continued Fraction, 2004 arXiv preprint cs/0402051

[8] Tropashko V., “Nested intervals tree encoding in SQL”, ACM SIGMOD Record, 34:2 (2005), 47–52 | DOI

[9] Tropashko V., Trees in SQL: Nested Sets and Materialized Path, 2002 URL: www.dbazine.com/tropashko4.shtml

[10] Tropashko V., Nested Intervals with Farey Fractions, 2004 URL: arXiv preprint cs.DB/0401014

[11] Celko J., Joe Celko's SQL for Smarties: Trees and Hierarchies, Morgan Kaufmann Publishers Inc, San Francisco, 2004, 436 pp.

[12] Celko J., SQL for Smarties: Advanced SQL Programming, Morgan Kaufmann Publishers Inc, San Francisco, 1999, 576 pp.

[13] Celko J., Thinking in Auxiliary Sets, Temporal, and Virtual Tables in SQL, Morgan Kaufmann Publishers Inc, Burlington, 2008, 576 pp.

[14] Celko J., SQL for Smarties: Advanced SQL Programming, third edition, Morgan Kaufmann Publishers Inc, San Francisco, 2005, 576 pp.

[15] Celko J., SQL for Smarties: Advanced SQL Programming, fourth edition, Morgan Kaufmann Publishers Inc, Burlington, 2011

[16] Leiserson Ch. E., Prokop H., Randall K. H., “Using de Bruijn sequences to index a 1 in a computer word”, Available on the Internet from http://supertech.csail.mit.edu/papers.html, 3:5 (1998)

[17] Anderson S., Count the consecutive zero bits (trailing) on the right with modulus division and lookup , 2005 URL: https://graphics.stanford.edu/

[18] Anderson S., Reverse bits in word by lookup table , 2005 URL: https://graphics.stanford.edu/

[19] Kernighan W. B., Ritchie D., The C programming language, Pearson Education Asia, Burlington, 2002

[20] Beeler M., Gosper R.W., Schroeppel R. H., MIT Artificial intelligence memo, v. 239, Feb, Burlington, 1972

[21] Anderson S., Interleave bits by table lookup , 2005 InterleaveTableLookup