How to find the longest prefix among the rows and to group on it?

Hello! Already spammed the whole Google, but what he gave, could not apply.
Could only find that such a problem is called Longest common prefix(LCP)

There is a table example:
| id | parent_id | path |
| 1 | 7 | val10/val11/val12/val3 |
| 2 | 7 | val1/val2/val3/val5 |
| 3 | 7 | val1/val2/val3/val6 |
| 4 | 7 | val1/val2/val3/val7 |
| 5 | 7 | val1/val2/val3/val8 |
| 6 | 7 | val1/val2/val3/val9 |

How to group the rows by the longest column prefix path relative to the parent_id? Under the prefix meaning the repeating part of the string starting from the beginning.

For the above table output should be:
| parent_id | path | count |
| 7 | val1/val2/val3 | 5 |
| 7 | val10/val11/val12/val3 | 1 |

to generate example:
create table example (id int, parent_id int, path varchar(50));

insert into example
select 1, 7, 'val10/val11/val12/val3'
union select 2, 7, 'val1/val2/val3/val5'
union select 3, 7, 'val1/val2/val3/val6'
union select 4, 7, 'val1/val2/val3/val7'
union select 5, 7, 'val1/val2/val3/val8'
union select 6, 7, 'val1/val2/val3/val9'

Perhaps, someone met such problem, respond! )
April 4th 20 at 13:19
3 answers
April 4th 20 at 13:21
Thanks for the tip! - Cleo.Green commented on April 4th 20 at 13:24
April 4th 20 at 13:23
um,,, select path, count(*) from example group by path ?
or am I missing something in not quite understand?
Not really, maybe I explained badly. The records with id 2 and 6 have a common piece of val1/val2/val3, here on it and you want to group, but the record with id 1 string does not contain the prefix val1/val2/val3 according to this the expected output of this line stands alone.

When your option against each row will stand 1, because they are all different.

Thanks for the response! - Cleo.Green commented on April 4th 20 at 13:26
@Jaleel34, and can be poshirshe to deploy the application sense?
I suspect that val1/val2/val3/val8 - it is "shapotou" in the original [somewhere] this is most likely something "wide" type bit fields

If Yes, then I would turn to this - Jude_Schamberger commented on April 4th 20 at 13:29
Generally it's just the structure of departments, and the point with parent_Id=7 we need to find the most appropriate unit. I then the meaning came the greatest common prefix. In its original form is a tree, parent-child, the only problem is that at points such parent_id = 7 no units and I need it to "determine" on the basis of the child. - Cleo.Green commented on April 4th 20 at 13:32
THAT is, for val1/val2/val3/this val8


Type for each id is a piece of some kind of global hierarchy without an explicit initial currents??? - Jude_Schamberger commented on April 4th 20 at 13:35
1. There is a table with a hierarchy of divisions, then the tree

table departments:
| id | parent_id | name |

2. There is a table with entities that have a sign department_id
| id | parent_id | department_id |

In the "table entities", those id, which are included in the list in the field department_id parent_id and parent_id is empty in my example, this is the entity with id = 7

The other entity is a sign department_id (in my example is id 1 - 6)

Duck here, task is the entity with id = 7 to find the most suitable unit based on the children names.

The names 'val1/val2/val3/val5' it just rolled OU tree.

I hope it is clear painted :) - Cleo.Green commented on April 4th 20 at 13:38
Yes, it seems the idea caught. That is id=7 "lost" chain.
Do I understand correctly that the extracted chain is guaranteed there is an inextricable piece of some greater (common tree)?

If Yes - then there is the idea:
- assume that petranyi chain - end - that is, the tails coincide
- build a main hierarchy tree of all possible chains
- looking for a match reversal
that is, in the complete hierarchy chain is
a0/b1/c2/d3/e4/f5 - reverse - f5/e4/d3/c2/b1/a0
a "scrap" d3/e4/f5 - reverse f5/e4/d3

so this pruning could find the original chain...

if the assumption about the matching tails incorrectly - will have a series of "shortened" full chain and search again - Jude_Schamberger commented on April 4th 20 at 13:41
April 4th 20 at 13:25
As for me - the task is set incorrectly. Or not enough extra-conditions. For example, I believe that the common prefix should be.

| parent_id | path | count |
| 7 | val1 | 6 |
Better. But not enough. I still can specify the initial data in which there will be many variants of prefixes. - Brandon.MacGyver60 commented on April 4th 20 at 13:31
I agree with this comment, there needs to be prefixed with the given delimiter “/“. Ie the comparison is in substrings with a delimiter “/“. - Cleo.Green commented on April 4th 20 at 13:28

Find more questions by tags PostgreSQLSQL