标签: transitive-closure-table

我有一个使用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, …

我在SQL Server数据库中使用了一组分层数据.数据以guid作为主键存储,而parentGuid作为指向直接父对象的外键存储.我最常通过WebApi项目中的Entity Framework访问数据.为了使情况更复杂,我还需要基于此层次结构管理权限,以便应用于父级的权限适用于其所有后代.我的问题是:

我已经搜遍了所有,无法决定哪种方法最适合处理这种情况.我知道我有以下选择.

1. 我可以创建Recursive CTEsCommon Table Expression(也就是RCTE)来处理分层数据.这似乎是正常访问最简单的方法,但我担心在用于确定子对象的权限级别时可能会很慢.
2. 我可以创建一个hierarchyId表中,并使用SQL Server所提供的功能,如数据类型字段GetAncestor(),IsDescendantOf()和等,这似乎将让查询很容易,但似乎需要一个相当复杂的插入/更新触发器,以保持HIERARCHYID域是正确的通过插入和移动
3. 我可以创建一个closure table,它将存储表中的所有关系.我想象如下:父列和子列,每个父 - >子关系将被表示.(即1-> 2 2-> 3将在数据库中表示为1-2,1-3,2-3).缺点是这需要插入,更新和删除触发器,即使它们非常简单,并且此方法会生成大量记录.

我已经尝试过全面搜索,但在这三种方法之间找不到任何建议.

PS我也对这个问题的任何替代解决方案持开放态度

我使用PostgreSQL 9.1来查询分层树结构数据,包括与节点连接的边(或元素).数据实际上是用于流网络,但我已经将问题抽象为简单的数据类型.考虑示例tree表.每条边都有长度和面积属性,用于确定网络中的一些有用指标.

CREATE TEMP TABLE tree (
  edge text PRIMARY KEY,
  from_node integer UNIQUE NOT NULL, -- can also act as PK
  to_node integer REFERENCES tree (from_node),
  mode character varying(5), -- redundant, but illustrative
  length numeric NOT NULL,
  area numeric NOT NULL,
  fwd_path text[], -- optional ordered sequence, useful for debugging
  fwd_search_depth integer,
  fwd_length numeric,
  rev_path text[], -- optional unordered set, useful for debugging
  rev_search_depth integer,
  rev_length numeric,
  rev_area numeric
);
CREATE INDEX ON tree (to_node);
INSERT INTO …

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

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

我的结构基于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, …

我的关系数据库(Firebird)中有一个DAG,有两个表edge和node(邻接列表模型).我想以递归方式查询它们,但发现递归查询非常低效.因此,我试图在Dong et.al之后实现触发器以维持传递闭包.论文http://homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf.

SELECTs现在非常快,但是DELETEs非常慢,因为几乎整个图形被复制用于单个删除.更糟糕的是,并发更新似乎不可能.

有没有更好的方法来实现这个？

编辑

我做了一些实验并向TC表引入了一个参考计数器.有了这个,删除很快.我写了一些简单的测试用例,但我不确定我做得对.这是我到目前为止:

CREATE GENERATOR graph_tc_seq;

CREATE TABLE EDGE (
    parent DECIMAL(10, 0) NOT NULL,
    child DECIMAL(10, 0) NOT NULL,
    PRIMARY KEY (parent, child)
);

CREATE TABLE GRAPH_TC (
    parent DECIMAL(10, 0) NOT NULL,
    child DECIMAL(10, 0) NOT NULL,
    refcount DECIMAL(9, 0),
    PRIMARY KEY (parent, child)
);

CREATE TABLE GRAPH_TC_TEMP (
    session_id DECIMAL(9, 0),
    parent DECIMAL(10, 0),
    child DECIMAL(10, 0)
);

CREATE PROCEDURE GRAPH_TC_CREATE (p_parent DECIMAL(10, 0), c_child …

我正在开始一个有一些分层数据的新项目,我正在查看目前存储在数据库中的所有选项.

我正在使用PostgreSQL,它允许递归查询.我还研究了关系数据库的设计模式,比如闭包表,我看了一下图形数据库解决方案,比如neo4j.

我发现很难在这些选项之间做出决定.例如:假设我的RDBMS允许递归查询,那么使用闭包表是否仍然有意义？在可维护性和性能方面,它与图数据库解决方案相比如何？

任何意见/经验将不胜感激!

我有一个数据库,其中包含使用邻接列表模型存储的类别层次结构.

层次结构深度为3级(不包括假想的根节点),包含大约1700个节点.第二级和第三级的节点可以有多个父节点.另外一个表用于多对多关系,如下所示:

CREATE TABLE dbo.Category(
    id int IDENTITY(1,1) NOT NULL,
    name varchar(255) NOT NULL,
)

CREATE TABLE dbo.CategoryHierarchy(
    relId int IDENTITY(1,1) NOT NULL,
    catId int NOT NULL,
    parentId int NOT NULL,
)

如果我转向使用传递闭包表方法(为了数据完整性等)是否有一个相对容易的查询,我可以执行,将生成闭包表的值？(使用SQL Server 2005)

我查看文章和演示文稿,例如Bill Karwin的分层数据模型,但只有单个节点的插入查询,我需要永远创建这样的树.

谢谢.

编辑:
CategoryHierarchy表中的RelID纯粹是为了主键,它与Category表的节点ID无关.

还有闭包表,我的意思是这样一个表:

CREATE TABLE ClosureTable (
    ancestor int NOT NULL,
    descendant int NOT NULL,
    [length] int NOT NULL,
)

前两列是复合主键,并且是Category.id的单独外键.

注意:在RhodiumToad的#postgresql帮助下,我已经找到了一个解决方案,我将其作为答案发布.如果有人可以改进这一点,请加入!

我无法使先前的递归查询解决方案适应包含多个"根"(无祖先)节点的以下有向非循环图.我正在尝试编写一个查询,其输出通常称为闭包表:一个多对多表,它存储从每个节点到每个后代及其自身的每条路径:

1  2  11  8  4  5  7
 \/    |  |   \ | /
  3    |   \    6
   \   |    \  /
    9  |     10
     \/     /
     12    13
       \  /
        14

CREATE TABLE node (
  id        SERIAL PRIMARY KEY,
  node_name VARCHAR(50) NOT NULL
);

CREATE TABLE node_relations (
  id                 SERIAL PRIMARY KEY,
  ancestor_node_id   INT REFERENCES node(id),
  descendant_node_id INT REFERENCES node(id)
);

INSERT into node (node_name)
SELECT 'node ' || g FROM generate_series(1,14) g;

INSERT INTO node_relations(ancestor_node_id, …

我创建了一个简单的例子来说明PostgreSQL中使用递归查询的传递闭包.

但是,我的递归查询有些问题.我不熟悉语法,所以这个请求可能完全是我的noobish,为此我提前道歉.如果运行查询,您将看到节点1在路径结果中重复自身.有人可以帮我弄清楚如何调整SQL吗？

/*           1
           /   \
          2     3
         / \   /
        4  5  6
       /
      7
     / \
    8   9
*/

create table account(
acct_id INT,
parent_id INT REFERENCES account(acct_id),
acct_name VARCHAR(100),
PRIMARY KEY(acct_id)
);

insert into account (acct_id, parent_id, acct_name) values (1,1,'account 1');
insert into account (acct_id, parent_id, acct_name) values (2,1,'account 2');
insert into account (acct_id, parent_id, acct_name) values (3,1,'account 3');
insert into account (acct_id, parent_id, acct_name) values (4,2,'account 4');
insert into account (acct_id, parent_id, acct_name) values (5,2,'account 5'); …

我想实现分层数据结构(例如Product - > Product 2 ----> Product3,Product 2 ----> Product4)使用实体框架6代码的第一种方法.有几种方法可用,但我认为封闭表方法可以满足我的所有要求.有人可以指导我如何有效地或任何其他替代方案在实体框架6中实施闭包表方法？