Questions tagged [tree]
Trees are special cases of graphs. They are acyclic i.e. there is at most one path from any node to any other node. Typical uses include hierarchical data (parent-child relationships; roll-up aggregate values) and BTree indexes.
62
questions
2
votes
0
answers
53
views
How to swap the paths of two records (and their children) using a postgresql ltree?
How do I swap two record's paths/positions in an ltree using postgres, where all children follow? There is a uniqueness constraint on the path.
Given the following records on a pages table:
id: 1, ...
- 121
0
votes
0
answers
22
views
Finding tree contours using nested set model
Is there a query or algorithm that will enable me to find the left and right contours for general hierarchical trees and subtrees described using the nested sets model?
I have described tree ...
- 131
0
votes
0
answers
23
views
Help with design using ltree on PostgreSQL
Currently designing a database to register animal species (Sharks and relatives)
1 table will hold species (name, attributes, and relative information)
I will have the taxonomy hierarchy for each ...
- 101
-2
votes
1
answer
91
views
I want to make a tree of parents only in sql server
My table in the database
How can I get my result as Where child = 'chl1'?
2
votes
0
answers
111
views
DB design for tree structure of user access permissions
I am trying to come up with a good database design for the following problem:
We have an application where users can create objects (such as notes) and link those objects to other objects, projects or ...
- 21
1
vote
0
answers
57
views
TSQL - retrieve all IDs in a tree for a given subnode
I've tried to translate and implement the PostGres solution to the problem found here: PostgreSQL - retrieve all IDs in a tree for a given subnode, but I'm either programming it wrong, or ...
- 111
0
votes
1
answer
436
views
how to update the tree path of the table in PostgreSQL
I have a menu table in PostgreSQL 13 like this:
-- Drop table
-- DROP TABLE public.menu_resource;
CREATE TABLE public.menu_resource (
id int4 NOT NULL GENERATED ALWAYS AS IDENTITY,
"...
- 755
-3
votes
1
answer
34
views
Seek query to change a text parent-child relationship into an integer parent-child relationship
What is the query against table a that returns the result below?
with a as ( values
(1,'a023C000002yyrBQAQ',''),
(2,'a023C000002yy0SQAQ','a023C000002yyrBQAQ'),
(3,'a023C000002yy0WQAQ','...
- 11
5
votes
1
answer
1k
views
How to turn a set of flat trees into a single tree with multiple leaves?
We have this beautiful Postgres tree generator. Yet it kind of produces cuts of a tree not a whole tree all at once:
item_id jsonb_pretty
1 {
"title": "PARENT",
"...
- 75
0
votes
2
answers
465
views
How to limit tree traversal in case of loops?
So I want to limit tree depth traversal (as the simplest recursion killer tool). Example code that turns normalized records into tree:
CREATE TABLE items (
item_id serial PRIMARY KEY,
title ...
- 75
0
votes
1
answer
213
views
handling primary key with large tree, best way to get root id from child table X
I always used database design using this pattern;
root table with PK id1
child1 table with PK id2 FK id1
child2 table with PK id3 FK id2
child3 table with PK id4 FK id3
etc...
so if I have to get ...
- 159
3
votes
1
answer
4k
views
Recursively find the path to all leaves descending from a given parent in a tree
I'm trying to write a query to identify the path to each furthest descendant of a particular parent node in a table of tree structures like:
0 1
| |
2 3
| |
4 5
...
- 155
2
votes
0
answers
394
views
Drop intermediate results of recursive query in Postgres
I'm trying to aggregate the contents of a column from a directed acyclic graph (DAG) stored in a Postgres table.
Each dag row has an id, bytes, and may also have a parent referencing another row. I'm ...
- 155
0
votes
1
answer
63
views
Aggregating nested set models with field constraints
I have a table built on the nested set model that basically records transactions of different natures (defined by the field idx):
pk lft rgt idx value
1 1 30 2783 20402.710000
2 ...
- 123
4
votes
2
answers
374
views
Is it possible to expose the max depth of the B-Tree behind a rowstore index or a way to see how many nodes were traversed for a particular query?
I'm personally interested in data structures and with knowing that rowstore indexes are stored with a B-Tree behind them, I'm always curious in trying to visualize what those B-Trees look like for a ...
- 35.2k
0
votes
1
answer
287
views
Mongodb tree structure questions and answers
I'm looking to build a question answer survey system where some questions will be based on the answer of the parent question. The hierarchy level of the questions can go any number of depth based on ...
- 101
0
votes
1
answer
2k
views
Calculate products count based on category tree table
It is necessary to calculate how many products were created in each category, of course, that the products created in a child must be considered for the parent.
How can i do that SQL/Postgresql?
...
- 3
0
votes
0
answers
42
views
How to UPSERT tree in PostgreSQL?
There is a tree-structures in two-tables with ParentId field. How to make UPSERT (INSERT ... ON CONFLICT (...) DO UPDATE ...) between them? The problem is that parent record for the current record in ...
- 1
0
votes
1
answer
594
views
Exclusion constraint on recursive foreign key (on the example of a Tree)
I have the table with recursive foreign key. It's just hierarchical tree structure:
CREATE TABLE tree (
id INTEGER GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
value ...
- 111
0
votes
1
answer
2k
views
Sql, get category tree for values from one table, names and ids
What I need
I need select all ids or names from table "category" (all chidrens) until category_id is 0 (main category).
Example
On web there is product with category tree.
In table "category" I have ...
-1
votes
1
answer
351
views
PostgreSQL, Stored Procedures, Recursive call Tree structure
I'm faced with a problem.I have a ternary structured data. The relation is from child to parent, more specific a child has an parent_id. A parent shouldn't have more than 3 children. When 4th child ...
0
votes
1
answer
77
views
Optimizing one-way syncing of large (wide) tree
I deal with several trees that can vary in size (they all have depths of ~8-10) but it's not unusual for them to consist of ~50-100k nodes.
At the moment, the trees are stored using simple parent_id ...
- 337
2
votes
2
answers
1k
views
Joining two ltree based tree tables recursively
I have two tables, roles and permissions, both of which use ltree for maintaining a tree structure. I also have a pivot table, roles_permissions, which serves to connect the two tables. How can I join ...
- 121
8
votes
2
answers
6k
views
PostgreSQL - retrieve all IDs in a tree for a given subnode
I have a non-binary tree of customer, and I need to obtain all the IDs in a tree for the given node.
The table is very simple, just an join table with a parent id and child id.
This is a ...
- 113
2
votes
1
answer
208
views
How to Store Trees on Disk
I am wondering how to store trees on a physical disk, for perhaps a tree-oriented database like an XML database.
Wikipedia states about XML databases:
...custom optimized data structures are used ...
- 189
1
vote
0
answers
100
views
Scalable way to manage aggregated statistics over time in hierarchy?
I'm using a closure table (Postgres through Django) to roll up stats through a hierarchical tree. When a node that is 10 layers deep has a value that increases, each parent's sum total of that value ...
- 11
9
votes
0
answers
4k
views
Working on a decision tree database design
I'm doing the conceptual model for a Decision tree database. The goal is store any Decision tree.
I have four entity types: DecisionTree, Node, Branch and Leaf.
Each Decision tree is composed of ...
- 91
1
vote
0
answers
103
views
Nested set model in higher dimensions
The nested set structure is well-known and involves using left and right values to denote the relative heirarchy of nodes on one axis.
Is there a generalization of this structure to higher dimensions?...
- 11
0
votes
1
answer
480
views
Bypass truncated data type error in `CREATE TABLE AS`
I am attempting to recreate the code from this excellent tutorial in MariaDB 10.2 to try and build nested sets from an existing adjacency list. (The goal being to ingest changes to the adjacency list ...
- 510
0
votes
1
answer
3k
views
How can I get performance using PostgreSQL CTE recursive?
I did a tree structure using id and parent_id in the same table. For query's I'm using CTE provide by PostgreSQL, but it's spend so much time to do the joins with recursive results. For example, by ...
- 11
4
votes
2
answers
7k
views
Create JSON object from recursive tree structure
Having this simple many-to-many self-referential structure.
An item owns other items through the joins table:
CREATE TABLE items (
item_id serial PRIMARY KEY
, title text
);
CREATE TABLE ...
- 169
2
votes
4
answers
174
views
Representing ownership of heirarchical tree structure
In an application I'm developing, I have (among others) two structures: Users and Folders.
CREATE TABLE users (
id SERIAL PRIMARY KEY,
name TEXT NOT NULL
);
CREATE TABLE folders (
id ...
- 132
0
votes
1
answer
266
views
Binary tree "get open list" SQL query
I have a node table that looks like this, plus it has an inserted_at column:
id | parent_id
----------+-----------
1 | nil
2 | 1
3 | 1
4 | 2
5 | 2
...
- 103
5
votes
1
answer
4k
views
What would be the maximum number of records that can be indexed with a three levels B-tree ? B+ tree?
I am learning dynamic tree-structure organizations and how to design databases.
Consider a DBMS with the following characteristics :
file pages with size 2048 bytes
pointers of 12 bytes
page header ...
1
vote
1
answer
801
views
How to create data tree in MS Access
I am trying to build a database in which I am going to need to have a tree to keep track of cars.
Unfortunately, I don't always know what level of detail I am going to have, and the level that I do ...
- 11
2
votes
0
answers
600
views
Retrieve all product from one category (tree model)
I'm using MySQL, have categories in a tree model. One product belongs to only one (leaf) category.
What I want to accomplish is, given one category (any, could or not be a leaf or a root), return ...
- 121
6
votes
2
answers
13k
views
How to best store a directory tree in a database?
I want to represent my directory structure in some format (currently I'm just using JSON.)
This is how a sample JSON might look. For those curious it was generated using unix tree command: tree /path/...
- 61
0
votes
1
answer
285
views
Can InnoDB use a clustered index as a covering index?
The scenario I have in mind is a query like:
SELECT id FROM table WHERE id = ?
or equivalently,
SELECT 1 FROM table WHERE id = ?
So here's some background:
In a B+ tree (which InnoDB uses as ...
- 101
0
votes
1
answer
118
views
DB schema for storing the process tree of linux
I search a db schema to store the process tree of linux every half hour.
Platform: PostgreSQL on Linux.
I am unsure where to split all the data into columns or to use a json column.
Which one is ...
- 1,491
4
votes
1
answer
517
views
B Tree and B+Tree differences
I'm studying B+ Tree and B Tree and I would like to understand two things about it, if someone can clarify it to me I would appreciate:
Why can I store more search keys on an B+ Tree Index? My guess ...
- 41
5
votes
1
answer
2k
views
For each category, find the count of foreign-key items in all child categories using a PostgreSQL Recursive CTE
I have a typical tree structure stored as an adjacency list in PostgreSQL 9.4:
gear_category (
id INTEGER PRIMARY KEY,
name TEXT,
parent_id INTEGER
);
As well as a list of items attached ...
- 305
4
votes
2
answers
863
views
Lineage tree database design [duplicate]
As the title says, I'm building a cannabis strain genetics/lineage database.
If you didn't know; one cannabis strain may be an original strain (no parents) or it could be the result of many crosses (...
- 191
3
votes
2
answers
7k
views
Best design for a tree-like structure database
I'm designing a database in MS Access which is used for tracking the locations of a variety of chemical solutions, made in batches.
Each batch can be split (aliquoted) practically indefinitely. That ...
- 133
-3
votes
1
answer
923
views
MySql - Get all child categories until not exists
Based on this answer, can you please tell me what's wrong in the next code ? I'm trying to get all child categories.
The example that I try it is:
DELIMITER $$
DROP FUNCTION IF EXISTS `...
- 11
2
votes
1
answer
762
views
"No Loop" Constraint for hierarchical data in postgresql
I've got table like this in postgres:
id primary key
parent_id foreign key on id
some data columns
I need no a constrain which prevents cycles on the parent relations. There might be more tree in ...
- 121
1
vote
1
answer
2k
views
Implement a Parent-Level Count in Binary Search Tree
Based on this question, have any way to implement a parent level count?
Find highest level of a hierarchical field: with vs without CTEs
Example table:
+----+-----------+
| id | parent_id |
+----+-...
- 113
3
votes
1
answer
3k
views
Summarize from unlimited level depth parent-child in mysql
I have 2 table master coa and coa transaction in MySQL like this,
master :
id | coa | id_parent |
----+------+-----------+
1 | 1 | NULL |
2 | 11 | 1 |
3 | 111 | 2 ...
4
votes
1
answer
1k
views
adjecency list model vs nested sets
I've stumbled upon an article describing nested sets model for storing hierarchical data and was quite intrigued by the supposed performance boost.
after implementing this in our database, i've found ...
- 147
18
votes
1
answer
13k
views
How do I sort the results of a recursive query in an expanded tree-like fashion?
Let's assume you have a nodes tables like this:
CREATE TABLE nodes (
node serial PRIMARY KEY,
parent integer NULL REFERENCES nodes(node),
ts timestamp NOT NULL DEFAULT now()
);
It ...
- 515
2
votes
1
answer
14k
views
Recursive Query in MySQL using stored proceedure and CURSOR
I'm expanding our user/group system to allow for dynamic groups which are made up of other groups members. I have three tables users, groups, and relationships.
For simplicity sake, lets say users ...
- 506