Профилирование данных — это процесс анализа данных, направленный на извлечение метаданных [1]. Его можно разделить на два типа: ненаукоёмкое и наукоёмкое [8]. Профилирование первого типа включает в себя поиск таких метаданных как, например, время создания данных и их авторство. Второй тип направлен на выявление такой гораздо более содержательной информации, как закономерности в данных. Анализируемые данные можно классифицировать на основе логической модели данных, к которой они относятся: графовые, табличные, транзакционные, пространственные и т. д. [3]. Модель данных определяет подходы, которые используются в алгоритмах поиска закономерностей. В данной работе будем рассматривать только табличные данные.
Существует множество способов формализации понятия закономерностей в табличных данных [4,5]. Одним из примеров такой формализации являются хорошо известные функциональные зависимости [11]. Такие формальные описания будем называть примитивами или просто зависимостями. Информация о закономерностях в данных используется для решения таких прикладных задач, как очистка данных (data cleaning), исследование данных (data exploration), реверс-инжиниринг баз данных (database reverse engineering) и оптимизация запросов в системах управления базами данных [1,15]. Поэтому были разработаны и продолжают разрабатываться алгоритмы автоматического поиска зависимостей.
Другим примером закономерности в табличных данных является уникальная комбинация колонок (Unique Column Combination, UCC) — набор атрибутов таблицы, проекция по которым не имеет одинаковых кортежей. UCC называется минимальной, если никакое подмножество ее атрибутов не является UCC. Важным свойством UCC является то, что уникальность комбинации колонок сохраняется при добавлении в неё любых других колонок. Это означает, что при автоматическим поиске UCC, достаточно находить только минимальные. Информация о том, какие комбинации колонок являются уникальными, необходима для решения таких задач, как сопоставление схем (schema matching) [19] или интеграция данных (data integration) [22]. Однако такая информация не всегда доступна, поэтому возможность поиска минимальных UCC над заданной таблицей является важной функциональностью любого профилировщика данных.
Платформа Desbordante [7] является наукоёмким профилировщиком данных с открытым исходным кодом. Она содержит алгоритмы поиска различных примитивов и предоставляет интерфейсы к ним, а также реализует сценарии решения прикладных задач анализа данных. Начальной мотивацией для создания Desbordante послужили недостатки существующей платформы Metanome [6], описанные в работе [8]. К ним относятся, например, не самая оптимальная производительность из-за использования Java в качестве основного языка программирования и отсутствие дружественных к пользователю интерфейсов. Более того, в Metanome алгоритмы поиска примитивов изолированы от реальных задач, то есть платформа не предоставляет ничего кроме самих алгоритмов, что уменьшает ее эффективность в применении к индустриальным задачам. Поэтому одной из целей Desbordante является предоставление возможностей по решению прикладных задач с помощью этих алгоритмов. В данный момент Desbordante активно развивается и нуждается в расширении набора поддерживаемых примитивов, в том числе в поддержке UCC. Это послужило мотивацией для задачи разработки высокопроизводительного алгоритма поиска уникальных комбинаций колонок, поставленной перед автором данной работы.
В ходе работы были достигнуты следующие результаты.
1. Выполнен обзор существующих подходов к автоматическому поиску UCC и выбран один из наиболее эффективных алгоритмов поиска — HyUCC. С целью переиспользования имеющегося кода изучен алгоритм поиска функциональных зависимостей HyFD, как алгоритм того же класса, что и HyUCC, и его реализация в Desbordante.
2. Алгоритм HyUCC реализован для платформы Desbordante (C++). Созданы интерфейсы, общие для любых алгоритмов поиска UCC, модуль тестирования и интерфейс к HyUCC для взаимодействия через Python. При реализации были выделены в отдельные модули и переиспользованы общие части HyUCC и HyFD.
3. С помощью профилирования найдены узкие места и реализована модифицированная версия алгоритма с использованием многопоточности.
4. В рамках экспериментов использованы синтетические и реальные наборы данных, применявшиеся авторами Metanome. Были выявлены следующие факты:
• обычная версия HyUCC, реализованная в платформе Desbordante, в среднем в 21 раз эффективнее реализации в Metanome;
• модифицированная версия алгоритма в среднем в 2.5 раз эффективнее обычной реализации в платформе Desbordante, и в 17 раз — параллельной версии в Metanome;
• модифицированная версия алгоритма потребляет в десять раз меньше памяти, чем многопоточная реализация в Metanome.
Код реализации открыт и доступен в репозитории4.
4https://github.com/Mstrutov/Desbordante
