Как предотвратить глубоко рекурсивные запросы с сущностями, состоящими из сущностей одного типа?[Прикольный пример внутри] - PullRequest
2 голосов
/ 19 августа 2010

Не беспокойся! Это выглядит сложнее, чем есть на самом деле! Просто приступай к напиткам!

TLDR-версия : Как эффективно запрашивать и обновлять сущности, имеющие отношения к другим сущностям?

Вот интересный сценарий моделирования данных с двумя таблицами, который меня озадачил:

Entities { ID, Name, ScalarValue }

ComponentEntities { AggregateEntityID, ComponentEntityID, quantity }

AggregateEntityID и ComponentEntityID являются внешними ключами таблицы Entities.

Дайте мне уже кровавый пример

Drinks { ID, Name, Alcohol% }

DrinkIngredients { CocktailID, IngredientID, amount }

Drinks { 1, "Vodka", 40% }
Drinks { 2, "Tomato juice", 0% }
Drinks { 3, "Tabasco", 0% }
Drinks { 4, "Bloody mary", - }

DrinkIngredients { 4, 1, 0.2 } // Bloody mary has 0.2*Vodka
DrinkIngredients { 4, 2, 0.7 } // Bloody mary has 0.7*Tomato juice
DrinkIngredients { 4, 3, 0.1 } // Bloody mary has 0.1*Tabasco

Если бы мы хотели получить содержание алкоголя Кровавой Мэри, мы бы SELECT * FROM DrinkIngredients WHERE CocktailID == 4.

Довольно стандартно; ничего странного там нет. Лизе нравится делать ее немного слаще, добавляя к ней немного страсти:

Drinks { 6, "Passion", 13% }
Drinks { 7, "Bloody Mary Pink", - }

DrinkIngredients { 7, 4, 0.8 }  // Bloody Mary Pink has 0.8*Bloody Mary
DrinkIngredients { 7, 6, 0.2 }  // Bloody Mary Pink has 0.2*Passion

Мама Лизы пробовала их так долго, что она считает, что нашла окончательное сочетание между ними:

Drinks { 8, "Bloody Milf", - }
DrinkIngredients { 8, 4, 0.45 } // Bloody Milf has 0.45*Bloody Mary
DrinkIngredients { 8, 7, 0.55 } // Bloody Milf has 0.55*Bloody Mary Pink

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

Это похоже на направленный ациклический граф .

СУБД: Одним из способов «кэширования» данных было бы вычисление соответствующих данных и их сохранение в самой сущности (или, возможно, в другой таблице). В приведенном выше примере содержание алкоголя в Bloody Mary рассчитывается один раз, когда оно создается и сохраняется в его поле% алкоголя. В этом случае обновления становятся дорогими, потому что мы должны обновлять каждый напиток (вместе со всей иерархией зависимостей), состоящий из обновленного.

Вопросы

RDBMS: есть ли лучший способ получить значения для листьев (напитки, которые не состоят из других), чем получать «родительский» напиток, пока не будет достигнут листовой напиток?

У обоих, RDBMS и NoSQL, есть проблема с этим: так или иначе.

Итог: это даже практично и выполнимо?

Что мне нужно, так это контрацепция

alt text

Ответы [ 2 ]

3 голосов
/ 19 августа 2010

«RDBMS: есть ли лучший способ получить значения листьев (напитки, которые не состоят из других), чем получать« родительский »напиток, пока не будет достигнут листовой напиток?»

Не понимаю этого. Напитки, которые не состоят из других, не имеют ничего общего с рекурсией. Это просто, КРОМЕ или ГДЕ НЕ СУЩЕСТВУЕТ.

А для "перехода к конечным значениям" (с учетом родителя) неизбежно потребуется обход дерева, независимо от структуры данных (реляционной или иерархической), используемой для его моделирования, не так ли?

У обоих, RDBMS и NoSQL, есть проблема с этим: так или иначе.

СУБД на самом деле не имеет проблем с этим. Эта проблема уже была выявлена ​​несколько десятилетий назад (около 80-х годов) и была решена путем внесения поправок в реляционную алгебру с транзитивной операцией замыкания и ее обобщенной версией. SQL поддерживает это с помощью рекурсивных запросов, и, как сказал Фрэнк, по крайней мере все большие собаки так или иначе поддерживают рекурсивные запросы.

Итог: это даже практично и выполнимо? "

Написание рекурсивных запросов не совсем тривиально, если вы никогда не делали этого раньше. Это делает это "непрактичным"? Я бы не знал.

0 голосов
/ 19 августа 2010

Многие RDMS поддерживают рекурсивные запросы. См. Е. г. http://msdn.microsoft.com/en-us/library/ms186243.aspx.

...