дерево - как выяснить, используя mysql, если потомки узла полны - PullRequest
Новая
       35

дерево - как выяснить, используя mysql, если потомки узла полны

0 голосов
/ 20 января 2012

Задавал похожий вопрос раньше, но никто не ответил, поэтому я переосмыслил проблему и задаю похожий / другой вопрос.

У меня есть процесс, который начинается с parent / root (top)приложение.Затем корневое приложение порождает дочерние приложения, которые также могут порождать приложения-потомки.Это может продолжаться для нескольких уровней.Каждый уровень может быть либо узлом, либо листом.Узел может иметь потомков.Лист не имеет порожденных дочерних / дочерних приложений.

В начале процесса приложение знает количество уровней.Процесс также структурирован таким образом, что каждое дочернее приложение может обновлять tbl после завершения, используя свой собственный идентификатор, а также parentID.

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

Я пытаюсь выяснить, как можно посмотреть на данный элемент / узел в дереве и определить, завершены ли приложения-потомки.

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

Ищу гуру mysql, чтобы помочь мне прояснить этот вопрос.

Спасибо! 

---------------------------------

The sample tree would look like:

spawn
3 levels
a - 3 copies of b
b - 3 copies of c


                     a(1)
                      |
---------------------------------------------------------------------
          |b(1)                   |b(2)                            |b(3)
-------------------         -------------------          --------------------  
|c(1)    |c(2)    |c(3)     c(1)    |c(2)   |c(3)        |c(1)    |c(2)    |c(3)  


so we have a total of 12 crawls/fetches

the levels
a
b
c

the (parent/child) levelRelationships
"",a
a,b
b,c

start level
a (parent/top)
end level
c (leaf)


operational process:

an app spawns either no child app, a single child app, or multiple child app(s)
an app that spawns children is a node
an app that spawns no children is a leaf
 there is no guarantee that an app at a given level, will stop operation 
 before an app at a lower level started by it's parent
each child app can set a tbl with a status when it completes 
 when each child app is complete, it generates a "level/complete" status
  which is stored in a levelStatusTBL

at the start of the root/top level process:
-the tree can have multiple/unknown levels
-each child app can spawn an unknown number of children


issue...
 how to algorithmically determine when all the descendants of a root/top level function have completed?
 how to algorithmically determine when all the descendants of a node have completed

Примеры таблиц, которые я рассматриваю: 

CREATE TABLE `crawlNodeChildrenCountTBL` (
  `rootID` varchar(100) NOT NULL DEFAULT '',
  `uCrawlID` varchar(100) NOT NULL DEFAULT '',
  `childCount` int(5) NOT NULL DEFAULT 0,
  `ID` int(10) NOT NULL AUTO_INCREMENT,
  PRIMARY KEY (`ID`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

CREATE TABLE `EdgeNodeCheckTBL` (
  `CollegeID` varchar(100) NOT NULL DEFAULT '',
  `rootID` varchar(100) NOT NULL DEFAULT '',
  `parentLevel` varchar(100) NOT NULL DEFAULT '',
  `Level` varchar(100) NOT NULL DEFAULT '',
  `nodeType` int(5) NOT NULL DEFAULT 0,     
  `masterParseInputUUID` varchar(100) NOT NULL DEFAULT '',
  `parentSetupPreComboID` varchar(100) NOT NULL DEFAULT '',
  `SetupPreComboChildStatusID` varchar(100) NOT NULL DEFAULT '',
  `ID` int(10) NOT NULL AUTO_INCREMENT,
  UNIQUE KEY `ID` (`ID`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;


EdgeNodeCheckTBL.SetupPreComboChildStatusID is the baseID
EdgeNodeCheckTBL.parentSetupPreComboID is the parentID of SetupPreComboChildStatusID

this is used to implement the standard child/parent relationship tbl

1 Ответ

0 голосов
/ 20 января 2012

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

Лучший способ хранить деревья в реляционной базе данных - это использовать модель вложенного множества . Идея состоит в том, что каждый узел имеет левый идентификатор и правый идентификатор, который представляет собой просто последовательность, когда каждый узел посещается с использованием обхода предварительного заказа. Левый идентификатор устанавливается при спуске дерева от верхнего узла; Правый идентификатор устанавливается при переходе вверх по дереву к верхнему узлу. Вы также должны обновить числа по мере изменения дерева.

Преимущество этой структуры в том, что вам не нужны рекурсивные запросы для проверки или обновления дерева. Он также рекомендует изолировать модификации дерева в одном месте, чтобы можно было корректно обновлять левый и правый идентификаторы.

В статье Википедии есть больше деталей.

...