Зачем?

Все мы часто работаем с табличными данными. Таблицы, конечно, бывают разные. Особенно приятно, когда таблица сразу плоская. Плоская таблица - это когда шапка однострочная и таблица НЕ матричная. Пример - любая таблица в SQL базе. В статье будем говорить только о плоских таблицах.

С первого взгляда таблица - это просто. Строчки, колонки, шапка. Но когда долго работаешь с ними, понимаешь, что архитектура таблицы - довольно сложная тема. Однако именно она позволяет эффективно работать со сложными большими таблицами.

Представьте, что нам дали таблицу. Например такую. Строк 114к, столбцов 21. Допустим нам надо быстро понять, про что эта таблица, сделать её обзорный анализ. Какие у нас варианты?

взять Excel, pivot tables. Покрутить, повертеть.
загрузить в pandas/polars/duckdb. Там провести обстоятельный анализ.
проанализировать шапку, что за колонки есть, что они означают.
просто выборочно посмотрим на строчки. Пофильтровать, посортировать.

Варианты в целом хорошие. Но в какой-то момент я понял, что самое первое - надо задаться двумя фундаментальными вопросами:

Что является первичным ключом таблицы? (primary key, PK)
Какие функциональные зависимости есть в таблице? (functional dependency, FD)

Кроме этого, PK и FD могут быть использованы для процесса нормализации таблиц/баз данных. Эти задачи довольно часто встречается, хотя не всегда их называют именно такими терминами.

Замечу, что PK не может быть получен автоматически. Это даже не NP complete. Эта задача - экспертное решение архитектора данных. Автоматически обычно получают CK (candidate key, потенциальные ключи). И один из них - это PK.

Как отвечать на эти два вопроса?

Сложно, вообще говоря.

Когда мой основной инструмент был MS Excel, я применял pivot table для этого. Там довольно удобно проверять уникальность набора столбцов и наличие FD. Вручную правда. Основные потребности это закрывало. Но хотелось большего.

Далее я начал использовать Python. Эти же действия можно автоматизировать и проверять все возможные варианты. Метод brute force. В целом неплохо. Но тоже есть ограничения. Я реализовал поиск всех FD вида X - > Y, где обе стороны являются одной колонкой. Полный перебор долгий, значительно ускорить его сложно. Инструмент есть моем репозитории (github), которым, кстати, мы до сих пор активно используем.

Но всегда была мысль, а можно ли быстрее искать? Чтобы найти вообще все FDs. Существует ли алгоритм, который не делает полный перебор... Сходу на этот вопрос я ответить не мог.

Стоя на плечах гигантов

Почти сразу нашел интересную статью. Она стала для меня отправной точной в исследовании.

"FDTool: a Python application to mine for functional dependencies and candidate keys in tabular data" Matt Buranosky

Ниже представлены основные выводы, которые я сделал.

Оказывается анализ таблиц и поиск FDs интересует не только меня и уже давно (есть ссылки на статьи 2002 года - "Mining functional dependencies from data" Yao). Вообще, это активная область исследований. Однозначных ответов тут нет.

Полный перебор - плохая идея. Есть алгоритмы гарантированно лучше.

Главные параметры - количество строк и колонок. Идеального алгоритма на все случаи не существует. В целом, алгоритмы делятся на две части:

хорошо работают когда много строк, но мало колонок;
и наоборот, хорошо работают когда много колонок, но мало строк;

Конечно, добавление одной колонки повышает search space гораздо сильнее, чем добавление одной строки.

Обзор семи алгоритмов и их производительности неплохо сделан в статье "Functional Dependency Discovery:An Experimental Evaluation of Seven Algorithms", Papenbrock T, 2015.

Если колонок будет, скажем, 500, видимо, придется ждать CUDA support, квантовые компьютеры или AGI. Благо таких таблиц не много)

Какие-то алгоритмы сильнее используют RAM, какие то CPU. Обратите внимание на FD_Mine алгоритм, ниже речь пойдет именно о нем.

Используемые алгоритмы

Они разные. Ниже примерных ход мыслей для общего понимания.

Ключевая часть алгоритма - поиск всех базовых FDs.

Мы ищем такие FD (X -> Y), чтобы X было несократимо, а Y было одной колонкой. Это даст нам базовый набор FDs. Все остальные FDs будут выводиться из этого набора с помощью Armstrong’s Axioms:

– Reflexivity: Y ⊆ X implies X → Y;
– Augmentation: X → Y implies XZ → YZ;
– Transitivity: X → Y and Y → Z imply X → Z;
– Union: X → Y and X → Z imply X → YZ;
– Decomposition: X → YZ implies that X → Y and X → Z.

Сколько нам надо проверить FD-кандидатов? Самый наивный подход - взять powerset по всем колонкам и декартово перемножит с количеством колонок. Это дает верхнюю границу для оценки сложности. В коде ниже видно, что количество FD-кандидатов растет очень быстро.

import seaborn as sns
import math 
powerset = lambda n: sum(math.comb(n, i) for i in range(1, n+1))

for n in range(1, 15+1):
    print(f'Columns = {n},', f'candidate FDs = {powerset(n) * n:_}')

# prints:
# Columns = 1, candidate FDs = 1
# Columns = 2, candidate FDs = 6
# Columns = 3, candidate FDs = 21
# Columns = 4, candidate FDs = 60
# Columns = 5, candidate FDs = 155
# Columns = 6, candidate FDs = 378
# Columns = 7, candidate FDs = 889
# Columns = 8, candidate FDs = 2_040
# Columns = 9, candidate FDs = 4_599
# Columns = 10, candidate FDs = 10_230
# Columns = 11, candidate FDs = 22_517
# Columns = 12, candidate FDs = 49_140
# Columns = 13, candidate FDs = 106_483
# Columns = 14, candidate FDs = 229_362
# Columns = 15, candidate FDs = 491_505

Такой быстры рост кандидатов нельзя победить перейдя на Rust или C. Да, время выполнение сильно улучшится, но принципиально картина не изменится. Слишком быстро растет search space. Именно поэтому нужны оптимизации самого алгоритма, которые изменят его асимптотику.

Смотря на наш наивный алгоритм, понятно, что он избыточен. Например, если A -> B и B -> С, то проверять A -> C нет смысла. Это следует из аксиом (транзитивность). Другой пример, проверять AB -> A нет смысла, т.к. очевидно, что эта FD существует. Всё это и есть примеры прунинга, т.е. разных подходов к снижению количества кандидатов-FDs, которые нам надо проверить, чтобы прийти к ответу. Алгоритмы отличаются тем, как они делают прунинг.

Замечу также, что если требуется формально доказанный корректный алгоритм поиска FDs, стоит проводить исследование с повышенным вниманием. Встречаются неочевидные утверждения: "The pseudo-code proposed in the second version of FD_Mine (Yao & Hamilton, 2008) will under certain circumstances output non-minimal FDs (Papenbrock et al., 2015).".

После того, как все базовые FDs найдены, эквивалентности (X <-> Y) получаются тривиально, как две взаимные FDs.

Потенциальные ключи (PK) находятся отдельным алгоритмом, который берет на вход комплект найденных ранее FDs. Алгоритм действует примерно так: если набор колонок функционально определяет все остальные колонки - значит это PK (исходят из предположения, что полных дубликатов строк нет). Тут проблем с временем выполнения нет.

FDTool, форк форка

С практической точки зрения меня интересовали вопросы: есть ли код? Как его запустить?

В этой же статье, автор опубликовал github а также PyPi. Это CLI инструмент. Автор выбрал алгоритм FD_Mine, который хорошо работает где много строк. В целом хорошее решение. Неинтересные столбцы еще можно удалить экспертным суждением, а вот состав строк сокращать, обычно, нельзя.

Что меня смущало? Ну, во-первых, всё это добро было написано на Python2. Также, я люблю запускать анализ таблиц из самого Python в jupyter notebook, а не работать с CLI.

Я решил сделать форк и поправить эти небольшие моменты. Интересно, что форки этого репозитория уже делали до меня, их семь штук. Я выбрал один из них, чтобы меньше было поправлять.

Несколько интересных моментов про допиливание кода:

В основе кода был pandas dataframe. Самая затратная операция на dataframe - это df.drop_duplicates(Candidate). Т.е. скорость нахождения уникальных будет очень важна. Поэтому я решил переложить эту обязанность на polars. К моему удивлению, потребовалось изменить пару строк кода и всё заработало как часы!
Для ускорения работы кода я делаю аналог pd.factorize для каждого столбца в polars dataframe. С целыми числами работать быстрее. А на логику работы это никак не влияет.
Все столбцы в начале переименовываются в строки типа: "0" "1" "2" "3" ... Это позволяет немножко ускорить операции с шапкой таблицы и гарантировать отсутствие проблем со странными символами, которые могут оказаться в шапке таблице на входе.
Ранее инструмент выдавал результат только в формате текста. Это не очень удобно, т.к. иногда надо работать с результатом в Python. Теперь возврат содержит и визуализацию (str for printing) и сами контейнеры с первичной информацией (for coding). Причем сама визуализация также доработана, в плане сортировок элементов (модуль utils). Оказалось, сортировка дело тонкое)
Дебажить функцию, которая запускается в отдельном процессе не очень приятно. Поэтому для дебага я делал тестовый прямой запуск, чтобы сразу видеть Exceptions.
Без нейросетей создание форка проходило бы сложнее (помогли perplixity, mistral, deepseek,@saiga_igusev_bot).
Очень хотел добавить multiprocessing.pool в часть кода, когда надо находить много раз df.n_unique(subset=Candidate). По идее, это независимые вычисления. Но, видимо, конфликт с библиотекой polars. У меня не заработало. Пришлось убрать. Кстати в исходном форке также пытались это сделать, но в main не вмерджили)
Запуск основного кода в отдельном процессе лучше делать через библиотеку multiprocessing, а не через subprocess. Это, кстати, теперь мой дефолтный вариант для REPL (на основе сгенерированного кода LLM).

Основной код поиска FDs имеет хорошую лицензию - CC0-1.0 license (как я понял, допускает вообще всё, в т.ч. коммерческое использование).

Часть кода по определению CK - dbschemacmd (поиск candidate key, потенциальных ключей) лицензирована как Convertible Free Software License (C-FSL) Version 1.0. Тут сложнее, как я понял, требуется, чтобы производный код распространялся свободно.

В итоге получился довольно удобный инструмент. По применению можно посмотреть колаб. X`Сам репозиторий тут github. Также сделан релиз на pypi (!pip install fdtooldf).

Идеи по развитию

Причесать хорошенько весь код Python (линтеры, форматеры, имена переменных)
Переписать всё на Rust с максимальной оптимизацией
Реализовать несколько алгоритмов, которые закроют разные ситуации (много строк или много столбцов). Сейчас алгоритм про много строк. Более 10-15 столбцов уже тяжело.
Сделать углубленное исследование научных достижений в этой сфере
Попробовать объединить FDTool с моей библиотекой FlatTableAnalysis, там более приятный UX/UI
Подумать, можно ли использовать неточные алгоритмы для ускорения работы. Например, HyperLogLog++ (в polars уже даже встроен, algorithm for cardinality estimation). Определенные научные наработки по этому направлению уже есть, см. тут.

Если интересно - присоединяйтесь. Open source это хорошо.

Пара дополнительных ссылок

Целый институт изучает таблицы, много релевантных материалов тут. На сайте можно найти реализацию на Java семи самых известных алгоритмов поиска FDs (тут).

Вроде как особо удачный новый алгоритм - DFD. См. статью - DFD: "Efficient Functional Dependency Discovery" Abedjan, 2014.

Функциональные зависимости в таблице (удобный форк FDTool для python3)