Построение дерева из строк базы данных

Question

Мне нужно построить дерево из строк базы данных. Чтобы быть более конкретным, у меня есть таблица, в которой содержится план счетов.

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

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

Я считаю, что эта проблема довольно общая, поэтому я предполагаю, что для нее уже может быть библиотека haskell.

Может ли кто-нибудь помочь?

Answer 1

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

В настоящее время ваш вопрос очень расплывчатый, и все, на что я могу ответить, вам нужно использовать структуру, похожую на Data.Map, чтобы сначала скопировать промежуточные результаты и переупорядочить их после запроса этой промежуточной структуры данных. Как показывает документация, сложность большинства его функций доступа составляет O(log n), что очень эффективно.

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

Answer 2

Как сказал Никита, в чем проблема?

Вы не обеспечиваете любой тип данных, дерево классификацию ключа, ...

Во всяком случае, этот код может помочь думать о вашей проблеме ...

data Tree a = Node a [Tree a] deriving Show 

db = [(0, 1) 
    ,(1, 2) 
    ,(1, 3) 
    ,(2, 4) 
    ,(2, 6) 
    ,(3, 5) 
    ] 

rootTree = Node 0 [] 

insert parent child (Node key childs) = 
    Node key $ if key == parent then Node child []:childs 
           else map (insert parent child) childs 

insertFromDB rows = foldl insertRow rootTree rows 
    where insertRow tree (parent, child) = insert parent child tree 

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

calculateDeepLevel db = compute 0 roots 
    where roots = filter (not.flip elem snds) fsts 
     fsts = nub $ map fst db 
     snds = map snd db 
     compute level parents = map (\n -> (n, level)) parents ++ 
           concatMap (addChilds (level + 1)) parents 
     addChilds level node = compute level $ map snd $ filter ((node==).fst) db 

с calculateDeepLevel вы можете кал запрограммировать упорядоченную версию db и 0 на основе неупорядоченной и без корневой (без 0 узла) версии db.

Answer 3

Первые часть импорта,

import qualified Data.Map as M 
import qualified Data.Tree as T 
import Data.List (foldl') 
import Control.Arrow ((&&&)) 
import Data.Maybe (fromMaybe) 

Далее, давайте предположим, что мы есть записи, которые имеют идентификатор и необязательный родительский идентификатор (корневые узлы не имеют родителя), и несут какую-то ценность:

data Rec a = Rec { recId  :: Int 
       , recParentId :: Maybe Int 
       , recValue :: a 
       } 

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

toTree :: [Rec a] -> [T.Tree a] 
toTree rs = ts where 

Во-первых, давайте создадим карту от дополнительного родительского идентификатора в списке записей, которые имеют что родительский ID:

-- gs :: M.Map (Maybe Int) [Rec a] 
    gs = foldl' f M.empty rs where 
     f m r = M.insertWith (const (r:)) (recParentId r) [r] m 

Далее, давайте развернуть дерево, начиная с фиктивным корневого узла, сыны которые будут корни деревьев, мы заинтересованы в Обратите внимание, что фиктивная корневой узел не имеет значения, поэтому мы используем undefined:.

-- t :: T.Tree a 
    t = T.unfoldTree mkNode (undefined, Nothing) 

mkNode функции передается значение и идентификатор узла мы хотим строить. Она возвращает значение, и список пар значение ребенка/Ид с помощью Map мы строили раньше:

-- mkNode :: (a, Maybe Int) -> (a, [(a, Maybe Int)]) 
    mkNode (a, i) = (a, map (recValue &&& Just . recId) 
          . fromMaybe [] 
          . M.lookup i $ gs) 

Наконец, мы можем отбросить фиктивный корневой узел, и вернуть его непосредственные дети, как корни деревьев мы заинтересованы в:

ts = T.subForest t 

А вот тест:

main = mapM_ (putStrLn . T.drawTree) 
     $ toTree [ Rec 0 Nothing "rootA" 
        , Rec 1 (Just 0) "rootA.childA" 
        , Rec 2 (Just 0) "rootA.childB" 
        , Rec 3 (Just 1) "rootA.childA.childA" 
        , Rec 4 (Just 1) "rootA.childA.childB" 
        , Rec 5 (Just 2) "rootA.childB.childA" 
        , Rec 6 (Just 2) "rootA.childB.childB" 
        , Rec 7 Nothing "rootB" 
        , Rec 8 (Just 7) "rootB.childA" 
        , Rec 9 (Just 7) "rootB.childB" 
        , Rec 10 (Just 8) "rootB.childA.childA" 
        , Rec 11 (Just 8) "rootB.childA.childB" 
        , Rec 12 (Just 9) "rootB.childB.childA" 
        , Rec 13 (Just 9) "rootB.childB.childB" 
        ] 

, который генерирует:

rootB 
| 
+- rootB.childB 
| | 
| +- rootB.childB.childB 
| | 
| `- rootB.childB.childA 
| 
`- rootB.childA 
    | 
    +- rootB.childA.childB 
    | 
    `- rootB.childA.childA 

rootA 
| 
+- rootA.childB 
| | 
| +- rootA.childB.childB 
| | 
| `- rootA.childB.childA 
| 
`- rootA.childA 
    | 
    +- rootA.childA.childB 
    | 
    `- rootA.childA.childA