[ Russian ] [ English ]

Зависимости в данных и их поддержка на уровне СУБД

Никита Бобров
СПбГУ

Исследования зависимостей в данных начали свое развитие одновременно с появлением реляционной модели данных [1]. Изначально зависимости нашли свое применение в качестве инструмента для описания ограничений целостности, а все нормальные формы отношения (начиная с 2NF) в том или ином виде определялись через функциональные или мультизначные зависимости. Зависимости использовались для нормализации отношений базы данных. Однако, эта задача не могла быть решена администратором базы данных без знания предметной области -- зависимости описывались вручную и формировались на этапе проектирования БД. Таким образом, с увеличением объемов обрабатываемых данных и запросов на их поддержку (данные могут быть сырыми и не содержать описания возможных ограничений), появилась потребность в автоматизированном поиске зависимостей.

Первые успехи [2, 3] в новой области позволили найти применение зависимостям для решения таких задач как очистка данных, проектирование схемы БД, оптимизация запросов. При этом были выведены и новые типы зависимостей, с помощью которых описывались более сложные связи в данных. За 45 лет развития области было определено несколько десятков различных типов зависимостей [4]. Поиск таких связей дает новые представления о хранимых данных, поэтому сегодня мы можем говорить, что знание о зависимостях может быть полезно не только для администратора БД, но и аналитиков и исследователей конкретной предметной области [5, 6].

Несмотря на огромное количество потенциальных зависимостей в данных и их активное использование, до сих пор нет удобного инструмента для их обработки, хранения, визуализации. На данный момент единственным существующим решением являются каркасы (framework) разработки алгоритмов поиска зависимостей [7]. Обычно результатом процесса поиска является текстовый файл, содержащий десятки тысяч зависимостей, среди которых лишь единицы могут представлять интерес. В связи с этим, актуальной является задача реализации эффективного и удобного метода, позволяющего разместить данные и их зависимости в одной экосистеме. Такое решение сократит количество промежуточных шагов по выгрузке и обработке данных в сторонней от СУБД среде, и даст возможность манипулировать обнаруженными зависимостями с помощью декларативных средств. Предлагаемый метод может быть реализован в виде отдельной компоненты СУБД, выполняющей параметризованный поиск зависимостей, хранение полученного результата с учетом обновления данных и фильтрацию «полезных» зависимостей. На фоне последних трендов по размещению аналитики внутри СУБД [8, 9, 10], задача реализации поддержки зависимостей представляет особый интерес.

В первой части доклада будет представлен обзор наиболее активно используемых типов зависимостей, будут даны теоретические основы для определения задачи их поиска.

Вторая часть будет посвящена размещению зависимостей внутри СУБД, их поддержке на уровне модулей обработки запросов, и расширению стандарта SQL новыми операторами для манипуляции зависимостями.

Слайды доклада.

Литература:

  1. Codd, E. F. (1972). “Further Normalization of the Data Base Relational Model”. In: Courant Computer Science Symposia 6, Data Base Systems. New York City: Prentice-Hall.
  2. Huhtala, Y. et al. (Jan. 1999). “Tane: An Efficient Algorithm for Discovering Functional and Approximate Dependencies”. In: The Computer Journal 42.2, pp. 100–111. ISSN: 0010-4620. DOI: 10.1093/comjnl/42.2.100.
  3. Flach, Peter A. and Iztok Savnik (Aug. 1999). “Database Dependency Discovery: A Machine Learning Approach”. In:AI Commun.12.3, pp. 139–160. ISSN: 0921-7126.
  4. Caruccio, Loredana, Vincenzo Deufemia, and Giuseppe Polese (Jan. 2016). “Relaxed Functional Dependencies — A Survey of Approaches”. In: IEEE Transactions on Knowledge and Data Engineering 28.1, pp. 147–165. ISSN: 1041-4347. DOI: 10.1109/TKDE.2015.2472010.
  5. Schirmer, Philipp et al. (2019). “DynFD: Functional Dependency Discovery in Dynamic Datasets”. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 253–264.
  6. Papenbrock, Thorsten and Felix Naumann (2016). “A Hybrid Approach to Functional Dependency Discovery”. In: Proceedings of the International Conference on Management of Data (SIGMOD). New York, NY, USA. ACM, pp. 821–833.
  7. Thorsten Papenbrock, Tanja Bergmann, Moritz Finke, Jakob Zwiener, and Felix Naumann. 2015. Data profiling with Metanome. Proc. VLDB Endow. 8, 12 (August 2015), 1860–1863. DOI: https://doi.org/10.14778/2824032.2824086.
  8. Abo Khamis, Mahmoud et al. (2018). “In-Database Learning with Sparse Tensors”. In: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. SIGMOD/PODS ’18. Houston, TX,USA: ACM, pp. 325–340. ISBN: 978-1-4503-4706-8.
  9. Feng, Xixuan et al. (2012). “Towards a Unified Architecture for in-RDBMS Analytics”. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. SIGMOD ’12. Scottsdale, Arizona, USA: ACM, pp. 325–336. isbn: 978-1-4503-1247-9.
  10. Hellerstein, Joseph M. et al. (Aug. 2012). “The MADlib Analytics Library: Or MAD Skills, the SQL”. In: Proc. VLDB Endow. 5.12, pp. 1700–1711. ISSN:2150-8097.
Supported by Synthesis Group