SQL PageRank实现

Question

有没有好的SQL PageRank实现呢？我看了http://www.databasedevelop.com/197517/，但是它的可读性和(T-SQL)语法不正确。

顺便问一下，有人知道上面链接中使用的是什么SQL吗？哪种SQL会在随机位置使用"is"，在"where"后面什么都不加，还有那个奇怪的AT关键字等等？

- Bondolin

---

这个链接的 T-SQL 真是糟糕透了。使用游标并不是正确的工具。PageRank 完美地映射到了 Map-Reduce 风格的 SQL 查询。 - usr

什么是Map-Reduce风格？ - Bondolin

Map-reduce是“GROUP BY”查询的现代流行词。搜索“Page Rank Map Reduce”以了解更多信息。 - usr

谢谢，这很有帮助。但是是否有SQL实现？ - Bondolin

我刚刚发现我们的系统无法进行MapReduce... - Bondolin

我已经在T-SQL中完成了PageRank。我没有时间清理代码并发布它，遗憾的是。但它足够简单，你可以将通用的PageRank教程转换为SQL代码。（此外，每个SQL Server都可以执行MapReduce，只是不被称为这样）。 - usr

Answer 1

我刚刚在SQL中实现了PageRank算法。该算法的工作流程如下：

1.计算PageRank的初始排名值；

2.将PageRank表与Edge表连接，向相邻节点发出排名值，并使用聚合函数sum来“收集”接收到的值。然后，将结果保存到临时表TmpRank中；

3. 交换PageRank和TmpRank的内容，并转到步骤2，直到满足收敛条件或达到最大迭代次数。

以下是代码：

-- The graph data and algorithm source from the book "Mining of Massive Datasets", P175, http://infolab.stanford.edu/~ullman/mmds/book.pdf
-- This script has been verified the correctness in SQL Server 2017 Linux Version.
DROP TABLE Node;
DROP TABLE Edge;
DROP TABLE OutDegree;
DROP TABLE PageRank;
CREATE TABLE Node(id int PRIMARY KEY);
CREATE TABLE Edge(src int,dst int, PRIMARY KEY (src, dst));
CREATE TABLE OutDegree(id int PRIMARY KEY, degree int);
CREATE TABLE PageRank(id int PRIMARY KEY, rank float);
CREATE TABLE TmpRank(id int PRIMARY KEY, rank float);

--delete all records
DELETE FROM Node;
DELETE FROM Edge;
DELETE FROM OutDegree;
DELETE FROM PageRank;
DELETE FROM TmpRank;

--init basic tables
INSERT INTO Node VALUES (0);
INSERT INTO Node VALUES (1);
INSERT INTO Node VALUES (2);
INSERT INTO Node VALUES (3);

INSERT INTO Edge VALUES (0, 1);
INSERT INTO Edge VALUES (0, 2);
INSERT INTO Edge VALUES (0, 3);
INSERT INTO Edge VALUES (1, 0);
INSERT INTO Edge VALUES (1, 3);
INSERT INTO Edge VALUES (2, 2);
INSERT INTO Edge VALUES (3, 1);
INSERT INTO Edge VALUES (3, 2);

--compute out-degree
INSERT INTO OutDegree
SELECT Node.id, COUNT(Edge.src) --Count(Edge.src) instead of Count(*) for count no out-degree edge
FROM Node LEFT OUTER JOIN Edge
ON Node.id = Edge.src
GROUP BY Node.id;

--WARN: There's no special process for node with out-degree, This may cause wrong result
--      Please to make sure every node in graph has out-degree

DECLARE @ALPHA float = 0.8;
DECLARE @Node_Num int;
SELECT @Node_Num = COUNT(*) FROM Node;

--PageRank Init Value
INSERT INTO PageRank
SELECT Node.id, rank = (1 - @ALPHA) / @Node_Num
FROM Node INNER JOIN OutDegree
ON Node.id = OutDegree.id

/*
--For Debugging
SELECT * FROM Node;
SELECT * FROM Edge;
SELECT * FROM OutDegree;
SELECT * FROM PageRank;
SELECT * FROM TmpRank;
*/

DECLARE @Iteration int = 0;

WHILE @Iteration < 50
BEGIN
--Iteration Style
    SET @Iteration = @Iteration + 1

    INSERT INTO TmpRank
    SELECT Edge.dst, rank = SUM(@ALPHA * PageRank.rank / OutDegree.degree) + (1 - @ALPHA) / @Node_Num
    FROM PageRank
    INNER JOIN Edge ON PageRank.id = Edge.src
    INNER JOIN OutDegree ON PageRank.id = OutDegree.id
    GROUP BY Edge.dst

    DELETE FROM PageRank;
    INSERT INTO PageRank
    SELECT * FROM TmpRank;
    DELETE FROM TmpRank;
END

SELECT * FROM PageRank;

- geng liang

Answer 2

根据您的SQL Server版本，可以查看OFFSET_FETCH窗口函数。有很多应用程序可用于页面排名。当然，这需要2012年或更高版本。

我也使用了SSIS和NTILE（）分割临时表来完成分页，在无法使用OFFSET_FETCH的情况下。通常使用记录计数除以我想在页面中看到的某个最大数字作为NTILE调用的种子。

由于某些原因，我甚至无法打开您的链接，所以希望这就是您要求的内容。 MSDN - OFFSET_FETCH MSDN - NTILE

- Matt