我正在尝试表示一个可传递关系（在数据库中），但很难确定最佳数据结构。
基本上，数据结构是一系列对，如果和，那么隐含地。对我来说，能够确定哪些条目是原始输入，哪些条目是隐含的是很重要的。询问是否相当于在有向图中查询是否存在从到的路径。
我可以只表示原始条目，但如果这样做，确定两个项是否相关需要很长时间，因为我需要搜索所有可能的路径，这会非常慢。
或者，我可以存储原始边缘以及所有路径的列表。这使添加新边缘变得容易，因为当我添加时，我可以只需取以结尾的路径和以结尾的路径的笛卡尔积并将它们放在一起。这在最坏情况下具有O（n²）的显着空间开销，但具有常数时间的查找操作是最常见的操作。问题在于删除，除了重新计算可能经过被删除边缘的所有路径，我想不出其他方法，而这可能非常棘手。
有更好的想法吗？
技术注释：有向图可能是循环的，但关系是自反的，因此我不需要表示自反性或存储任何有关它的信息。
基本上，数据结构是一系列对，如果和，那么隐含地。对我来说，能够确定哪些条目是原始输入，哪些条目是隐含的是很重要的。询问是否相当于在有向图中查询是否存在从到的路径。
我可以只表示原始条目，但如果这样做，确定两个项是否相关需要很长时间，因为我需要搜索所有可能的路径，这会非常慢。
或者，我可以存储原始边缘以及所有路径的列表。这使添加新边缘变得容易，因为当我添加时，我可以只需取以结尾的路径和以结尾的路径的笛卡尔积并将它们放在一起。这在最坏情况下具有O（n²）的显着空间开销，但具有常数时间的查找操作是最常见的操作。问题在于删除，除了重新计算可能经过被删除边缘的所有路径，我想不出其他方法，而这可能非常棘手。
有更好的想法吗？
技术注释：有向图可能是循环的，但关系是自反的，因此我不需要表示自反性或存储任何有关它的信息。