Pull to refresh
88.13
lsFusion
Не очередной язык программирования

Функциональная СУБД

Reading time9 min
Views13K
Мир баз данных давно захвачен реляционными СУБД, в которых используется язык SQL. Настолько сильно, что появляющиеся разновидности называют NoSQL. Им удалось отбить себе определенное место на этом рынке, но реляционные СУБД умирать не собираются, и продолжают активно использоваться для своих целей.

В этой статье я хочу описать концепцию функциональной базы данных. Для лучшего понимания, я буду это делать путем сравнения с классической реляционной моделью. В качестве примеров будут использоваться задачи из различных тестов по SQL, найденные в интернете.

Введение


Реляционные базы данных оперируют таблицами и полями. В функциональной базе данных вместо них будут использоваться классы и функции соответственно. Поле в таблице с N ключами будет представлено как функция от N параметров. Вместо связей между таблицами будут использоваться функции, которые возвращают объекты класса, на который идет связь. Вместо JOIN будет использоваться композиция функций.

Прежде чем перейти непосредственно к задачам, опишу задание доменной логики. Для DDL я буду использовать синтаксис PostgreSQL. Для функциональной свой синтаксис.

Таблицы и поля


Простой объект Sku с полями наименование и цена:

Реляционная

CREATE TABLE Sku
(
    id bigint NOT NULL,
    name character varying(100),
    price numeric(10,5),
    CONSTRAINT id_pkey PRIMARY KEY (id)
)

Функциональная
CLASS Sku;
name = DATA STRING[100] (Sku);
price = DATA NUMERIC[10,5] (Sku);

Мы объявляем две функции, которые принимают на вход один параметр Sku, и возвращают примитивный тип.

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

Зададим цену для товара / магазина / поставщика. Она может изменяться со временем, поэтому добавим в таблицу поле время. Объявление таблиц для справочников в реляционной базе данных пропущу, чтобы сократить код:

Реляционная

CREATE TABLE prices
(
    skuId bigint NOT NULL,
    storeId bigint NOT NULL,
    supplierId bigint NOT NULL,
    dateTime timestamp without time zone,
    price numeric(10,5),
    CONSTRAINT prices_pkey PRIMARY KEY (skuId, storeId, supplierId)
)

Функциональная
CLASS Sku;
CLASS Store;
CLASS Supplier;
dateTime = DATA DATETIME (Sku, Store, Supplier);
price = DATA NUMERIC[10,5] (Sku, Store, Supplier);

Индексы


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

Реляционная

CREATE INDEX prices_date
    ON prices
    (skuId, storeId, supplierId, dateTime)

Функциональная
INDEX Sku sk, Store st, Supplier sp, dateTime(sk, st, sp);

Задачи


Начнем с относительно простых задач, взятых из соответствующей статьи на Хабре.

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

CLASS Department;
name = DATA STRING[100] (Department);

CLASS Employee;
department = DATA Department (Employee);
chief = DATA Employee (Employee);
name = DATA STRING[100] (Employee);
salary = DATA NUMERIC[14,2] (Employee);

Задача 1.1


Вывести список сотрудников, получающих заработную плату большую чем у непосредственного руководителя.

Реляционная

select a.*
from   employee a, employee b
where  b.id = a.chief_id
and    a.salary > b.salary

Функциональная
SELECT name(Employee a) WHERE salary(a) > salary(chief(a));

Задача 1.2


Вывести список сотрудников, получающих максимальную заработную плату в своем отделе

Реляционная

select a.*
from   employee a
where  a.salary = ( select max(salary) from employee b
                    where  b.department_id = a.department_id )

Функциональная
maxSalary 'Максимальная зарплата' (Department s) = 
    GROUP MAX salary(Employee e) IF department(e) = s;
SELECT name(Employee a) WHERE salary(a) = maxSalary(department(a));

// или если "заинлайнить"
SELECT name(Employee a) WHERE 
    salary(a) = maxSalary(GROUP MAX salary(Employee e) IF department(e) = department(a));

Обе реализации эквивалентны. Для первого случая в реляционной базе можно использовать CREATE VIEW, который таким же образом сначала посчитает для конкретного отдела максимальную зарплату в нем. В дальнейшем я для наглядности буду использовать первый случай, так как он лучше отражает решение.

Задача 1.3


Вывести список ID отделов, количество сотрудников в которых не превышает 3 человек.

Реляционная

select department_id
from   employee
group  by department_id
having count(*) <= 3

Функциональная
countEmployees 'Количество сотрудников' (Department d) = 
    GROUP SUM 1 IF department(Employee e) = d;
SELECT Department d WHERE countEmployees(d) <= 3;

Задача 1.4


Вывести список сотрудников, не имеющих назначенного руководителя, работающего в том-же отделе.

Реляционная

select a.*
from   employee a
left   join employee b on (b.id = a.chief_id and b.department_id = a.department_id)
where  b.id is null

Функциональная
SELECT name(Employee a) WHERE NOT (department(chief(a)) = department(a));

Задача 1.5


Найти список ID отделов с максимальной суммарной зарплатой сотрудников.

Реляционная

with sum_salary as
  ( select department_id, sum(salary) salary
    from   employee
    group  by department_id )
select department_id
from   sum_salary a       
where  a.salary = ( select max(salary) from sum_salary )

Функциональная
salarySum 'Максимальная зарплата' (Department d) = 
    GROUP SUM salary(Employee e) IF department(e) = d;
maxSalarySum 'Максимальная зарплата отделов' () = 
    GROUP MAX salarySum(Department d);
SELECT Department d WHERE salarySum(d) = maxSalarySum();


Перейдем к более сложным задачам из другой статьи. В ней есть подробный разбор того, как реализовывать эту задачу на MS SQL.

Задача 2.1


Какие продавцы продали в 1997 году более 30 штук товара №1?

Доменная логика (как и раньше на РСУБД пропускаем объявление):
CLASS Employee 'Продавец';
lastName 'Фамилия' = DATA STRING[100] (Employee);

CLASS Product 'Продукт';
id = DATA INTEGER (Product);
name = DATA STRING[100] (Product);

CLASS Order 'Заказ';
date = DATA DATE (Order);
employee = DATA Employee (Order);

CLASS Detail 'Строка заказа';

order = DATA Order (Detail);
product = DATA Product (Detail);
quantity = DATA NUMERIC[10,5] (Detail);

Реляционная

select LastName
from Employees as e
where (
  select sum(od.Quantity)
  from [Order Details] as od
  where od.ProductID = 1 and od.OrderID in (
    select o.OrderID
    from Orders as o
    where year(o.OrderDate) = 1997 and e.EmployeeID = o.EmployeeID)
) > 30

Функциональная
sold (Employee e, INTEGER productId, INTEGER year) = 
    GROUP SUM quantity(OrderDetail d) IF 
        employee(order(d)) = e AND 
        id(product(d)) = productId AND 
        extractYear(date(order(d))) = year;
SELECT lastName(Employee e) WHERE sold(e, 11997) > 30;

Задача 2.2


Для каждого покупателя (имя, фамилия) найти два товара (название), на которые покупатель потратил больше всего денег в 1997-м году.

Расширяем доменную логику из предыдущего примера:
CLASS Customer 'Клиент';
contactName 'ФИО' = DATA STRING[100] (Customer);

customer = DATA Customer (Order);

unitPrice = DATA NUMERIC[14,2] (Detail);
discount = DATA NUMERIC[6,2] (Detail);

Реляционная

SELECT ContactName, ProductName FROM (
SELECT c.ContactName, p.ProductName
, ROW_NUMBER() OVER (
    PARTITION BY c.ContactName
    ORDER BY SUM(od.Quantity * od.UnitPrice * (1 - od.Discount)) DESC
) AS RatingByAmt
FROM Customers c
JOIN Orders o ON o.CustomerID = c.CustomerID
JOIN [Order Details] od ON od.OrderID = o.OrderID
JOIN Products p ON p.ProductID = od.ProductID
WHERE YEAR(o.OrderDate) = 1997
GROUP BY c.ContactName, p.ProductName
) t
WHERE RatingByAmt < 3

Функциональная
sum (Detail d) = quantity(d) * unitPrice(d) * (1 - discount(d));
bought 'Купил' (Customer c, Product p, INTEGER y) = 
    GROUP SUM sum(Detail d) IF 
        customer(order(d)) = c AND 
        product(d) = p AND 
        extractYear(date(order(d))) = y;
rating 'Рейтинг' (Customer c, Product p, INTEGER y) = 
    PARTITION SUM 1 ORDER DESC bought(c, p, y), p BY c, y;
SELECT contactName(Customer c), name(Product p) WHERE rating(c, p, 1997) < 3;

Оператор PARTITION работает по следующему принципу: он суммирует выражение, указанное после SUM (здесь 1), внутри указанных групп (здесь Customer и Year, но может быть любое выражение), сортируя внутри групп по выражениям, указанным в ORDER (здесь bought, а если равны, то по внутреннему коду продукта).

Задача 2.3


Сколько товаров нужно заказать у поставщиков для выполнения текущих заказов.

Опять расширяем доменную логику:
CLASS Supplier 'Поставщик';
companyName = DATA STRING[100] (Supplier);

supplier = DATA Supplier (Product);

unitsInStock 'Остаток на складе' = DATA NUMERIC[10,3] (Product);
reorderLevel 'Норма продажи' = DATA NUMERIC[10,3] (Product);

Реляционная
select s.CompanyName, p.ProductName, sum(od.Quantity) + p.ReorderLevel — p.UnitsInStock as ToOrder
from Orders o
join [Order Details] od on o.OrderID = od.OrderID
join Products p on od.ProductID = p.ProductID
join Suppliers s on p.SupplierID = s.SupplierID
where o.ShippedDate is null
group by s.CompanyName, p.ProductName, p.UnitsInStock, p.ReorderLevel
having p.UnitsInStock < sum(od.Quantity) + p.ReorderLevel

Функциональная
orderedNotShipped 'Заказано, но не отгружено' (Product p) = 
    GROUP SUM quantity(OrderDetail d) IF product(d) = p;
toOrder 'К заказу' (Product p) = orderedNotShipped(p) + reorderLevel(p) - unitsInStock(p);
SELECT companyName(supplier(Product p)), name(p), toOrder(p) WHERE toOrder(p) > 0;

Задача со звездочкой


И последней пример лично от меня. Есть логика социальной сети. Люди могут дружить друг с другом и нравится друг другу. С точки зрения функциональной базы данных это будет выглядеть следующим образом:
CLASS Person;
likes = DATA BOOLEAN (Person, Person);
friends = DATA BOOLEAN (Person, Person);

Необходимо найти возможных кандидатов на дружбу. Более формализовано нужно найти всех людей A, B, C таких, что A дружит с B, а B дружит с C, A нравится C, но A не дружит с C.
С точки зрения функциональной базы данных запрос будет выглядеть следующим образом:
SELECT Person a, Person b, Person c WHERE 
    likes(a, c) AND NOT friends(a, c) AND 
    friends(a, b) AND friends(b, c);

Читателю предлагается самостоятельно решить эту задачу на SQL. Предполагается, что друзей гораздо меньше чем тех, кто нравится. Поэтому они лежат в отдельных таблицах. В случае успешного решения есть также задача с двумя звездочками. В ней дружба не симметрична. На функциональной базе данных это будет выглядеть так:
SELECT Person a, Person b, Person c WHERE 
    likes(a, c) AND NOT friends(a, c) AND 
    (friends(a, b) OR friends(b, a)) AND 
    (friends(b, c) OR friends(c, b));

UPD: решение задачи с первой и второй звездочкой от dss_kalika:
SELECT 
   pl.PersonAID
  ,pf.PersonAID
  ,pff.PersonAID
FROM Persons                 AS p
--Лайки                      
JOIN PersonRelationShip      AS pl ON pl.PersonAID = p.PersonID
                                  AND pl.Relation  = 'Like'
--Друзья                     
JOIN PersonRelationShip      AS pf ON pf.PersonAID = p.PersonID 
                                  AND pf.Relation = 'Friend'
--Друзья Друзей              
JOIN PersonRelationShip      AS pff ON pff.PersonAID = pf.PersonBID
                                   AND pff.PersonBID = pl.PersonBID
                                   AND pff.Relation = 'Friend'
--Ещё не дружат         
LEFT JOIN PersonRelationShip AS pnf ON pnf.PersonAID = p.PersonID
                                   AND pnf.PersonBID = pff.PersonBID
                                   AND pnf.Relation = 'Friend'
WHERE pnf.PersonAID IS NULL 

;WITH PersonRelationShipCollapsed AS (
  SELECT pl.PersonAID
        ,pl.PersonBID
        ,pl.Relation 
  FROM #PersonRelationShip      AS pl 
  
  UNION 

  SELECT pl.PersonBID AS PersonAID
        ,pl.PersonAID AS PersonBID
        ,pl.Relation
  FROM #PersonRelationShip      AS pl 
)
SELECT 
   pl.PersonAID
  ,pf.PersonBID
  ,pff.PersonBID
FROM #Persons                      AS p
--Лайки                      
JOIN PersonRelationShipCollapsed  AS pl ON pl.PersonAID = p.PersonID
                                 AND pl.Relation  = 'Like'                                  
--Друзья                          
JOIN PersonRelationShipCollapsed  AS pf ON pf.PersonAID = p.PersonID 
                                 AND pf.Relation = 'Friend'
--Друзья Друзей                   
JOIN PersonRelationShipCollapsed  AS pff ON pff.PersonAID = pf.PersonBID
                                 AND pff.PersonBID = pl.PersonBID
                                 AND pff.Relation = 'Friend'
--Ещё не дружат                   
LEFT JOIN PersonRelationShipCollapsed AS pnf ON pnf.PersonAID = p.PersonID
                                   AND pnf.PersonBID = pff.PersonBID
                                   AND pnf.Relation = 'Friend'
WHERE pnf.[PersonAID] IS NULL 


Заключение


Следует отметить, что приведенный синтаксис языка — это всего лишь один из вариантов реализации приведенной концепции. За основу был взят именно SQL, и целью было, чтобы он максимально был похож на него. Конечно, кому-то могут не понравится названия ключевых слов, регистры слов и прочее. Здесь главное — именно сама концепция. При желании можно сделать и C++, и Python подобный синтаксис.

Описанная концепция базы данных, на мой взгляд обладает следующими преимуществами:

  • Простота. Это относительно субъективный показатель, который не очевиден на простых случаях. Но если посмотреть более сложные случаи (например, задачи со звездочками), то, на мой взгляд, писать такие запросы значительно проще.
  • Инкапсуляция. В некоторых примерах я объявлял промежуточные функции (например, sold, bought и т.д.), от которых строились последующие функции. Это позволяет при необходимости изменять логику определенных функций без изменения логики зависящих от них. Например, можно сделать, чтобы продажи sold считались от совершенно других объектов, при этом остальная логика не изменится. Да, в РСУБД это можно реализовать при помощи CREATE VIEW. Но если всю логику писать таким образом, то она будет выглядеть не очень читабельной.
  • Отсутствие семантического разрыва. Такая база данных оперирует функциями и классами (вместо таблиц и полей). Точно также, как и в классическом программировании (если считать, что метод — это функция с первым параметром в виде класса, к которому он относится). Соответственно, «подружить» с универсальными языками программирования должно быть значительно проще. Кроме того, эта концепция позволяет реализовывать гораздо более сложные функции. Например, можно встраивать в базу данных операторы вида:
    CONSTRAINT sold(Employee e, 12019) > 100 IF name(e) = 'Петя' MESSAGE  'Что-то Петя продает слишком много одного товара в 2019 году';

  • Наследование и полиморфизм. В функциональной базе данных можно ввести множественное наследование через конструкции CLASS ClassP: Class1, Class2 и реализовать множественный полиморфизм. Как именно, возможно напишу в следующих статьях.

Несмотря на то, что это всего лишь концепция, у нас есть уже некоторая реализация на Java, которая транслирует всю функциональную логику в реляционную логику. Плюс к ней красиво прикручена логика представлений и много чего другого, благодаря чему получается целая платформа. По сути, мы используем РСУБД (пока только PostgreSQL) как «виртуальную машину». При такой трансляции иногда возникают проблемы, так как оптимизатор запросов РСУБД не знает определенной статистики, которую знает ФСУБД. В теории, можно реализовать систему управления базой данных, которая будет использовать в качестве хранилища некую структуру, адаптированную именно под функциональную логику.
Tags:
Hubs:
Total votes 26: ↑13 and ↓130
Comments278

Articles

Information

Website
lsfusion.org
Registered
Founded
Employees
51–100 employees
Location
Беларусь
Representative
NitroJunkie