Модель данных

Нереляционная модель

Графическое представление модели

Описание

User

name - название (String, до 50 байтов)
email - адрес электронной почты (String, до 129 байтов)
password - пароль (String - до 64 байтов)
created_at - Дата и время регистрации (Datetime - 8 байт)

Route

name - название (String, до 50 байтов)
description - описание (String, до 2000 байт)
length - длина в метрах (Float, 4 байта)
duration - продолжительность в минутах (Integer, 4 байта)
created_at - дата создания (Datetime, 8 байт)

PointOfInterest

name - название (String, до 50 байтов)
description - описание (String, до 2000 байт)

Walk

start_datetime - дата и время начала (Datetime, 8 байтов)
end_datetime - дата и время окончания (Datetime, 8 байтов)
length - длина в метрах (Float, 4 байта)

Dot

location - местоположение (Point, 16 байтов)
time - дата и время (Datetime, 8 байтов)

Intersection

street_count - количество улиц (Integer, 4 байта)
location - местоположение (Point, 16 байтов)

RoadSegment

length - длина сегмента в метрах (Float, 4 байта)

Image

name - название изображения (String, до 50 байтов)
uri - uri изображения (String, до 100 байтов)

Оценка объема информации, хранимой в модели

Возьмём средний объём текста в полях без чёткого объёма как 2/3 с округлением в верх от максимального. При расчетах подразумевается, что каждому узлу и связи нужен идентификатор типа Integer размером 4 байт.

User - 4 + 34 + 86 +43 + 8 = 175 байт на объект
Route - 4 + 34 + 1334 + 4 + 4 + 8 = 1388 байт на объект
PointOfInterest - 4 + 34 + 1334 = 1372 байт на объект
Walk - 4 + 8 + 8 + 4 = 24 байт на объект
Dot - 4 + 16 + 8 = 28 байт на объект
Intersection - 4 + 4 + 16 = 24 байт на объект
Image - 4 + 34 + 66 = 104 байт на объект

Также необходимо учесть связи между узлами:

User-CREATED->Route - 4 + 4 + 4 = 12 байт на объект
Walk-CREATED_BY->User - 4 + 4 + 4 = 12 байт на объект
Walk_ALONG_THE->Route - 4 + 4 + 4 = 12 байт на объект
Walk-CONSISTS_OF->Dot - 4 + 4 + 4 = 12 байт на объект
Route-INCLUDE->PointOfInterest - 4 + 4 + 4 + 4 (order: Integer 4 байт) = 16 байт на объект
PointOfInterest-CLOSE_TO_THE->Intersection - 4 + 4 + 4 = 12 байт на объект
PointOfInterest-DEPICTED_ON->Image - 4 + 4 + 4 = 12 байт на объект
Intersection-ROAD_SEGMENT->Intersection - 4 + 4 + 4 + 4 (length: Float 4 байт) = 16 байт на объект

В конечной формуле оценки будем отталкиваться от количества пользователей со следующими предположениями:

в среднем на человека приходится 15 маршрутов
в среднем маршрут состоит из 12 точек интереса
в среднем 30000 точек интереса
в среднем каждый пользовател прошёл 30 маршрутов
в среднем на точку интереса приходится 9 фотографий и 9 связей DEPICTED_ON
в среднем на отслеживание одной прогулки по маршруту требуется 35 точек отслеживания
для количества пересечений и сегментов дорог возьмём данные по Аптекарскому острову и умножим на 30 (1842 и 9978). Это в итоге 55260 пересечений и 299340 сегментов дорог

В итоге получаем следующую зависимость объема данных в байтах от количества пользователей:
x ⋅ (175 + 15 ⋅ (1388 + 12) + 15 ⋅ 12 ⋅ 12 + 30 ⋅ (12 + 12 + 24) + 30 ⋅ 35 ⋅ (28 + 12)) + 30000 ⋅ (1372 + 9 ⋅ (104 + 12)) + 55260 ⋅ 24 + 299340 ⋅ 16 =66775x + 78595680

Избыточность модели

Следующие данные можно отнести к избыточным:

Связь User-CREATED->Route - 12 байт
Walk-CREATED_BY->User - 12 байт
Walk_ALONG_THE->Route - 12 байт
Walk-CONSISTS_OF->Dot - 12 байт
Route-INCLUDE->PointOfInterest - 12 байт (все поля кроме order)
PointOfInterest-CLOSE_TO_THE->Intersection - 12 байт
PointOfInterest-DEPICTED_ON->Image - 12 байт
Intersection-ROAD_SEGMENT->Intersection - 12 байт (все поля кроме length)
Walk - 20 байт
Intersection - атрибут street_count - 4 бйта
RoadSegment - атрибут length - 4 байт

В итоге получаем излишки x⋅(15 ⋅ 12 + 15 ⋅ 12 ⋅ 12 + 30 ⋅ (12 + 12 + 20 + 12)) + 30000 ⋅ 9 ⋅ 12 + 55260 ⋅ 4 + 299340 ⋅ 4 = 4020x + 4658400

Объём чистых данных соответственно 66775x + 78835680 − 4020x - 4658400 = 62755x + 74177280

В итоге получаем следующее соотношение $\frac{V(x)}{V_{pure}(x)}$. При 1000 пользователей получается избыточность в ≈1.063

Направление роста модели при увеличении количества объектов каждой сущности

При добавлении пользователь не возникает дополнительных сущностей. Рост линейный (175 байт на объект)
При добавлении маршрута возникает связь CREATED с пользователем, связт INCLUDE с точками интереса (среднем это 12 связей). Рост линейный (1416 байт на объект)
При добавлении точки интереса необходимо добавить его фотографии и добавить связи DEPICTED_ON (В среднем это 9 фото). Также требуется сопоставить ближайший перекресток, т.е. добавить связь CLOSE_TO_THE. Рост линейный (1404 байт на объект)
При добавлении нового изображения к точке интереса также возникает одна связь DEPICTED_ON. Рост линейный (116 байт на объект)
При отслеживании нового маршрута возникает новые точки отслеживания. В среднем 35, также добавляются связи ALONG_THE, CONSISTS_OF, CREATED_BY. Рост линейный (1444 байт на объект)
При добавлении точки OSM необходимо добавить новые сегменты дорог. В среднем на одну точку приходится 5 сегментов. Рост линейный (104 байт на объект)

В итоги для модели наблюдается только линейный рост при увеличении количества объектов.

Реляционная модель

Графическое представление модели

Описание отношений

User

user_id - целочисленный идентификатор (serial, 4 байта)
name - название (varchar(50), до 50 байтов)
email - адрес электронной почты (varchar(129), до 129 байтов)
password - пароль (varchar(64) - до 64 байтов)
created_at - дата регистрации (date - 4 байта)

Route

route_id - целочисленный идентификатор (serial, 4 байта)
name - название (varchar(50), до 50 байтов)
user_id - целочисленный идентификатор создателя (integer, 4 байта)
description - описание (varchar(2000), до 2 кб)
point_num - количество точек интереса (intager, 4 байта)
length - длина в метрах (intager, 4 байта)
duration - продолжительность в минутах (intager, 4 байта)
created_at - дата создания (date, 4 байта)

PointOfInterest

point_id - целочисленный идентификатор (serial, 4 байта)
name - название (varchar(50), до 50 байтов)
location - местоположение (point, 16 байтов)
description - описание (varchar(1000), до 2 кб)
intersection_id - идентификатор OSM точки (bigint, 8 байтов)

Walk

walk_id - целочисленный идентификатор (serial, 4 байта)
user_id - идентификатор пользователя (integer, 4 байта)
route_id - идентификатор маршрута (integer, 4 байта)
start_datetime - дата и время начала (timestamp, 8 байтов)
end_datetime - дата и время окончания (timestamp, 8 байтов)
dot_count - количество точек отслеживания (integer, 4 байта)
length - длина в метрах (integer, 4 байта)

Dot

dot_id - целочисленный идентификатор (serial, 4 байта)
walk_id - идентификатор прогулки (integer, 4 байта)
location - местоположение (point, 16 байтов)
datetime - дата и время (timestamp, 8 байтов)

Intersection

intersection_id - целочисленный идентификатор точки OSM (bigint, 8 байтов)
street_count - количество улиц (integer, 4 байта)
location - местоположение (point, 16 байтов)

RoadSegment

roadseg_id - целочисленный идентификатор (serial, 4 байта)
from_intersection_id - идентификатор OSM начальной точки (bigint, 8 байтов)
in_intersection_id - идентификатор OSM конечной точки (bigint, 8 байтов)
length - длина сегмента в метрах (integer, 4 байта)

Image

image_id - целочисленный идентификатор (serial, 4 байта)
name - название изображения (varchar(50), до 50 байтов)
uri - uri изображения (varchar(50), до 100 байтов)

Оценка объема информации, хранимой в модели

Возьмём средний объём текста в полях без чёткого объёма как 2/3 с округлением в верх от максимального. Аналогичное сделано и при оценке для нереляционной модели.

User - $4+34+86+43+4=171$ байт на объект
Route - $4+34+4+1334+4+4+4+4=1392$ байт на объект
PointOfInterest - $4+34+16+1334+8+4=1400$ байт на объект
Walk - $4+4+4+8+8+4+4=36$ байт на объект
Dot - $4+4+16+8=32$ байт на объект
Intersection - $8+4+16=28$ байт на объект
RoadSegment - $4+8+8+4=24$ байт на объект
Image - $4+34+67=105$ байт на объект

Также связь между рядом отношений поражает другие отношения:

Route-PointOfInterest - $4+4+4=12$ байт на связь (третье поле - нумерация для установления порядка)
PointOfInterest-Image - $4+4=8$ байт на связь

В конечной формуле оценки будем отталкиваться от количества пользователей со следующими предположениями:

в среднем на человека приходится 15 маршрутов
в среднем маршрут состоит из 12 точек интереса
в среднем каждый клиент прошёл 30 маршрутов
в среднем на отслеживание одной прогулки по маршруту требуется 35 точек отслеживания
для количества пересечений и сегментов дорог возьмём данные по Аптекарскому острову и умножим на 25 (4519 и 20720). Это в итоге 112975 пересечений и 518000 сегментов дорог
точек интереса 30000
в среднем на точку интереса приходится 9 фотографий

В итоге получаем $$x\cdot(171 + 15 \cdot 1392+15 \cdot 12 \cdot 12+30 \cdot 36+30 \cdot 35 \cdot 32) + 112975 \cdot 28 + 518000 \cdot 24 + 30000 \cdot (1400+(105+8)\cdot9) = 57891x + 88105300$$

Избыточность модели

Следующие можно посчитать избыточностью:

Route - атрибут user_id, point_num, length, duration - 16 байт на объект
PointOfInterest - атрибут intersection_id - 8 байт на объект
Walk - атрибуты user_id, route_id, start_datetime, end_datetime, dot_count и length - 32 байт на объект
Dot - атрибут walk_id - 4 байта на объект
RoadSegment - атрибуты from_intersection, in_intersection, length - 20 байт
Intersection - атрибут street_count - 4 байта
Route-PointOfIntest - атрибуты route_id и point_id - 8 байт
PointOfIntest-Image полностью - 8 байт

В итоге получаем излишки $$x\cdot(15 \cdot 16+15 \cdot 12 \cdot 8+30 \cdot 32+30 \cdot 35 \cdot 4) + 112975 \cdot 4+ 518000 \cdot 20 + 30000 \cdot (8+8\cdot9) = 6840x+13211900$$

Объём чистых данных соответственно $$57891x + 88105300 - 6840x - 13211900 = 51051x + 74893400$$

В итоге получаем следующее соотношение $$\frac{V(x)}{V_{pure}(x)}$$. При 1000 пользователей получается избыточность в $\approx 1.159$

Направление роста модели при увеличении количества объектов каждой сущности

При добавлении пользователь не возникает дополнительных сущностей. Рост линейный (171 байт на объект)
При добавлении маршрута возникает новое количество связей между маршрутом и точкой интереса. В среднем это 12 связей. Рост линейный (1536 байт на объект)
При добавлении точки интереса необходимо добавить его фотографии и связать их с ним. В среднем это 9 фото. Рост линейный (2417 байт на объект)
При добавлении нового изображения к точке интереса также возникает одно дополнительная связь. Рост линейный (113 байт на объект)
При отслеживании нового маршрута возникает новые точки отслеживания. В среднем 35. Рост линейный (1156 байт на объект)
При добавлении точки OSM необходимо добавить новые сегменты дорог. В среднем на одну точку приходится 5 сегментов. Рост линейный (148 байт на объект)

В итоги для модели наблюдается только линейный рост при увеличении количества объектов.

Примеры данных

User

user_id	name	email	password	created_at
1	Иван Рур	[email protected]	12345678	2023-01-01
2	Саша Саша	[email protected]	87654321	2023-01-02

Route

route_id	name	user_id	description	point_num	length	duration	created_at
1	По следам Пушкина	1	Лучший маршрут связный с Пушкиным	2	2001	130	02.02.2023
2	Петроградка	2	Маршрут по Петроградском острову	2	1000	67	03.02.2023

PointOfInterest

point_id	name	location	description	intersection_id	created_at
1	Петропавловская крепость	point(x:30.3024903, y:59.9713101)	Первая крепость города	1234	01.01.2023
2	Памятник Пушкину	point(x:30.2924903, y:59.9113101)	Отлит из бронзы	2341	01.01.2023
3	Аврора	point(x:20.9924903, y:60.0013101)	Корабль революции	3412	01.01.2023
4	Место дуэли Пушкина	point(x:20.8124903, y:60.3413101)	Здесь стрелялся Пушкин	4123	01.01.2023

Route-PointOfInterest

route_id	point_id	position
1	2	1
1	4	2
2	1	1
2	3	2

Image

image_id	name	uri
1	img1	https://uri_1
2	img2	https://uri_2
3	img3	https://uri_3
4	img4	https://uri_4

PointOfInterest-Image

user_id	image_id
1	1
2	2
3	3
4	4

Walks

walk_id	user_id	route_id	start_datetime	end_datetime	dot_count	length
1	1	2	2023-01-01 00:00:00	2023-01-01 01:07:00	2	1002
2	2	1	2023-01-01 00:00:00	2023-01-01 02:10:00	2	2000

Dots

dot_id	walk_id	location	time
1	1	point(x:30.3024903, y:59.9713101)	2023-01-01 00:00:00
2	2	point(x:30.2924903, y:59.9113101)	2023-01-01 00:00:00
3	1	point(x:20.9924903, y:60.0013101)	2023-01-01 01:07:00
4	2	point(x:20.8124903, y:60.3413101)	2023-01-01 02:10:00

Intersection

intersection_id	street_count	location
1234	1	point(x:30.3024903, y:59.9713101)
2341	2	point(x:30.2924903, y:59.9113101)
3412	2	point(x:20.9924903, y:60.0013101)
4123	1	point(x:20.8124903, y:60.3413101)

RoadSegment

roadseg_id	from_intersection_id	in_intersection_id	length
1	1234	2341	345
2	2341	3412	354
3	3412	4123	376

Примеры запросов

Регистрация

SELECT * FROM User WHERE email = '[email protected]';
INSERT INTO User (email, name, password, created_at) 
VALUES ('[email protected]', 'Иван Рур', '12345678', CURRENT_DATE);

Вход

SELECT * FROM User 
WHERE email = '[email protected]' AND password = '12345678';

Поиск Точек

SELECT * FROM PointOfIntest
WHERE LOWER(name) ILIKE 'аврора' OR LOWER(description) ILIKE 'аврора';

Создание маршрута

INSERT INTO Route (name, user_id, description, point_num, length, duration, created_at)
VALUES ('Новый маршрут', 1, 'Описание нового маршрута', 10, 1000, 60, CURRENT_DATE)
RETURNING route_id;
INSERT INTO RoutePoint (route_id, point_id, position)
SELECT route_id, point_id, position
FROM UNNEST(ARRAY[(1, 1, 1), (1, 2, 2), (1, 3, 3), ...]) AS t(route_id, point_id, position);

Поиск кратчайшего пути между точками

pgr_astar('SELECT
        rs.roadseg_id AS source,
        rs.in_intersection_id AS target,
        rs.length AS cost,
        i1.location[0] AS x1,
        i1.location[1] AS y1,
        i2.location[0] AS x2,
        i2.location[1] AS y2
    FROM 
        RoadSegment rs
        JOIN Intersection i1 ON rs.from_intersection_id = i1.intersection_id
        JOIN Intersection i2 ON rs.in_intersection_id = i2.intersection_id
', start, end, false, false)

Выбор маршрута по фильтрам

SELECT * FROM Route 
WHERE
    (LOWER(name) ILIKE 'аврора' OR LOWER(description) ILIKE 'аврора') AND
    (length BETWEEN 1000 AND 10000) AND
    (duration BETWEEN 30 AND 3600) AND
    (created_at BETWEEN '2023-01-01' AND '2023-02-01') AND
    (user_id = 1) AND
    (point_num BETWEEN 2 AND 5) AND
    EXISTS (
        SELECT 1
        FROM RoutePointOfInterest rpoi
        WHERE rpoi.route_id = Route.id
        GROUP BY rpoi.route_id
        HAVING ARRAY[1, 3, 8] @> ARRAY_AGG(rpoi.point_id)
    )

Выбор пользователей по фильтрам

SELECT *
FROM User
WHERE user_id IN (
  SELECT user_id
  FROM Walks
  GROUP BY user_id
  HAVING
    COUNT(walk_id) BETWEEN 6 AND 9 AND
    SUM(end_datetime - start_datetime) BETWEEN INTERVAL '40 minutes' AND INTERVAL '120 minutes' AND
    SUM(length) BETWEEN 1000 AND 2000
) AND created_at BETWEEN '2023-01-01' AND '2023-02-01'

Модель данных

Нереляционная модель

Графическое представление модели

Описание

User

Route

PointOfInterest

Walk

Dot

Intersection

RoadSegment

Image

Оценка объема информации, хранимой в модели

Избыточность модели

Направление роста модели при увеличении количества объектов каждой сущности

Реляционная модель

Графическое представление модели

Описание отношений

User

Route

PointOfInterest

Walk

Dot

Intersection

RoadSegment

Image

Оценка объема информации, хранимой в модели

Избыточность модели

Направление роста модели при увеличении количества объектов каждой сущности

Примеры данных

User

Route

PointOfInterest

Route-PointOfInterest

Image

PointOfInterest-Image

Walks

Dots

Intersection

RoadSegment

Примеры запросов

Регистрация

Вход

Поиск Точек

Создание маршрута

Поиск кратчайшего пути между точками

Выбор маршрута по фильтрам

Выбор пользователей по фильтрам

Сравнение моделей

Удельный объем информации

Запросы по отдельным юзкейсам

Вывод

Clone this wiki locally