Skip to main content

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
1 vote
1 answer
115 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 ...
Squirrel-Power's user avatar
2 votes
1 answer
79 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) =>...
cjheppell's user avatar
  • 213
2 votes
0 answers
60 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, ...
Matthew's user avatar
  • 121
0 votes
0 answers
37 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 ...
Chris Walton's user avatar
0 votes
0 answers
24 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 ...
Tiago Conceição's user avatar
-2 votes
1 answer
163 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'?
Mahmoud fathy's user avatar
2 votes
0 answers
145 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 ...
hg.m's user avatar
  • 21
1 vote
0 answers
59 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 ...
Gthoma2's user avatar
  • 111
0 votes
1 answer
470 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, "...
Dolphin's user avatar
  • 773
-2 votes
1 answer
38 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','...
Emmett's user avatar
  • 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", "...
Blender's user avatar
  • 75
0 votes
2 answers
555 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 ...
Blender's user avatar
  • 75
0 votes
1 answer
228 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 ...
Fredou's user avatar
  • 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 ...
Jason Dreyzehner's user avatar
2 votes
0 answers
429 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 ...
Jason Dreyzehner's user avatar
0 votes
1 answer
69 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 ...
manoelpqueiroz's user avatar
4 votes
2 answers
479 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 ...
J.D.'s user avatar
  • 38.1k
1 vote
1 answer
323 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 99x's user avatar
  • 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? ...
boris's user avatar
  • 3
0 votes
0 answers
45 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 ...
osya's user avatar
  • 1
0 votes
1 answer
621 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 ...
Eldar Agalarov's user avatar
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 ...
Stanislav Hosek's user avatar
-1 votes
1 answer
378 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 ...
Husniddin Qurbonboyev's user avatar
0 votes
1 answer
85 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 ...
fgblomqvist's user avatar
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 ...
Forest's user avatar
  • 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 ...
Luca Nitti's user avatar
2 votes
1 answer
216 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 ...
Lance's user avatar
  • 209
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 ...
Evan H's user avatar
  • 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 ...
Amater90's user avatar
1 vote
0 answers
106 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?...
J. Pao's user avatar
  • 11
0 votes
1 answer
507 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 ...
Noah Goodrich's user avatar
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 ...
Tiago Mendes's user avatar
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 ...
Ben's user avatar
  • 179
2 votes
4 answers
179 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 ...
rintaun's user avatar
  • 132
0 votes
1 answer
267 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 ...
MetaStack's user avatar
  • 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 ...
Revolucion for Monica's user avatar
1 vote
1 answer
833 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 ...
Mark's user avatar
  • 11
2 votes
0 answers
608 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 ...
user1532587's user avatar
6 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/...
dufferZafar's user avatar
0 votes
1 answer
287 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 ...
igaz's user avatar
  • 101
0 votes
1 answer
119 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 ...
guettli's user avatar
  • 1,531
4 votes
1 answer
538 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 ...
David's user avatar
  • 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 ...
Jeff Widman's user avatar
4 votes
2 answers
868 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 (...
PaparazzoKid's user avatar
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 ...
Mark Butler's user avatar
-2 votes
1 answer
929 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 `...
Simona's user avatar
  • 21
2 votes
1 answer
778 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 ...
dve's user avatar
  • 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 | +----+-...
Marcelo Aymone's user avatar
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 ...
Septian Primadewa's user avatar
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 ...
lordvlad's user avatar
  • 147