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

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

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

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

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

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

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

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

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

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

Логические и нелогические запросы

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

Ссылки

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

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

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

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

[1]

[2]

[3]