Оценка запроса

Определение ответов на запрос в базе данных

В теории баз данных проблема оценки запроса — это проблема ^{[ требуется проверка ]} определения ответов на запрос в базе данных. Исследования в теории баз данных направлены на определение вычислительной сложности ответа на различные виды запросов в базах данных, в частности в реляционных базах данных .

Формальное определение

Задача оценки запроса принимает два входа: запрос, на который нужно ответить, и базу данных, на которой нужно ответить. Выходом задачи является набор ответов на запрос в базе данных. Если запросы являются булевыми запросами , т. е. запросы имеют ответ «да» или «нет» (например, булевы конъюнктивные запросы ), то задача оценки запроса является задачей принятия решений .

Проблема оценки запроса обычно ставится для определенного класса запросов и баз данных. Например, одним из примеров проблемы оценки запроса может быть проблема оценки конъюнктивного запроса в реляционной базе данных .

Вычислительную сложность задачи можно измерить разными способами ^[1] , учитывая тот факт, что два входных параметра задачи различны:

Совокупная сложность задачи оценки запроса — это ее вычислительная сложность , измеряемая как функция двух входных данных, т. е. запроса и базы данных, как это обычно бывает при вычислительной сложности.
Сложность данных — это вычислительная сложность, когда запрос фиксирован, а входными данными является только база данных. Например, мы говорим, что оценка запроса имеет полиномиальную сложность данных для класса запросов, если для каждого фиксированного запроса Q в этом классе, учитывая базу данных D , мы можем вычислить ответы на Q на D за полиномиальное время.
Реже мы можем изучать сложность запроса , которая является вычислительной сложностью, когда база данных фиксирована и когда входными данными является только запрос. Это также называется сложностью выражения . ^[2]

Классы запросов

Сложность оценки запросов можно изучать для нескольких классов запросов, например, ациклических запросов, конъюнктивных запросов , объединений конъюнктивных запросов , Datalog, регулярных путевых запросов и т. д., вплоть до логических формализмов, таких как логика первого порядка или монадическая логика второго порядка .

Например, для булевых конъюнктивных запросов сложность оценки запроса полиномиальна по сложности данных: она даже попадает в класс AC0 . Напротив, сложность запроса и объединенная сложность являются NP-полными ^[3] путем редукции от 3-раскрашиваемости . ^{[ требуется ссылка ]}

Булевы и небулевы запросы

Сложность оценки запроса может быть изучена для запросов, которые возвращают ответы, или для булевых запросов (запросы типа «да/нет»). Однако мы часто можем свести к случаю булевых запросов. Более конкретно, если количество ответов на запрос всегда полиномиально по размеру базы данных, и если мы можем переписать запрос в булев запрос для каждого ответа, то мы можем свести оценку запроса для небулевого запроса к полиномиально множеству проблем оценки булевых запросов. ^{[ необходима цитата ]}

Ссылки

^ Варди, Моше Й. (1982-05-05). "Сложность реляционных языков запросов (Расширенный реферат)". Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 137–146 . doi :10.1145/800070.802186. ISBN 978-0-89791-070-5.
^ Абитбуль, Серж; Халл, Ричард; Виану, Виктор (1994-12-02). Основы баз данных: Логический уровень (1-е изд.). Reading, Массачусетс: Pearson. ISBN 978-0-201-53771-0.
^ Греко, Джанлуиджи; Скарчелло, Франческо (2014-06-18). «Подсчет решений для конъюнктивных запросов: структурная и гибридная трактуемость». Труды 33-го симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных . PODS '14. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 132– 143. doi :10.1145/2594538.2594559. ISBN 978-1-4503-2375-8.

[1] Варди, Моше Й. (1982-05-05). "Сложность реляционных языков запросов (Расширенный реферат)". Труды четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 137–146 . doi :10.1145/800070.802186. ISBN 978-0-89791-070-5.

[2] Абитбуль, Серж; Халл, Ричард; Виану, Виктор (1994-12-02). Основы баз данных: Логический уровень (1-е изд.). Reading, Массачусетс: Pearson. ISBN 978-0-201-53771-0.

[3] Греко, Джанлуиджи; Скарчелло, Франческо (2014-06-18). «Подсчет решений для конъюнктивных запросов: структурная и гибридная трактуемость». Труды 33-го симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных . PODS '14. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 132– 143. doi :10.1145/2594538.2594559. ISBN 978-1-4503-2375-8.