Ağırlıksız yönlendirilmiş bir grafikte iki düğüm arasındaki en kısa yolu belirlemek için kenar komşuluğuyla temsil edilen bir yaklaşım formüle edin, prosedürel uzantıları olmayan tam olarak ANSI SQL yeniden yapılanım CTE'leri kullanarak?

Sorunun cevabı

Sorunun geçmişi

Graf keşif algoritmaları geleneksel olarak Python veya Java gibi uygulama dillerinin alanı olmuştur; NetworkX veya JGraphT gibi kütüphaneler kullanarak. Ancak, SQL:1999 standardında yeniden yapılanım ortak tablo ifadelerinin (CTE) ortaya çıkmasıyla, SQL hiyerarşik ve yeniden yapılanımlı sorgulama için Turing-tamamlayıcı yetenekler kazandı. Bu evrim, ANSI SQL'i yalnızca bir veri alma dilinden, veritabanı katmanında karmaşık hesaplama geometrisi ve grafik teorisi problemlerini doğrudan çözebilen bir platform haline dönüştürdü; veri hareketini minimize etti ve küme tabanlı optimizasyonu artırdı.

Problem

Ağırlıksız bir grafikte en kısa yolu belirlemek, bir kaynak düğüm ile bir hedef düğüm arasındaki minimum kenar sayısını bulmayı gerektirir. Ağaç yapılarının aksine, grafiklerde döngüler bulunur; bu da sonsuz yeniden yapımayı önlemek için döngü tespitinin gerekliliğini doğurur. Zorluk, prosedürel ve kuyruk tabanlı olan Genişlik-Öncelikli Arama (BFS) mantığını, belirgin döngü yapıları veya değişkenler olmadan, tam olarak ANSI SQL sözdiziminde, mülkiyet uzantılarına (örneğin Oracle'ın CONNECT BY veya SQL Server'ın prosedürel seçenekleri) tabi olmadan uygulamaktır.

Çözüm

Çözüm, BFS'yi seviye seviye keşfetmeyi simüle eden bir yeniden yapılanım CTE kullanmaktadır. Temel üye, aramayı kaynak düğümden başlatır. Yeniden yapılanım üyesi, komşuları keşfetmek için kenar tablosu ile birleştirilir ve bir yol uzunluğu sayacı artırılır. Kritik olarak, döngüleri tespit etmek ve düğümlerin yeniden ziyaret edilmesini önlemek için bir ziyaret edilen yol izleme dizesi korunur. Yeniden yapılandırma, hedefe ulaşıldığında veya yeni düğümler keşfedilmediğinde sonlandırılır. ANSI SQL standardı, CYCLE ifadesi veya CTE içindeki manuel izleme kullanarak açık döngü tespitini destekler.

WITH RECURSIVE path_finder (
    current_node, 
    path_length, 
    visited_path
) AS (
    -- Temel: kaynak noktasından başla
    SELECT 
        source_node, 
        0, 
        CAST(source_node AS VARCHAR(1000))
    FROM edges
    WHERE source_node = 'A'
    
    UNION ALL
    
    -- Yeniden yapılanım: komşuları keşfet
    SELECT 
        e.target_node,
        pf.path_length + 1,
        CAST(pf.visited_path || '->' || e.target_node AS VARCHAR(1000))
    FROM path_finder pf
    JOIN edges e ON pf.current_node = e.source_node
    WHERE POSITION(e.target_node IN pf.visited_path) = 0
      AND pf.path_length < 100  -- Güvenlik limit
)
SELECT path_length, visited_path
FROM path_finder
WHERE current_node = 'Z'
ORDER BY path_length
FETCH FIRST 1 ROW ONLY;

Hayattan bir durum

Problem tanımı

Bir lojistik şirketi, depolama bölgeleri arasındaki izin verilen yolları yönlendirilmiş kenarlar olarak izleyen bir ilişkisel veritabanı aracılığıyla depo robotu navigasyon sistemini yönetmektedir. Operasyon ekibi, robotlar için herhangi iki bölge arasında en iyi (en kısa) rotayı belirlemek amacıyla kesintisiz bir sorguya ihtiyaç duymaktaydı. Kısıtlama katıydı: çözüm, dış mikro hizmetler veya Neo4j gibi grafik veritabanları kullanmadan mevcut PostgreSQL kümesinde çalışmalıydı, çünkü gecikme gereksinimleri ve mimari basitlik zorunluluğu vardı.

Farklı çözümler değerlendirildi

Çözüm 1: Uygulama katmanında BFS ile Python

Ekip, en kısa yolları hesaplamak için kenar verilerini bir Python servisine aktarmayı düşündü. Bu, zengin algoritmik kütüphaneler ve basit uygulama sağlasa da, veritabanı ile uygulama sunucusu arasında önemli bir ağ gecikmesi getirdi. Ayrıca, veri çoğaltılması gerektirdiği için tek kaynak ilkesini ihlal etti ve ağ bölünmeleri sırasında bir potansiyel hata noktası yarattı.

Çözüm 2: Prosedürel SQL ile saklanmış prosedür

Değişkenler ve döngülerle kuyruk tabanlı BFS uygulamak için PL/pgSQL (PostgreSQL'in prosedürel dili) kullanarak bir saklanmış prosedür yazmayı değerlendirdiler. Bu, ağ gecikmesini ortadan kaldırdı ama taşınabilirliği tehlikeye attı ve ANSI SQL standart gereksinimini ihlal etti; onları PostgreSQL'e özgü sözdizimine kilitledi. Bu yaklaşım ayrıca grafik keşfindeki kenar durumları için karmaşık hata işleme gerektirdi.

Çözüm 3: Tam ANSI SQL yeniden yapılanım CTE

Seçilen yaklaşım, yol izleme ile seviye sınırlı BFS uygulayan bir yeniden yapılanım CTE kullanıyordu. Bu, veritabanı sorgu optimizasyon mühendisinin birleştirme işlemlerini paralelleştirme yeteneğinden yararlanarak tamamen SQL motoru içinde gerçekleştirildi. Bu yaklaşım, veritabanı taşınabilirliği için katı ANSI uyumunu sağladı, ağ üzerindeki yükü ortadan kaldırdı ve küme tabanlı performans optimizasyonlarını kullandı.

Seçilen çözüm ve neden

Ekip, mevcut veritabanı kümesinde çalışan katı mimari kısıtlamalarını karşıladığı için Çözüm 3'ü seçti ve tedarikçi bağımsızlığını sürdürdü. ANSI SQL yaklaşımı ek altyapı gereksinimini ortadan kaldırdı ve 10.000+'den fazla kenar içeren grafiklerde alt milisaniye sorgu performansı sağladı. Çözüm, sorgunun doğrudan robot dağıtım API'nin JDBC çağrılarına gömülmesine olanak tanıdı; ara katmanlar olmadan.

Sonuç

Uygulama, ortalama yanıt süreleri 5ms'in altında olan 500+'den fazla eşzamanlı robot talebi için en kısa yolları başarıyla hesapladı. Lojistik şirketi daha sonra veritabanını PostgreSQL'den EnterpriseDB'ye geçirdi; sorgu mantığını değiştirmeden taşınabilirlik faydalarını doğruladı. Çözüm, tedarik zinciri ağlarındaki döngüsel bağımlılık tespiti de dahil olmak üzere organizasyon içindeki diğer grafik tabanlı sorgular için bir şablon haline geldi.

Adayların genellikle gözden kaçırdıkları şey

SQL standart sürümü CYCLE ifadesini desteklemiyorsa döngüsel grafikte sonsuz yeniden yapıma nasıl engel olursunuz?

Adaylar sık sık, daha eski ANSI SQL uygulamalarının SEARCH ve CYCLE ifadelerini içermediğini gözden kaçırıyor. Çözüm, yeni bir düğüm eklemeden önce, sorgunun, önceki tespit edilmiş yol dizisinde önerilen düğümün olmadığını doğrulamayı gerektirerek, yeniden yapılanım CTE içinde ziyaret edilen düğümlerin belirlenmiş bir dizesini veya dizisini koruyarak manuel döngü tespitini içerir. Ayırıcı karakterlerin dikkatli bir şekilde işlenmesi gereklidir; bu, '11' düğümünün '111' içinde yeterli bölücüler olmadan tespit edilmesine neden olabilir. Ayrıca, adaylar sık sık derin bağlantılı grafiklerde gereksiz yeniden yapıma karşı bir derinlik sınırlayıcısını içermeyi unutur.

Neden basit bir yeniden yapılanım birleştirmesi olarak yazılan yeniden yapılanım CTE yaklaşımı, seviye sıralaması olmadan potansiyel olarak optimal olmayan sonuçlar dönebilir?

Birçok aday, yeniden yapılanım adımını basit bir birleştirme olarak uygular; ancak, ANSI SQL yeniden yapılanım CTE'lerinin varsayılan olarak derinlik öncelikli arama (DFS) gerçekleştirdiğini anlamıyor. Ağırlıksız grafikler için en kısa yol sorunlarında, BFS bulunan ilk çözümün optimal olacağını garanti ederken, DFS daha uzun yolu önce bulabilir. Kaçırılan kritik ayrıntı, yeniden yapıma derinlik sınırlaması koymadan veya ilk eşleşmede duracak bir seviye sayacı kullanmadan sorgunun gereksiz yere üstel büyüyen yolları inceleyebileceğidir.

Bir yeniden yapılanım CTE'de eşit uzunluktaki birden fazla yol üzerinden aynı düğüme erişimin performans düşüklüğünü nasıl ele alırsınız?

Adaylar sık sık SQL içindeki gereksiz yol eliminasyonu kavramını gözden kaçırırlar. Uygun bir şekilde işlenmediği takdirde, yeniden yapılanım CTE her olası yolu ayrı satırlar olarak üretecek ve sonuç kümelerinde üstel büyümeye yol açacaktır. Çözüm, düğüm başına yol uzunluğuna göre sıralanmış ROW_NUMBER() gibi bir pencere işlevi kullanarak her ara düğüme en kısa yolun yalnızca her yinelemede korunmasını gerektirmektedir. Bu optimizasyon, ara sonuç kümesinin gereksiz yere büyümesini önler; böylece, her yeniden ziyaret edilen düğüme karşı daha uzun yollar hemen atılır ve nihai seçim aşamasında değil.