Chọn hai hàng tuân theo quy tắc

Question

Tôi có một bảng lớn (1M hàng) với các cột sau: nguồn, dest, khoảng cách. Mỗi hàng xác định một liên kết (từ A đến B).

Tôi cần tìm khoảng cách giữa một cặp bằng nút anoter. Ví dụ: Nếu muốn tìm khoảng cách giữa A và B, Nếu tôi tìm thấy nút x và có: x -> A x -> B Tôi có thể thêm khoảng cách này và có khoảng cách giữa A và B Câu hỏi của tôi: Làm cách nào tôi có thể tìm thấy tất cả các nút (chẳng hạn như x) và nhận khoảng cách của chúng đến (A và B)? Mục đích của tôi là chọn giá trị tối thiểu của khoảng cách.

P.s: A và B chỉ là một kết nối (tôi cần thực hiện nó cho kết nối 100K). Cảm ơn!

Answer 1

Giả sử bạn muốn lấy đường dẫn từ A-B với nhiều bước trung gian, bạn không thể thực hiện điều đó trong SQL thuần túy trong một số bước không xác định. Đơn giản chỉ cần đặt, nó thiếu sức mạnh biểu cảm, xem http://en.wikipedia.org/wiki/Expressive_power#Expressive_power_in_database_theory. Như Andomar đã nói, tải dữ liệu vào một quy trình và thuật toán của chúng tôi là Djikstra.

Answer 2

Điều này nghe có vẻ như là traveling salesman problem.

Từ quan điểm cú pháp SQL: connect by prior sẽ xây dựng cây của bạn sau khi sử dụng bắt đầu và giới hạn số lớp mà nó có thể đi qua; tuy nhiên, việc làm sẽ không đảm bảo mức tối thiểu.

Answer 3

Tôi có thể bị giảm giá cho điều này, nhưng tôi thấy đây là một vấn đề thú vị. Tôi ước rằng đây có thể là một cuộc thảo luận cởi mở hơn, vì tôi nghĩ rằng tôi có thể học được rất nhiều từ điều này.

Có vẻ như có thể đạt được điều này bằng cách thực hiện nhiều câu lệnh chọn - chẳng hạn như SELECT id FROM mytable WHERE source="A" ORDER BY distance ASC LIMIT 1. Gói một cái gì đó như thế này trong một vòng lặp trong khi, và thay thế "A" với một biến id, sẽ làm các trick, không?

Ví dụ (A là nguồn, B là điểm đến cuối cùng):

DECLARE var_id as INT 
WHILE var_id != 'B' 
    BEGIN 
    SELECT id INTO var_id FROM mytable WHERE source="A" ORDER BY distance ASC LIMIT 1 
    SELECT var_id 
    END 

Sẽ không phải cái gì đó như công việc này? (Các mã là cẩu thả, nhưng ý tưởng có vẻ như âm thanh.) Bình luận được chào đón nhiều hơn.

Answer 4

Tham gia bảng với chính nó với đích được kết nối với nguồn. Thêm khoảng cách từ hai liên kết. Chèn nó dưới dạng một liên kết mới với nguồn bên trái, đích bên phải và tổng khoảng cách nếu không có trong bảng. Nếu đó là trong bảng nhưng với tổng khoảng cách ngắn hơn thì hãy cập nhật hàng hiện tại với khoảng cách ngắn hơn.

Lặp lại bước này cho đến khi bạn không thêm liên kết mới nào vào bảng và không có cập nhật nào có khoảng cách ngắn hơn. Bảng của bạn hiện chứa liên kết cho mọi kết hợp có thể có của nguồn và đích với khoảng cách tối thiểu giữa chúng. Nó sẽ là thú vị để xem có bao nhiêu sự lặp lại này sẽ mất.

Điều này sẽ không theo dõi đường dẫn trung gian giữa nguồn và đích nhưng chỉ cung cấp khoảng cách ngắn nhất.

Answer 5

Như Andomar nói, bạn sẽ cần thuật toán của Dijkstra, đây là một liên kết đến rằng thuật toán trong T-SQL: T-SQL Dijkstra's Algorithm

Answer 6

IIUC này nên làm, nhưng tôi không chắc chắn nếu điều này là thực sự khả thi (hiệu suất -wise) do số lượng lớn các hàng tham gia và đến CROSS JOIN

SELECT 
    t1.src AS A, 
    t1.dest AS x, 
    t2.dest AS B, 
    t1.distance + t2.distance AS total_distance 
FROM 
    big_table AS t1 
CROSS JOIN 
    big_table AS t2 ON t1.dst = t2.src 
WHERE 
    A = 'insert source (A) here' AND 
    B = 'insert destination (B) here' 
ORDER BY 
    total_distance ASC 
LIMIT 
    1 

đoạn trên sẽ làm việc đối với trường hợp trong đó bạn có hai hàng dưới hình thức A-> x và x-> B nhưng không cho các kết hợp khác (ví dụ A-> x và B-> x). Việc mở rộng nó để bao gồm tất cả bốn sự kết hợp sẽ là tầm thường (ví dụ: tạo một khung nhìn sao chép mỗi hàng và hoán đổi src và dest).