Truy vấn SQL để xử lý mối quan hệ phức tạp

Question

Tôi có một kịch bản mà tôi có một số lượng lớn các blog. Tất cả các blog này đều có nhiều bài đăng. Mỗi bài đăng trên blog có thể liên kết tới một bài đăng trên một blog khác, nhưng sau đó họ phải không bao giờ liên kết trở lại từ blog đó vào blog liên kết.

Để làm rõ:

• Site A liên kết đến các trang web B (và có thể liên kết đến trang web khác)
• Site B sau đó không thể liên kết đến trang web A (nhưng có thể liên kết đến trang web khác)

Mỗi lần đăng bài, tôi lưu trữ ID của bài đăng và ID của trang web mà nó liên kết tới. Điều quan trọng cần nhớ là khi một bài đăng duy nhất liên kết tới bất kỳ bài đăng nào trên một trang web khác mà trang web khác không thể liên kết lại từ ở bất kỳ đâu, không chỉ bài đăng được liên kết.

Trang web A có thể liên kết đến Trang web B nhiều lần tùy thích và mỗi bài đăng có thể liên kết đến nhiều bài đăng khác. Một kịch bản ví dụ có thể là:

• Site A liên kết đến các trang web B
• Site C liên kết đến các trang web B
• Site D liên kết đến các trang web Một

Trong dữ liệu trên:

• Trang web A có thể liên kết đến Trang web C (hoặc Trang web B một lần nữa)
• Trang web B có thể liên kết đến Trang web D
• Site C có thể liên kết đến trang web A hoặc trang web D (hoặc trang web B một lần nữa)
• Site D có thể liên kết đến trang web của B hoặc Site C (hoặc trang web A một lần nữa)

Dưới đây là một liên kết đến một số dữ liệu thử nghiệm và một bãi chứa của 2 bảng cần thiết: http://pastie.org/1506715

Tôi nghĩ rằng tôi cần tham gia chéo để có được tất cả các kết hợp liên kết có thể, nhưng sau đó đưa các mối quan hệ hiện có để ngăn các trang web liên kết ngược lại. Truy vấn tôi có cho đến thời điểm này là:

SELECT 
t1.* , t2.* FROM test_posts t1, test_posts as t2 
WHERE 
t1.post_id != t2.post_id 
ORDER BY 
t1.post_id, t2.post_id; 

Điều này mang lại cho tôi tất cả các mối quan hệ có thể có giữa các bài đăng. Những gì tôi đang đấu tranh là làm thế nào để loại trừ các mối quan hệ mà sẽ mâu thuẫn với các quy tắc trên. Các mối quan hệ trước đó được ghi lại trong bảng test_smartlinks_to_websites, với post_id thuộc trang web "originating" và website_id thuộc trang web "đích" (nhớ rằng mối quan hệ là một cách hiệu quả giữa các trang web, chứ không phải bài đăng).

Tôi đã thử sử dụng truy vấn con KHÔNG tồn tại, nhưng tôi không chắc chắn về điều khoản chính xác (hoặc cho dù đó là cách tiếp cận chính xác).

Answer 1

Sửa lỗi nếu tôi sai. Nó xuất hiện nhiệm vụ của bạn là để xác định chu kỳ trong đồ thị trực tiếp. Nó không phức tạp như nó có vẻ. Vui lòng xem bài đăng trên blog này để biết cách thực hiện trong SQL: http://devio.wordpress.com/2009/09/13/finding-cycles-in-directed-graphs-using-tsql/. Ngoài ra, hãy xem liên kết này cho tìm kiếm rộng đầu tiên trong SQL: http://willets.org/sqlgraphs.html.

CHỈNH SỬA: thêm hình ảnh để làm rõ và hiểu các đồ thị theo chu kỳ và tuần hoàn.

Ví dụ: đây là điều tương tự với tình huống của bạn. Nó không phải là một biểu đồ duy nhất mà là một bộ đồ thị (hoặc rừng nếu chúng là cây). Lưu ý không có gốc chung. Nó chỉ là các nút kết nối bằng cách nào đó. Có một chu kỳ trong đồ thị con lớn hơn nơi các nút tham chiếu lẫn nhau. Nếu để loại bỏ các liên kết trở lên, các đồ thị con trở nên tuần hoàn.