Використання досконалої диз’юнктивної нормальної форми (ДДНФ) для створення умови предикату WHERE

Зазвичай умови, які потрібно вказати в предикаті запиту на вибірку, інтуїтивно зрозумілі та не потребують складних обчислень.

Але іноді нашої інтуїції недостатньо, і нам доводиться звертатися до булевої алгебри. Розглянемо цей випадок.

Отже, потрібно вибрати тури, які повністю або частково потрапляють у заданий діапазон дат.

Ми застосуємо ДДНФ. Теоретичне обґрунтування та докази ви можете прочитати в статтях на цю тему, але я одразу перейду до суті.

Введемо такі позначення:

t1 — початок діапазону

t2 — завершення діапазону

start — початок туру

finish — завершення туру

Давайте визначимо логічні змінні, які будуть використовуватися під час створення умови:

a = t1 >= start

b = t1 >= finish

c = t2 >= start

d = t2 >= finish

Тепер, лише для тих варіантів, які слід включити до запиту, ми запишемо кон’юнкції з наших змінних:

Лінія над змінною означає НЕ, і між змінними передбачається знак логічного множення (кон’юнкції).

Тепер ми можемо записати ДДНФ:

Плюс означає логічне додавання (диз’юнкцію).

Ми отримали запис логічної функції, яка має бути реалізована у предикаті WHERE. Тепер ми можемо записати умову, але вона громіздка. Давайте використаємо булеву алгебру, дуже схожу на шкільну алгебру.

Перша дія з першими двома членами:

Сподіваюся, ви розумієте, що вираз у дужках є істинним для будь-якого a, і тому не впливає на результат кон’юнкції.

Друга дія з двома останніми членами:

Ми закінчуємо:

Згідно з принципом дуальності в булевій алгебрі,

b͞ = t1 <= finish (note: not t1 < finish )

Отже, ми можемо записати предикат WHERE:

WHERE (t1 <= tours.finish ) AND (t2 >= tours.start)

Приклад запиту:

SELECT * FROM tours WHERE (t1 <= tours.finish ) AND (t2 >= tours.start)

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті