Вестник КРАУНЦ. Физ.-мат. науки. 2023.Т. 43. №2. C. 44-54. ISSN 2079-6641

ИНФОРМАЦИОННЫЕ И ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ
https://doi.org/10.26117/2079-6641-2023-43-2-44-54
Научная статья
Полный текст на русском языке
УДК 004.6

Содержание выпуска

Read English Version 

Бинарное кодирование иерархических структур

В. С. Кириллов^\ast

Кабардино-Балкарский научный центр Российской академии наук, 360010, г. Нальчик, ул. Балкарова, 2, Россия

Аннотация. В данной статье представлен алгоритм, который дает расширенные возможности представления ключей для иерархических структур. Использование бинарного представления материализованного пути позволяет эффективно сортировать узлы путем побитного сравнения и быстро вычислять верхний и нижний пределы для всех ключей элементов поддерева. Эта методика широко применяется в проектировании баз данных и в задачах фильтрации информации. В работе проведено сравнение данного алгоритма с различными подходами, используемыми в известных серверах баз данных. Результаты исследования подтверждают эффективность предложенного метода и его преимущества по сравнению с альтернативными подходами. Он обеспечивает более быстрое выполнение операций сортировки и вычисления пределов ключей, что является критически важным для эффективного функционирования баз данных и обработки больших объемов информации. Таким образом, представленный алгоритм имеет значительное практическое применение и может быть полезным инструментом при разработке и оптимизации баз данных, а также в других задачах, связанных с обработкой и фильтрацией информации.

Ключевые слова: деревья данных, иерархии, реляционные базы данных и модели

Получение: 03.04.2023; Исправление: 12.04.2023; Принятие: 16.04.2023; Публикация онлайн: 30.06.2023

Для цитирования. Кириллов В. С. Бинарное кодирование иерархических структур // Вестник КРАУНЦ. Физ.-мат. науки. 2023. Т. 43. № 2. C. 44-54. EDN: XUMKPG. https://doi.org/10.26117/2079-6641-2023-43-2-44-54.

Финансирование. Работа выполнялась без поддержки фондов.

Конкурирующие интересы. Конфликтов интересов в отношении авторства и публикации нет.

Авторский вклад и ответственность. Автор участвовал в написании статьи и полностью несет ответственность
за предоставление окончательной версии статьи в печать.

^\astКорреспонденция: E-mail: vkirillov74@gmail.com

Контент публикуется на условиях Creative Commons Attribution 4.0 International License

© Кириллов В. С., 2023

© ИКИР ДВО РАН, 2023 (оригинал-макет, дизайн, составление)

Список литературы

  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, pp. 903–908
    http://www.cse.iitb.ac.in/infolab/Data/Courses/CS632/2014/2007/Papers/ordpath.pdf.
  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, pp. 47-57.
  4. 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, 2012. vol. 53, no. 18.
  7. Tropashko V. Nested Intervals Tree Encoding with Continued Fraction, 2004 arXiv preprintcs/0402051.
  8. Tropashko V. Nested intervals tree encoding in SQL,ACM SIGMOD Record, 2005. vol. 34, no. 2, pp. 47–52.
  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. San Francisco: Morgan Kaufmann Publishers Inc, 2004. 436 pp.
  12. Celko J. SQL for Smarties: Advanced SQL Programming. San Francisco: Morgan Kaufmann Publishers Inc, 1999. 576 pp.
  13. Celko J. Thinking in Auxiliary Sets, Temporal, and Virtual Tables in SQL. Burlington: Morgan Kaufmann Publishers Inc, 2008. 576 pp.
  14. Celko J. SQL for Smarties: Advanced SQL Programming, third edition. San Francisco: Morgan Kaufmann Publishers Inc, 2005. 576 pp.
  15. Celko J. SQL for Smarties: Advanced SQL Programming, fourth edition. Burlington: Morgan Kaufmann Publishers Inc, 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, 1998. vol. 3, no. 5 http://supertech.csail.mit.edu/papers/debruijn.pdf.
  17. Anderson S. Count the consecutive zero bits (trailing) on the right with modulus division and lookup, 2005 URL:
    https://graphics.stanford.edu/ seander/bithacks.html#ZerosOnRightModLookup.
  18. Anderson S. Reverse bits in word by lookup table, 2005 URL: https://graphics.stanford.edu/ seander/bithacks.html#BitReverseTable.
  19. Kernighan W. B., Ritchie D. The C programming language. Burlington: Pearson Education Asia, 2002.
  20. Beeler M., Gosper R.W., Schroeppel R. H. MIT Artificial intelligence memo, vol. 239. Burlington: Feb, 1972.
  21. Anderson S. Interleave bits by table lookup, 2005 InterleaveTableLookup.

Информация об авторе

Кириллов Владимир Святославович – кандидат физико-математических наук, доцент, научный сотрудник КБНЦ РАН, Россия, ORCID 0009-0007-3996-1844

Читать статьюСкачать статью