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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
16 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, "...
user avatar
  • 477
-3 votes
1 answer
29 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','...
user avatar
  • 1
0 votes
0 answers
48 views

document db tree structure - is it valid to have both child and parent references in each node?

I'm in the process of building a tree structure, which should support the following requirements: It should be possible to find the root of the tree The tree will most often be traversed from root-&...
user avatar
4 votes
1 answer
310 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", "...
user avatar
  • 65
0 votes
2 answers
62 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 ...
user avatar
  • 65
0 votes
1 answer
43 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 ...
user avatar
  • 159
2 votes
1 answer
739 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 ...
user avatar
2 votes
0 answers
143 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 ...
user avatar
0 votes
1 answer
27 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 ...
user avatar
2 votes
1 answer
41 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 ...
user avatar
  • 24k
0 votes
1 answer
100 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 ...
user avatar
  • 101
0 votes
1 answer
1k 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? ...
user avatar
  • 3
0 votes
0 answers
34 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 ...
user avatar
  • 1
0 votes
1 answer
302 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 ...
user avatar
0 votes
1 answer
794 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 ...
user avatar
-1 votes
1 answer
231 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 ...
user avatar
0 votes
1 answer
52 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 ...
user avatar
0 votes
0 answers
91 views

How does query parameters work under the hood?

I thought about how can it work under the hood and I came with an idea Db engine receives query with parameters and also defined values of those parameters SQL is being parsed into syntax tree like ...
user avatar
  • 111
1 vote
2 answers
693 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 ...
user avatar
  • 111
6 votes
2 answers
4k 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 ...
user avatar
2 votes
1 answer
155 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 ...
user avatar
  • 209
1 vote
0 answers
72 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 ...
user avatar
  • 11
8 votes
0 answers
3k 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 ...
user avatar
1 vote
0 answers
60 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?...
user avatar
  • 11
0 votes
1 answer
316 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 ...
user avatar
0 votes
1 answer
2k 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 ...
user avatar
4 votes
2 answers
3k 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 ...
user avatar
  • 165
2 votes
4 answers
120 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 ...
user avatar
  • 133
0 votes
1 answer
201 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 ...
user avatar
  • 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 ...
user avatar
1 vote
1 answer
687 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 ...
user avatar
  • 11
2 votes
0 answers
475 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 ...
user avatar
5 votes
2 answers
9k 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/...
user avatar
0 votes
1 answer
265 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 ...
user avatar
  • 1
0 votes
1 answer
108 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 ...
user avatar
  • 1,331
4 votes
1 answer
343 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 ...
user avatar
  • 41
4 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 ...
user avatar
4 votes
2 answers
814 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 (...
user avatar
3 votes
2 answers
6k 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 ...
user avatar
-3 votes
1 answer
819 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 `...
user avatar
  • 11
2 votes
1 answer
672 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 ...
user avatar
  • 121
1 vote
1 answer
1k 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 | +----+-...
user avatar
3 votes
1 answer
2k 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 ...
user avatar
4 votes
1 answer
971 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 ...
user avatar
  • 147
16 votes
1 answer
11k 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 ...
user avatar
  • 475
2 votes
1 answer
13k 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 ...
user avatar
  • 506
2 votes
0 answers
226 views

Building a tree in Apache Derby 10.10

I know this question has been asked probably a million times, so please forgive me asking it again. I am not a DBA and have very little knowledge of SQL and Derby, but need some kind of a solution as ...
user avatar
  • 23
11 votes
3 answers
28k views

COUNT of rows with parent id equal to the row we have with a parent id of 0 in one query

I'd like to do the following in one query using MySQL: grab a row that has a parent_id of 0 grab a count of all the rows that have a parent_id of the row that we grabbed which has a parent_id of 0 ...
user avatar
2 votes
1 answer
173 views

How to select nodes where all children is satisfied?

I have a tree structure of light bulbs. I want to turn on all the light bulbs starting from the leafs of the tree. A light bulb cannot be turned on unless all its immediate children are turned on. ...
user avatar
  • 289
1 vote
2 answers
2k views

Performing SELECT on EACH ROW in CTE or Nested QUERY?

This is a problem in PostgreSQL I have a table which stores the tree of users; +------+---------+ | id | parent | |------+---------| | 1 | 0 | |------|---------| ...
user avatar
  • 281