1

So I have the following sql table: 

CREATE TABLE LINKTABLE (
  id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
  parent_id INT,
  quote_id INT,
  article_id INT,
  asset_id INT,
  blog_id INT
);

The ids here are references to other tables (blog, article, etc) with the exception of parent_id which references the blog table as well. The idea here is that a quote can link an article to a blog or a blog to a parent blog parent.

This forms a tree where articles are leaves, blogs are nodes and quotes are branches between nodes and leaves.

Given that I have this table, I'm trying to figure out the most efficient way to traverse it. Greedily, I think I can just iterate through all quotes and then link nodes together, but that then means that my runtime will be determined by the number of branches I have, which I think is factorial time (?).

Does anyone have a better solution?

EDIT: Forgot to add this is in mysql.

EDIT EDIT: One dead end appears to be to include all quotes between any two blogs A and C irrespective of if there is a blog B such that A is a parent of B is a parent of C with the same quote, and then removing the A to C connection as being a shorter path. Here (How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?) seems to imply that that approach is NP-hard.

GMB
  • 216,147
  • 25
  • 84
  • 135
Peter Weyand
  • 2,159
  • 9
  • 40
  • 72
  • 1
    The only option you really have is a recursive CTE -- and that only if you are using MySQL 8+. – Gordon Linoff Nov 17 '19 at 00:35
  • @peter, could you focus your question to one problem only? traversing and the "dead end" case are really two different things. Sample data and expected result would also be helpful. – trincot Nov 17 '19 at 11:51

0 Answers0