Важная работа, выполненная Чандрой и Нарелом [231], а также Ульманом [1524], привела к признанию языка Datalog в качестве стандартного языка для дедуктивных баз данных. Кроме того, стал стандартным "восходящий" логический вывод, или прямой логический вывод, отчасти потому, что данный метод позволяет избежать проблем, обусловленных незавершаемыми и избыточными вычислениями, которые возникают при обратном логическом выводе, и отчасти потому, что имеет более естественную реализацию в терминах основных операций реляционной базы данных. Разработка метода магических множеств для перезаписи правил Бансильоном и др. [67] позволила воспользоваться в прямом логическом выводе преимуществами целенаправленности, свойственными обратному логическому выводу. Методы табулированного логического программирования (с. 1), вступившие в конкурентную борьбу с другими методами, заимствовали преимущества динамического программирования от прямого логического вывода.

Большой вклад в понимание сложностей логического вывода внесло сообщество пользователей дедуктивных баз данных. Чандра и Мерлин [232] впервые показали, что задача согласования единственного нерекурсивного правила (в терминологии баз данных — конъюнктивного запроса) может оказаться NP-трудной. Купер и Варди [870] предложили использовать понятие сложности данных (т.е. сложности как функции размера базы данных, в которой размер правила рассматривается как постоянный) в качестве подходящего критерия эффективности получения ответов на запросы. Готтлоб и др. [586] обсудили связь между конъюнктивными запросами и задачами удовлетворения ограничений, показав, как можно использовать способ декомпозиции гипердерева для оптимизации процесса согласования.