标签: hierarchical-data

有没有人有一个有效的算法来检索一个mptt查询集的所有祖先？到目前为止我能想到的最好的是这样的:

def qs_ancestors(queryset):
    if isinstance(queryset, EmptyQuerySet):
        return queryset
    queryset_aggs = queryset.values_list('tree_id', 'level').annotate(max_lft=Max('lft'), min_rght=Min('rght'))
    new_queryset = queryset.none()
    for tree_id, level, max_lft, min_rght in queryset_aggs:
        ancestors = MyModel.objects.filter(
           tree_id=tree_id,
           level__lt=level, 
           lft__lte=max_lft,
           rght__gte=min_rght,
        )
        new_queryset = ancestors | new_queryset
    return new_queryset

这种方法存在两个问题:

1. 如果存在彼此不相邻的分支(即它确实不起作用),它将失败
2. 这是非常低效的,因为它最终number_of_trees*number_of_levels在最终查询中有条款,它可以非常快地变得非常大

我愿意在其他地方缓存祖先,但我想不出有效的方法.我考虑添加一个字段,用逗号分隔的祖先id的列表,然后GROUP_CONCAT在一个额外的内部做一个(我在MySQL中),但我认为这可能会变得很大/很慢.

我有一个使用Closure Table方法保存分层数据的MySQL数据库.一个简单的示例数据库创建脚本遵循该问题.我目前的问题是如何以正确的顺序从数据库中提取数据？我目前正在使用以下select语句.

SELECT `TreeData`.`iD`, `TreeData`.`subsectionOf`,
       CONCAT(REPEAT('-', `TreePaths`.`len`),`TreeData`.`name`),
       `TreePaths`.`len`,`TreePaths`.`ancestor`,`TreePaths`.`descendant`
FROM `TreeData`
LEFT JOIN `TreePaths` ON `TreeData`.`iD` = `TreePaths`.`descendant`
WHERE `TreePaths`.`ancestor` = 1
ORDER BY `TreeData`.`subsectionOrder`

它会提取正确的信息,但输入顺序不正确.

示例数据库使用示例数据创建脚本.

-- Simple Sample
SET FOREIGN_KEY_CHECKS=0;
DROP TRIGGER IF EXISTS Tree_Insert;
DROP TRIGGER IF EXISTS Tree_Update;
DROP TABLE IF EXISTS TreePaths;
DROP TABLE IF EXISTS TreeData;
SET FOREIGN_KEY_CHECKS=1;


CREATE TABLE `TreeData` (
    `iD`              INT NOT NULL,             -- PK
    `subsectionOf`    INT,                      -- Parent ID & FK
    `subsectionOrder` INT,                      -- Oder of Subsections 
    `name`            NVARCHAR(500) NOT NULL, …

我有一个文件夹表，以id，parent_id关系与自身连接：

CREATE TABLE folders (
  id int(10) unsigned NOT NULL AUTO_INCREMENT,
  title nvarchar(255) NOT NULL,
  parent_id int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (id)
);

INSERT INTO folders(id, title, parent_id) VALUES(1, 'root', null);
INSERT INTO folders(id, title, parent_id) values(2, 'one', 1);
INSERT INTO folders(id, title, parent_id) values(3, 'target', 2);
INSERT INTO folders(id, title, parent_id) values(4, 'child one', 3);
INSERT INTO folders(id, title, parent_id) values(5, 'child two', 3);
INSERT INTO folders(id, title, parent_id) values(6, 'root 2', null);
INSERT …

现在,实体框架4中不支持包含HierarchyID的CLR UDT.HierarchyID.ToString()很有用,但是一旦任何项目有10个以上的兄弟姐妹就会崩溃(基本结构为/ 3/4/12 / 或/ 3/4/2 /所以第12个节点将在第2个节点之前排序).

关于潜在选择的更多信息:

• 将hierarchyID作为varbinary返回并实现我自己的二进制分类器

• 将hierarchyID作为varbinary返回并实现我自己的hierarchyID.ToString()方法,该方法在构建字符串时用零填充数字,以便生成的字符串是可排序的(即"/ 0003/ 0004/0012 /").我反汇编了Microsoft.SqlServer.Types.dll并查看了实现.看起来Interals基于一个名为"OrdTree"的类,我可以使用该类作为重新实现的基础.

• 为SQL编写我自己的CLR类型来处理二进制数据并构建自己的字符串(选项2的变体).虽然,附带部署令人头疼.

• 编写一个SQL udf来解析层次结构字符串并将其填充到数据库层.阵列处理/正则表达式的缺乏似乎是这里最大的问题.

• 按数据库层上的hierarchyID排序,并使用ROW_NUMBER()函数作为排序顺序的替代.

• 在.net层上编写一些辅助方法,重新解析hierarchyId.ToString()并生成可排序的字符串(即"/ 0003/ 0004/0012 /").

所以我的问题是有人解决了限制吗？你有没有使用上述任何一种策略？如果是这样,怎么样？

我有一张桌子:

Series
========
ID
SeriesName
ParentSeriesID

一个系列可以是"根"系列,(ParentSeriesID是0或null)或者它可以有一个父系列.一个系列也可以是几个级别,即它的父级有一个父级,它有一个父级等.

如何通过它的ID和所有后代系列来查询表格以获得系列？

到目前为止,我尝试过:

 SELECT child.*
 FROM Series parent JOIN Series child ON child.ParentSeriesID = parent.ID
 WHERE parent.ID = @ParentID

但这只返回第一级子节点,我想要父节点和所有"下游"节点.我不确定如何从这里进步.

我想请你帮我解决存储为闭包表的分层数据结构的问题.

我想用这个结构来存储我的网站菜单.一切正常,但问题是我不知道如何按自定义顺序对确切的子树进行排序.目前,树按照项目添加到数据库的顺序排序.

我的结构基于Bill Karwin关于Closure Tables 的文章以及其他一些帖子.

这是我的MySQL数据库结构,包含一些DEMO数据:

--
-- Table `category`
--

CREATE TABLE IF NOT EXISTS `category` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) COLLATE utf8_czech_ci NOT NULL,
  `active` tinyint(1) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;


INSERT INTO `category` (`id`, `name`, `active`) VALUES
(1, 'Cat 1', 1),
(2, 'Cat 2', 1),
(3, 'Cat  1.1', 1),
(4, 'Cat  1.1.1', 1),
(5, 'Cat 2.1', 1),
(6, 'Cat 1.2', 1),
(7, …

我有父表子关系的db表:

NodeId    NodeName    ParentId
------------------------------
1         Node1       0
2         Node2       0
3         Node3       1
4         Node4       1
5         Node5       3
6         Node6       5
7         Node7       2

这里parentId = 0表示它是根级节点.现在我想编写一个SQL查询,它将在父类别的所有级别返回子级.

例如,对于nodeId = 1,它应该返回3,4,5,6.

我正在使用MS SQL Server 2005

是否有一个工具可以与SQL Server一起使用,从分层数据模型生成树状图？

我正在使用大型地理层次结构,并希望将其可视化.

这是一个例子.

我有一个NodeHierarchy表,存储节点之间的层次关系.表中的每一行代表一个节点.除一个节点外,每个节点都有一个父节点 没有父节点的节点是层次结构的根节点.

以下是我创建表格的方法:

CREATE DATABASE HierarchyTest;
GO

USE HierarchyTest;
GO

CREATE TABLE NodeHierarchy (
  PK_NodeID INT NOT NULL
    CONSTRAINT PK_NodeHierarchy PRIMARY KEY,
  FK_ParentNodeID INT NULL
    CONSTRAINT FK_NodeHierarchy_NodeHierarchy FOREIGN KEY
      REFERENCES NodeHierarchy(PK_NodeID),
  Name NVARCHAR(255) NOT NULL
);

我有一个苏格兰城市和场地的例子.苏格兰是层次结构的根源.苏格兰的后裔是城市和场所.在这个家庭中,父母"包含"一个孩子,所以我们说例如"Barrowlands在格拉斯哥,格拉斯哥在苏格兰".

此语句使用eample数据填充NodeHierachy表:

INSERT INTO NodeHierarchy(PK_NodeID, FK_ParentNodeID, Name)
VALUES
  (1, NULL, N'Scotland'),
  (2, 1, N'Glasgow'),
  (3, 1, N'Edinburgh'),
  (4, 1, N'St Andrews'),
  (5, 2, N'The Barrowlands'),
  (6, 2, N'The Cathouse'),
  (7, 2, N'Carling Academy'),
  (8, 2, N'SECC'),
  (9, 2, N'King Tut''s …

我正在尝试在CouchDB中对文档进行建模以在我的系统中使用,这在概念上类似于博客.每篇博文都属于至少一个类别,每个类别可以有很多帖子.分类是分层的,这意味着如果一个专属于中CatB层次结构中的" CATA - > 中CatB "("中CatB在CATA)",它也属于CATA.

用户必须能够快速查找某个类别(及其所有子级)中的所有帖子.

解决方案1 post类型的每个文档都包含一个"category"数组,表示它在层次结构中的位置(参见2).

{
   "_id": "8e7a440862347a22f4a1b2ca7f000e83",
   "type": "post",
   "author": "dexter",
   "title": "Hello",
   "category":["OO","Programming","C++"]
}

解决方案2 post类型的每个文档都包含表示层次结构中路径的"category"字符串(参见4).

{
   "_id": "8e7a440862347a22f4a1b2ca7f000e83",
   "type": "post",
   "author": "dexter",
   "title": "Hello",
   "category": "OO/Programming/C++"
}

解决方案3 post类型的每个文档都包含其父类"category"id,表示其在层次结构中的路径(参见3).通过链接的"类别"文档类型构建分层类别结构.

{
   "_id": "8e7a440862347a22f4a1b2ca7f000e83",
   "type": "post",
   "author": "dexter",
   "title": "Hello",
   "category_id": "3"
}

{
   "_id": "1",
   "type": "category",
   "name": "OO"
}


{
   "_id": "2",
   "type": "category",
   "name": "Programming",
   "parent": "1"
}


{
   "_id": …

我试图遍历这个充满父 - >子关系的XML数据,并且需要一种构建树的方法.任何帮助将非常感激.此外,在这种情况下,为父 - >子关系设置属性或节点是否更好？

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<nodes>
    <node name="Car" child="Engine"/>
    <node name="Car" child="Wheel"/>
    <node name="Engine" child="Piston"/>
    <node name="Engine" child="Carb"/>
    <node name="Carb" child="Bolt"/>
    <node name="Spare Wheel"/>
    <node name="Bolt" child="Thread"/>
    <node name="Carb" child="Foat"/>
    <node name="Truck" child="Engine"/>
    <node name="Engine" child="Bolt"/>
    <node name="Wheel" child="Hubcap"/>
</nodes>

在Python脚本上,这就是我所拥有的.我的大脑是炒的,我无法理解逻辑？请帮忙

import xml.etree.ElementTree as ET
tree = ET.parse('rec.xml')
root = tree.getroot()
def find_node(data,search):
    #str = root.find('.//node[@child="1.2.1"]')
    for node in data.findall('.//node'):
        if node.attrib['name']==search:
            print('Child-->', node)

for nodes in root.findall('node'):
    parent = nodes.attrib.get('name')
    child = nodes.attrib.get('child')
    print (parent,'-->', …