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.
68 questions
2
votes
0
answers
59
views
How to prevent anomalies in a tree data structure
I have two tables node and node_tree:
CREATE TABLE node (
id integer PRIMARY KEY
);
CREATE TABLE node_tree (
node_id integer references node(id) UNIQUE,
parent_id integer references node(id)
);
...
- 175
1
vote
2
answers
46
views
How to convert a recursive query to a function?
I have written a PostgreSQL query that's working perfectly:
WITH RECURSIVE x AS (
SELECT i, parent, id, name, type, '' AS path
FROM entry
WHERE name = 'JS-VBNET-2'
UNION ALL
SELECT e.i,...
0
votes
1
answer
16
views
How to fuzzy query a directory structure in PostgreSQL?
I was able to put together a rough idea for a PostgreSQL query to query over a node table, which contains id, parent__id, slug, and file_url (optional). It's considered a file if it has file_url, ...
- 221
0
votes
0
answers
72
views
Modeling hierarchical data for multiple entities, inherited properties, and varying hierarchy
I am trying to model hierarchical data using a RDBMS but can't quite find the right solution. We are capturing information about storage levels in a warehouse system. There are 8 possible storage ...
- 1
0
votes
0
answers
45
views
Simplifying Complex Traversal Patterns Involving Multiple Association Types (1:N, M:N, N:1 ...)
I'm working on a data model for a system that represents interconnected entities with complex traversal requirements. Specifically, I have the following scenario:
An EntityA connected to multiple ...
- 1
1
vote
1
answer
415
views
SQL query classifying types of nodes in a binary tree
I am using MySQL in trying to solve a problem relating to a SQL query classifying types of nodes in a binary tree.
Specifically, the question states as follows:
You are given a table, BST, containing ...
- 111
2
votes
1
answer
121
views
Joining tables using the longest matching ltree path
Given a table like so:
path (ltree)
a.b.c
a.b
a
d.e
f
How would I write a query to return the longest matching ltree path given an input?
For example:
(input) => expected output
(a.b.c) =>...
- 213
2
votes
0
answers
69
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
33
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
211
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
172
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
62
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
490
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,
"...
- 825
-2
votes
1
answer
41
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','...
- 21
5
votes
1
answer
2k
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
632
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
233
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
5k
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
483
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
76
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
536
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 ...
- 39.5k
1
vote
2
answers
351
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 ...
- 111
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
48
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
638
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
397
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
99
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
3
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 ...
- 131
9
votes
2
answers
7k
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 ...
- 123
2
votes
1
answer
230
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 ...
- 221
1
vote
0
answers
106
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
107
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
532
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
5
votes
2
answers
8k
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 ...
- 179
2
votes
4
answers
186
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
274
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
5k
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
859
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
622
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
7
votes
2
answers
14k
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/...
- 71
0
votes
1
answer
291
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
124
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,561
4
votes
1
answer
545
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
875
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
-2
votes
1
answer
935
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 `...
- 121