MySQL顶点和边的交集

Question

我有两个表格：edges和users

edges（带有约束：id1 < id2）：

id1
name1
id2
name2

users:

id
name

我想要获取仅包含边缘(id1，name1，id2，name2)的结果集，以便BOTH id1和id2都在用户表中。这似乎很简单，但我无法做到。我的尝试：

SELECT
   e.id1 AS id1,
   e.name1 AS name1,
   e.id2 AS id2,
   e.name2 AS name2
FROM 
   edges AS e,
   users AS u
WHERE u.id = e.id1

UNION

SELECT
   e.id1 AS id1,
   e.name1 AS name1,
   e.id2 AS id2,
   e.name2 AS name2
FROM 
   edges AS e,
   users AS u
WHERE u.id = e.id2

任何提示？

- lollercoaster

Answer 1

尝试使用两个INNER JOIN，像这样：

SELECT * FROM edges e 
JOIN users u1 ON e.name1 = u1.name 
JOIN users u2 ON e.name2 = u2.name

- jordeu

---

这个可以！虽然有点慢，但我猜第一个JOIN是一个O(|V| * |E|)的操作，所以这些JOIN一起会导致运行时间为O(|V| * |E|^2)？可能这是我们能做到的最好的了吧？ - lollercoaster

在三个姓名字段上创建索引以提高性能。 - jordeu

我不确定，但我认为如果您的用户表比边缘表小，您可以先进行RIGHT JOIN，然后进行LEFT JOIN，这将加快查询速度。 - jordeu

在这种情况下，我们对每个字段进行哈希，意味着第一个连接查找的复杂度为 O(1) * O(|V|)，然后再增加另外 O(|V|)，因此总复杂度为 O(|V|)。 - lollercoaster

Answer 2

试试这个：

select e.id1, e.name1, e.id2, e.name2 from edges e
join users u1 on e.id1 = u1.id
join users u2 on e.id2 = u2.id

- Mosty Mostacho

---

是的，这是@jordeu的代码，但在这里你可以摆脱重复的列，这正是所需的。对于运行时间有什么想法吗？就像我之前提到的那样。 - lollercoaster

Answer 3

可能是这样的：

SELECT
   e.id1 AS id1,
   e.name1 AS name1,
   e.id2 AS id2,
   e.name2 AS name2
FROM 
   edges AS e
WHERE EXISTS
  (
      SELECT
        NULL
      FROM
        users AS u
      WHERE
        u.id = e.id1
        AND u.id = e.id2
  )

- Arion

---

这会返回空集合吗？ - lollercoaster

不，它返回具有用户的边缘。 - Arion