计算SQL表中的最小路径长度 [英] Computing minimum path lengths in an SQL table

问题描述

我在练习中遇到问题:

表Friend:

 Friend1     Friend2

表Relationship:

 Friend1     Friend2      GradeOfFriendship

我需要创建一个触发器，在其中必须获取对称元组，例如:

I need to create a trigger in which I must obtain symmetric tuple, for example:

Luc    Mark

Mark   Luc

在两个表中.

如果两个人之间有直接联系，那么他们的GradeOfFriendship = 1

If there is a direct contact between two people then their GradeOfFriendship = 1

如果两个人之间没有接触，则GradeOfFriendship = 0.

If there is no contact between a pair of people then GradeOfFriendship = 0.

在其他情况下，必须将GradeOfFriendship计算为连接这两个人的所有可能路径上的最小距离(我们必须将此表视为有向图)

In other cases the GradeOfFriendship must be calculated as the minimum distance over all possible paths connecting these two people (we must consider this table as a directed graph)

我的问题不是获取对称的元组，而是如何计算两个人之间的所有可能路径.例如:

My problem is not to obtain a symmetric tuple, but how to calculate all the possible paths between two people. For example:

   Luc     Marc 1
   Marc    John 1
   Luc     John 2

我正在使用SQL Server.目前，我不知道如何解决此问题-我认为我必须使用一些递归函数，但我不知道如何....

I am using SQL Server. At the moment I don't have any idea how solve this problem - I think that I must use some recursive function but I don't know how....

推荐答案

这是创建递归油炸网络的一种方法:

This is one way to create recursive fried network:

;with DATA as (
  select Person1, Person2, 1 as Grade from Friends
  union
  select Person2, Person1, 1 as Grade from Friends
),
CTE as (
  select Person1, Person2, Grade,
    convert(varchar(max), '|' + Person1 + '|' + Person2 +'|') as Path
    from DATA
  union all
  select C.Person1, D.Person2, C.Grade+1, C.Path+D.Person2+'|' 
  from CTE C join DATA D on C.Person2 = D.Person1
  where C.Person1 <> D.Person2 and C.Path not like '|%'+D.Person2 +'%|'
)

select Person1, Person2, min(Grade)
from CTE
group by Person1, Person2
order by 1,3,2

第一个称为DATA的CTE在那里存在，因此不需要将Friedships双向输入到好友表中.如果已经有这种方式，则可以将其忽略.

The first CTE called DATA is there so that there's no need to have friedships entered both ways into friend table. If you have them that way already, you can leave it out.

第二个CTE称为CTE是递归的，它获取从一个人到另一个人的所有路径.路径-列，名称之间用|分隔在那里可以防止友谊交end时无休止的循环.

The second CTE called CTE is recursive, and it fetches all the paths from one person to another. The path -column with names separated by | is there to prevent endless loops when friendships make circles.

最终选择仅选择朋友之间的最短路径.

The final select picks only the shortest path between friends.

SQL小提琴中的示例

这篇关于计算SQL表中的最小路径长度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！