Skip to content

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

Jump to bottom
Andrei Malykh edited this page Nov 15, 2024 · 49 revisions

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

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

Neo4j

Описание

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 байтов)

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

{
  "identity": 13,
  "labels": [
    "User"
  ],
  "properties": {
    "password": "12345678",
    "name": "Иван Рур",
    "created_at": "2024-10-30T18:46:51.927000000Z",
    "email": "[email protected]"
  },
  "elementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:13"
}

Route

{
  "identity": 16,
  "labels": [
    "Route"
  ],
  "properties": {
    "durarion": 130,
    "length": 13.5,
    "name": "По следам Пушкина",
    "created_at": "2024-10-30T18:59:28.346000000Z",
    "description": "Лучший маршрут, связанный с Пушкиным"
  },
  "elementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:16"
}

PointOfInterest

{
  "identity": 17,
  "labels": [
    "PointOfInterest"
  ],
  "properties": {
    "name": "Петропавловская крепость",
    "created_at": "2024-10-30T19:09:06.678000000Z",
    "description": "Первая крепость города",
    "location": "point({srid:4326, x:56.21, y:13.43})"
  },
  "elementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:17"
}

Image

{
  "identity": 18,
  "labels": [
    "Image"
  ],
  "properties": {
    "name": "default image",
    "uri": "[https://uri_1](https://uri_1/)"
  },
  "elementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:18"
}

Walk

{
  "identity": 19,
  "labels": [
    "Walk"
  ],
  "properties": {
    "length": 0.3,
    "end_time": "2024-10-30T19:21:47.217000000Z",
    "start_date": "2024-10-30T00:00:00Z"
  },
  "elementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:19"
}

Dot

{
  "identity": 20,
  "labels": [
    "Dot"
  ],
  "properties": {
    "location": "point({srid:4326, x:-34.2, y:32.43})",
    "time": "2024-10-30T19:26:11.220000000Z"
  },
  "elementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:20"
}

Walk-CREATED_BY->User

{
  "identity": 7,
  "start": 19,
  "end": 13,
  "type": "CREATED_BY",
  "properties": {

  },
  "elementId": "5:8029c3ee-3cb0-4f9f-9549-21a0282727a1:7",
  "startNodeElementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:19",
  "endNodeElementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:13"
}

Intersection

{
  "identity": 21,
  "labels": [
    "Intersection"
  ],
  "properties": {
    "location": "point({srid:4326, x:-34.2, y:32.43})",
    "street_count": 4
  },
  "elementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:21"
}

Intersection-ROAD_SEGMENT->Intersection

{
  "identity": 8,
  "start": 21,
  "end": 22,
  "type": "ROAD_SEGMENT",
  "properties": {
    "length": 0.2
  },
  "elementId": "5:8029c3ee-3cb0-4f9f-9549-21a0282727a1:8",
  "startNodeElementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:21",
  "endNodeElementId": "4:8029c3ee-3cb0-4f9f-9549-21a0282727a1:22"
}

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

Регистрация

MATCH (u: User) WHERE u.email="[email protected]"
CREATE (u: User {
	email: '[email protected]', 
	name: 'Иван Рур',
	password: '12345678', 
	created_at: datetime()
})

Итого: 1 запрос для проверки существует ли пользователь с таким email; 1 запрос для создания пользователя

Затрагивается только одна коллекция

Вход

MATCH (u: User) WHERE u.email="[email protected]" AND u.password="12345678"

Итого: 1 запрос.

Затрагивается только одна коллекция.

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

MATCH (source:Intersection)  
WHERE ID(source) = 45 
MATCH (dest:Intersection)  
WHERE ID(dest) = 14  
CALL apoc.algo.aStarConfig(source, dest, "ROAD_SEGMENT",  
{pointPropName: "location", weight: "length"})  
YIELD weight, path  
RETURN *

Итого: 3 запроса Затронуты две коллекции

Поиск Точек

MATCH (p: PointOfInterest) WHERE n.name =~ '(?i).*Петропавлав.*' RETURN p;

Итого: 1 запрос.

Затрагивается только одна коллекция.

Расчет длины маршрута

CALL () {
	MATCH 
	(r:Route WHERE ID(r)=8)-[inc1: INCLUDE]->
	(: PointOfInterest)-[:CLOSE_TO_THE]->(i1: Intersection),
	(r:Route WHERE ID(r)=8)-[inc2: INCLUDE{order: inc1.order + 1}]->
	(: PointOfInterest)-[:CLOSE_TO_THE]->(i2: Intersection)
	RETURN i1, i2
	ORDER BY inc1.order
}
CALL apoc.algo.aStarConfig(i1, i2, "ROAD_SEGMENT", {pointPropName: "location", weight: "length"})  
YIELD weight
RETURN SUM(weight) as total_distance

Итого: 2 запроса.

Затрагивается 6 коллекций.

Обновление длины маршрута

MATCH (route: Route WHERE ID(route)=8)
CALL () {
	MATCH 
	(route)-[inc1: INCLUDE]->
	(: PointOfInterest)-[:CLOSE_TO_THE]->(i1: Intersection),
	(route)-[inc2: INCLUDE{order: inc1.order + 1}]->
	(: PointOfInterest)-[:CLOSE_TO_THE]->(i2: Intersection)
	RETURN i1, i2
	ORDER BY inc1.order
}
WITH route, i1, i2
CALL apoc.algo.aStarConfig(i1, i2, "ROAD_SEGMENT", {pointPropName: "location", weight: "length"})  
YIELD weight
WITH SUM(weight) as total_distance, route
SET route.length=total_distance
RETURN route

Итого: 3 запроса.

Затрагивается 5 коллекций.

Обновление длительности маршрута

MATCH (w: Walk)-[:ALONG_THE]->(r:Route WHERE ID(r)=8) WITH r,
CASE COUNT(w)
  WHEN >= 10 THEN AVG(w.duration)
  ELSE r.length / 78
END AS duration
SET r.duration = duration
RETURN r

Итого: 1 запрос.

Затрагивается 3 коллекции.

Расчет длины Walk

CALL () {
    MATCH (w :Walk WHERE ID(w)=87)-[:CONSISTS_OF]->(d :Dot), 
        (i: Intersection WHERE point.distance(i.location, d.location) < 10000000)
    WITH d, i ORDER BY point.distance(i.location, d.location)
    RETURN d, collect(i)[0] AS nearest_i
    ORDER BY d.time
}
WITH collect(DISTINCT nearest_i)[0..-1] AS i1, collect(DISTINCT nearest_i)[1..] AS i2
UNWIND i1 AS s
UNWIND i2 AS d
CALL apoc.algo.aStarConfig(s, d, "ROAD_SEGMENT", {pointPropName: "location", weight: "length"})
YIELD weight
RETURN SUM(weight) AS length

Итого: 2 запроса.

Затрагивается 5 коллекций.

Обновление длины Walk

CALL () {
    MATCH (w :Walk WHERE ID(w)=87)-[:CONSISTS_OF]->(d :Dot), 
        (i: Intersection WHERE point.distance(i.location, d.location) < 10000000)
    WITH w, d, i ORDER BY point.distance(i.location, d.location)
    RETURN w, d, collect(i)[0] AS nearest_i
    ORDER BY d.time
}
WITH collect(DISTINCT nearest_i)[0..-1] AS i1, collect(DISTINCT nearest_i)[1..] AS i2, w
UNWIND i1 AS s
UNWIND i2 AS d
CALL apoc.algo.aStarConfig(s, d, "ROAD_SEGMENT", {pointPropName: "location", weight: "length"})
YIELD weight
WITH SUM(weight) AS total_distance, w
SET w.length = total_distance
RETURN w

Итого: 2 запроса.

Затрагивается 5 коллекций.

Расчет длительности прогулки

MATCH (n :Walk WHERE ID(n) = 87)-[:CONSISTS_OF]->(d: Dot)
WITH min(d.time) as start_time, max(d.time) as finish_time
RETURN duration.inSeconds(start_time, finish_time).minutes

Итого: 1 запрос.

Затрагивается 3 коллекции.

Обновление длительности прогулки

MATCH (n :Walk WHERE ID(n) = 87)-[:CONSISTS_OF]->(d: Dot)
WITH min(d.time) as start_time, max(d.time) as end_time, n
SET n.start_time=start_time, 
    n.end_time=end_time 
RETURN n

Итого: 1 запрос.

Затрагивается 3 коллекции.

20 самых быстрых пользователей (Прогулки больше часа)

MATCH (user :User)-[:CREATED_BY]-(w :Walk)
WHERE duration.inSeconds(w.start_time, w.end_time).hours > 1
RETURN user, SUM(w.length) / SUM(duration.inSeconds(w.start_time, w.end_time).seconds) AS speed
ORDER BY speed DESC
LIMIT 20

Итого: 1 запрос.

Затрагивается 3 коллекции.

100 самых популярных intersection за последний месяц

MATCH (d: Dot WHERE duration.between(d.time, Datetime()).months <= 1), 
      (i :Intersection WHERE point.distance(d.location, i.location) < 50) 
RETURN i, COUNT(d) as popularity
ORDER BY popularity DESC 
LIMIT 100

Итого: 1 запрос.

Затрагивается 2 коллекции.

100 самых популярных road_segment за последний месяц

MATCH (d: Dot WHERE duration.between(d.time, Datetime()).months <= 1), 
    (i1 :Intersection WHERE point.distance(d.location, i1.location) < 50)
    -[r :ROAD_SEGMENT]-
    (i2 :Intersection WHERE point.distance(d.location, i2.location) < 50) 
RETURN r, COUNT(d) as popularity 
ORDER BY popularity DESC 
LIMIT 100

Итого: 1 запрос.

Затрагивается 2 коллекции.

Построение маршрута между двумя произвольными точками

CALL () {
    WITH point({latitude: 51.3451242, longitude: 11.4355232}) AS source
    MATCH (source_i: Intersection WHERE point.distance(source_i.location, source) < 10000)
    RETURN source_i
    ORDER BY point.distance(source_i.location, source)  
    LIMIT 1
}
CALL () {
    WITH point({latitude: 52.3145351, longitude: 13.4341564}) AS dest
    MATCH(dest_i: Intersection WHERE point.distance(dest_i.location, dest) < 10000)
    RETURN dest_i 
    ORDER BY point.distance(dest_i.location, dest) 
    LIMIT 1
}
CALL apoc.algo.aStarConfig(source_i, dest_i, "ROAD_SEGMENT", {pointPropName: "location", weight: "length"})  
YIELD path
RETURN path

Итого: 3 запроса.

Затрагивается 2 коллекции.

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

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

SQL

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

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);

Итого: 2 запроса.

Затронута 1 коллекция

Вход

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

Итого: 1 запрос.

Затронута 1 коллекция

Поиск Точек

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

Итого: 1 запрос.

Затронута 1 коллекция

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

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)

Итого: 3 запроса.

Затронуто 3 коллекции

Расчет длины маршрута

WITH RouteInPoints AS (
  SELECT intersection_id, position
  FROM RoutePoint
  JOIN PointOfInterest ON PointOfInterest.point_id = RoutePoint.point_id
  WHERE route_id = 1
)
SELECT SUM(cost) AS total_distance
FROM (
    SELECT astar_result.cost,
    FROM RouteInPoints rp1
    JOIN 
    RouteInPoints rp2 ON rp1.position + 1 = rp2.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
  ', rp1.intersection_id, rp2.intersection_id, false, false) AS astar_result;
) AS distance;

Итого: 3 запроса.

Затронуты 3 коллекции

Обновление длины маршрута

UPDATE Route
SET length = (
    WITH RouteInPoints AS (
        SELECT intersection_id, position
        FROM RoutePoint
        JOIN PointOfInterest ON PointOfInterest.point_id = RoutePoint.point_id
        WHERE route_id = 1
    )
    SELECT SUM(cost) AS total_distance
    FROM (
        SELECT astar_result.cost,
        FROM RouteInPoints rp1
        JOIN
        RouteInPoints rp2 ON rp1.position + 1 = rp2.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',
                rp1.intersection_id, rp2.intersection_id, false, false
        ) AS astar_result
    ) AS distance
)
WHERE route_id = 1;

Итого: 4 запроса.

Затронуты 4 коллекции

Обновление длительности маршрута

CASE WHEN (SELECT COUNT(*) FROM Walk WHERE route_id = 1) > 10 THEN
  UPDATE Route SET
    duration =
    (
      SELECT ROUND(AVG(EXTRACT(EPOCH FROM (end_time - start_time)) / 60 / (Walk.length / Route.length)))
      FROM Walk
      JOIN Route ON Walk.route_id = Route.route_id
      WHERE route_id = 1
    )
  WHERE route_id = 1
ELSE
  UPDATE Route SET
    duration = length / 78
    -- 78 меторв в минуту
  WHERE route_id = 1
END

Итого: 3 запроса.

Затронуты 2 коллекции

Обновление длины Walk

Update Walk SET
length = 
(
  WITH ordered_dots AS (
    SELECT dot_id, location, time,
      LAG(location) OVER (PARTITION BY walk_id ORDER BY time) AS prev_location
    FROM Dot
    WHERE walk_id = 1
  )
  SELECT SUM(location <@> prev_location)
  FROM ordered_dots
  WHERE prev_location IS NOT NULL
)
WHERE walk_id = 1;

Итого: 3 запроса.

Затронуты 2 коллекции

Обновление длительности прогулки

-- SELECT EXTRACT(EPOCH FROM (MAX(time) - MIN(time))) / 60 AS duration_in_minutes
-- FROM Dot
-- WHERE walk_id = 1;
UPDATE Walk SET
  start_time = (SELECT MIN(time) FROM Dot WHERE walk_id = 1),
  end_time = (SELECT MAX(time) FROM Dot WHERE walk_id = 1)
WHERE walk_id = 1;

Итого: 3 запроса.

Затронуты 2 коллекции

20 самых быстрых пользователей (Прогулки больше часа)

SELECT user_id, SUM(Walk.length) / SUM(Walk.duration) AS speed
FROM User
JOIN Walk ON User.user_id = Walk.user_id
GROUP BY user_id
HAVING SUM(Walk.duration) > 60
ORDER BY speed DESC;

Итого: 1 запрос.

Затронуты 2 коллекции

100 самых популярных intersection за последний месяц

SELECT i.intersection_id, SUM(151 - d.location <@> i.location) AS popularity
FROM Intersection i
JOIN Dot d ON d.location <@> i.location < 150 AND d.time > NOW() - INTERVAL '1 month'
GROUP BY i.intersection_id
ORDER BY popularity DESC
LIMIT 100;

Итого: 1 запроса.

Затронуты 2 коллекции

100 самых популярных road_segment за последний месяц

SELECT rs.roadseg_id, SUM(151 - d.location <@> i1.location) + SUM(151 - d.location <@> i1.location) AS popularity
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
JOIN Dot d ON (d.location <@> i1.location < 150 OR d.location <@> i2.location < 150) AND d.time > NOW() - INTERVAL '1 month'
GROUP BY rs.roadseg_id
ORDER BY popularity DESC
LIMIT 100;

Итого: 1 запрос.

Затронуты 3 коллекции

Построение маршрута между двумя произвольными точками

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
',
(
  SELECT intersection_id
  FROM Intersection
  ORDER BY location <@> sta_point
  LIMIT 1;
)
,
(
  SELECT intersection_id
  FROM Intersection
  ORDER BY location <@> end_point
  LIMIT 1;
)
, false, false);

Итого: 3 запроса.

Затронуты 2 коллекции

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

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

Реляционная модель демонстрирует больший удельный объём информации. При этом нереляционная модель имеет меньшую избыточность информации.

Сравнение веса по моделям:

Описываемый объект Neo4j SQL
User 175 байт 171 байт
Route 1388 байт 1392 байта
PointOfInterest 1372 байта 1400 байт
Walk 24 байта 36 байт
Dot 28 байт 32 байта
Intersection 24 байта 28 байт
Image 104 байта 105 байт
Избыточность 1.063 1.159

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

Use Case Neo4j SQL
Регистрация 2 операции, 1 коллекция 2 операции, 1 коллекция
Вход 1 операция, 1 коллекция 1 операция, 1 коллекция
Поиск Точек 1 операция, 1 коллекция 1 операция, 1 коллекция
Поиск кратчайшего пути между точками 3 операции, 2 коллекции 3 операции, 3 коллекции
Расчет длины маршрута 2 операции, 6 коллекций 3 операции, 3 коллекции
Обновление длины маршрута 3 операции, 5 коллекций 4 операции, 4 коллекции
Обновление длительности маршрута 1 операция, 3 коллекции 3 операции, 2 коллекции
Обновление длины Walk 2 операции, 5 коллекций 3 операции, 2 коллекции
Обновление длительности прогулки 1 операция, 3 коллекции 3 операции, 2 коллекции
20 самых быстрых пользователей 1 операция, 3 коллекции 1 операция, 2 коллекции
100 самых популярных intersection 1 операция, 2 коллекции 1 операция, 2 коллекции
100 самых популярных RoadSegment 1 операция, 2 коллекции 1 операция, 3 коллекции
Построение маршрута между двумя произвольными точками 3 операции, 2 коллекции 3 операции, 2 коллекции

Нереляционная модель требует в среднем меньшее количество операций, чем реляционная модель, но запросы затрагивают большее количество коллекций из-за использования связей между узлами.

Вывод

В отличие от реляционной, нереляционная модель данных лучше масштабируется. Модели данных с множественными связями (например, Route и PointOfInterest) удобнее и эффективнее моделировать при помощи графов и базирующихся на них базах данных, таких как, например, neo4j. Реляционная модель лучше справляется с линейными структурами и стандартными операциями, такими как фильтрация данных и операции с большими таблицами, но может быть менее удобна для сложных связей между сущностями. Выбор между SQL и noSQL базами данных зависит от особенностей данных и задач.

Clone this wiki locally