Пособие посвящено изучению языков запросов для баз данных. В первой главе содержатся определения классов сложности глобальных предикатов и полноты языка запросов для заданного класса сложности. Показывается, что язык логики предикатов первого порядка задает только полиномиально распознаваемые на детерминированных машинах Тьюринга запросы, но не является полным PTIME. Строятся полные для PTIME и NPTIME языки запросов при условии, что базы данных упорядочены. Во второй главе приводится пример Гуревича, показывающий, что использование линейного порядка существенно увеличивает выразительные возможности языка логики предикатов, даже для случая генерических (сохраняющихся при перестановках универсума) запросов
