社交網路資料庫設計：怎麼找共同朋友、朋友的朋友

在 facebook 內當你點朋友時，你可以知道彼此共同朋友有哪些，另外在網頁右欄有個"你可能認識"的專區，這個功能是怎麼做的？

先來分析這兩個語意：
1. 共同的朋友："自己的朋友"跟"朋友的朋友"重疊的部分
2. 你可能認識的人：把朋友的朋友全部列出來，依據重疊次數來排序，越高的表示你越可能認識的人，如果是你還沒加到名單的，facebook 就會主動推薦給你


在 stackoverflow 找到兩篇參考文章：

• database design - how facebook calculates mutual friends? - Stack Overflow
• database - Wondering how Facebook does the "Mutual friends" feature - Stack Overflow 

關連式資料庫
用一般的關連式資料庫 (relational database)來找共同朋友

table: friends
--------------------------
 user_id | friend_id
---------+----------------
 1       | 2
 1       | 3
 1       | 4
 2       | 4
 3       | 1
 3       | 2
 4       | 3

若要找 1 跟 3 的共同朋友，可以下 sql query：

SELECT user_id FROM friends AS A, friends AS B
  WHERE A.user_id = B.user_id AND A.friend_id = 1 AND B.friend_id = 3
-- 用中文解釋就是，同一個人，擁有朋友1而且還擁有朋友3

得到結果就是 user 2
似乎很容易取得，而且 query 不會太複雜。



但如果要找"你可能認識的人"呢？這就有點難了...
分階段來作：

a) 朋友的朋友，但不是自己
參考 mysql - "people you may know" sql query - Stack Overflow

SELECT DISTINCT(F2.friend_id) FROM friends AS F1 
  INNER JOIN friends AS F2 ON F1.friend_id = F2.user_id 
  WHERE F1.user_id = 1 AND F2.friend_id != 1 

b) 朋友的朋友，但不是自己，且還不是我的朋友

SELECT DISTINCT(F2.friend_id) FROM friends AS F1 
  INNER JOIN friends AS F2 ON F1.friend_id = F2.user_id 
  WHERE F1.user_id = 1 AND F2.friend_id != 1 AND 
    F2.friend_id NOT IN (SELECT friend_id FROM friends WHERE user_id = 1)

c) 朋友的朋友，但不是自己，且還不是我的朋友，並統計重疊的次數

SELECT F2.friend_id, COUNT(F2.friend_id) FROM friends AS F1 
  INNER JOIN friends AS F2 ON F1.friend_id = F2.user_id 
  WHERE F1.user_id = 1 AND F2.friend_id != 1 AND 
    F2.friend_id NOT IN (SELECT friend_id FROM friends WHERE user_id = 1)
  GROUP BY F2.friend_id
  ORDER BY count DESC

Well ~ 看樣子還是辦得到！
但這些 query 的複雜度一定很大，如果每次 user refresh 就去 query，database 肯定會忙死，所以變成要 offline 執行，並且把結果存起來，一但有變動就要再重新 query，不過相對即時性就沒那麼高了。



圖形資料庫
從另一種角度思考，這個問題可以映射到圖學理論中的 bidirected graph，人是 vertex，關係是 edge。graph 要怎麼用 database 來存？於是找到了 graph database - neo4j，官網是這麼介紹的：

Neo4j
The World’s Leading Graph Database
Neo4j is a high-performance, NOSQL graph database with all the features of a mature and robust database.

找共同朋友
java - How to calculate mutual friends with neo4j? - Stack Overflow 用中文來解釋就是：vertex A 與 vertex B 的 shortest path，而且只過一個 hop

找你可能認識的人
(目前還沒研究)