tailieunhanh - Advanced SQL Database Programmer phần 7

Tôi đã nhận một email yêu cầu tôi làm thế nào để tìm đường đi trong một đồ thị bằng cách sử dụng SQL. Tác giả của email đã thấy chương của tôi trên đồ thị trong SQL cho Smarties, và đọc mà tôi không hài lòng với câu trả lời của riêng tôi. Những gì ông muốn là một danh sách các đường dẫn từ bất kỳ hai nút trong một biểu đồ chỉ dẫn | Graphs in SQL CHAPTER 11 Path Finder I got an email asking me how to find paths in a graph using SQL. The author of the email had seen my chapter on graphs in SQL for Smarties and read that I was not happy with my own answers. What he wanted was a list of paths from any two nodes in a directed graph and I would assume that he wanted the cheapest path. After thinking about this for a while the best way is probably to do the Floyd-Warshall or Johnson algorithm in a procedural language and load a table with the results. But I want to do this in pure SQL as an exercise. Let s start with a simple graph and represent it as an adjacency list with weights on the edges. CREATE TABLE Graph source CHAR 2 NOT NULL destination CHAR 2 NOT NULL cost INTEGER NOT NULL PRIMARY KEY source destination I got data for this table from the book Introduction to Algorithms by Cormen Leiserson and Rivest ISBN 0-262-03141-8 page 518. This book is very popular in college courses in the United States. I made one decision that will be important later I added self-traversal edges . the node is both the source and the destination with weights of zero. oracle 63 INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INTO INTO INTO INTO INTO INTO INTO INTO INTO INTO INTO INTO INTO INTO INTO Graph Graph Graph Graph Graph Graph Graph Graph Graph Graph Graph Graph Graph Graph Graph VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES VALUES s s s u u u v v x x x x y y y s 0 u 3 x 5 u 0 v 6 x 2 v 0 y 2 u 1 v 4 x 0 y 6 s 3 v 7 y 0 I am not happy about this approach because I have to decide the maximum number of edges in path before I start looking for an answer. But this will work and I know that a path will have no more than the total number of nodes in the graph. Let s create a table to hold the paths CREATE TABLE Paths step1 CHAR 2 NOT NULL step2 CHAR 2 NOT NULL step3 CHAR 2 NOT NULL .