質問への回答

質問の歴史

グラフ探索アルゴリズムは伝統的に、PythonやJavaといったアプリケーション言語の領域であり、NetworkXやJGraphTのようなライブラリを利用していました。しかし、SQL:1999標準で再帰的共通テーブル式（CTE）が登場したことで、SQLは階層的および再帰的なクエリのためのチューリング完全な機能を持つこととなり、この進化によりANSI SQLは単なるデータ取得言語から、データベース層内で複雑な計算幾何学やグラフ理論の問題を直接解決できるプラットフォームへと変貌しました。

問題

無重みのグラフにおいて最短経路を決定するには、ソースノードとターゲットノード間のエッジの最小数を見つける必要があります。木構造とは異なり、グラフにはサイクルが含まれるため、無限再帰を防ぐためのサイクル検出が必要です。課題は、明示的なループ構造や可変変数なしで、手続き的でキューに基づく方式の幅優先探索（BFS）ロジックを宣言的で集合ベースのパラダイムに実装することです。ANSI SQL構文に厳密に従い、OracleのCONNECT BYやSQL Serverの手続きオプションのようなプロプライエタリな拡張を禁止する必要があります。

解決策

この解決策は再帰的CTEを利用して、BFSのレベル別探索をシミュレートします。アンカーメンバーがソースノードから検索を初期化します。再帰メンバーはエッジテーブルと結合して隣接ノードを発見し、パス長カウンタを増加させます。重要なことに、再訪問を防ぐためにサイクルトラッキング文字列が維持されます。再帰はターゲットが到達されたとき、または新しいノードが発見されなかったときに終了します。ANSI SQL標準は、CYCLE句を使用した明示的なサイクル検出またはCTE内での手動トラッキングをサポートしています。

WITH RECURSIVE path_finder (
    current_node, 
    path_length, 
    visited_path
) AS (
    -- アンカー：ソースから開始
    SELECT 
        source_node, 
        0, 
        CAST(source_node AS VARCHAR(1000))
    FROM edges
    WHERE source_node = 'A'
    
    UNION ALL
    
    -- 再帰：隣人を探索
    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  -- 安全制限
)
SELECT path_length, visited_path
FROM path_finder
WHERE current_node = 'Z'
ORDER BY path_length
FETCH FIRST 1 ROW ONLY;

実生活の状況

問題の説明

ある物流会社は、倉庫ロボットのナビゲーションシステムを管理するために、保管場所間の許可されるルートを有向エッジとして追跡するリレーショナルデータベースを使用していました。オペレーションチームは、バッテリー消費を最小限に抑えるために、任意の2つのベイ間のロボット向けに最適な（最短）ルートを決定するためのリアルタイムクエリが必要でした。制約は厳格で、解決策は既存のPostgreSQLクラスター上で実行され、外部マイクロサービスまたはNeo4jのようなグラフデータベースを展開することはできませんでした。

考慮された異なる解決策

解決策1：Pythonによるアプリケーション層でのBFS

チームは、エッジデータをPythonサービスにエクスポートし、NetworkXを使用して最短経路を計算することを検討しました。この方法は豊富なアルゴリズムライブラリと簡単な実装を提供しましたが、データベースとアプリケーションサーバの間に大幅なネットワーク遅延をもたらしました。さらに、データの複製が必要となり、単一の真実の原則に違反し、ネットワーク分割時に潜在的な障害点を作り出しました。

解決策2：手続き型SQLを使用したストアドプロシージャ

チームは、PL/pgSQL（PostgreSQLの手続き型言語）を使用して、可変変数とループを持つキュー型BFSを実装するストアドプロシージャの作成を評価しました。これによりネットワーク遅延が排除されましたが、ポータビリティが犠牲になり、ANSI SQL標準の要件に違反することになり、PostgreSQL固有の構文にロックされました。このアプローチは、グラフ探索におけるエッジケースのための複雑な例外処理も必要としました。

解決策3：純粋なANSI SQLの再帰的CTE

選択されたアプローチは、パストラッキングを行うレベル制限されたBFSを実装した再帰的CTEを利用しました。これにより、SQLエンジン内で完全に実行され、クエリオプティマイザの並列化能力を活用しました。このアプローチは、データベースのポータビリティを確保するために厳格なANSI準拠を保証し、ネットワークオーバーヘッドを排除し、集合ベースのパフォーマンス最適化を利用しました。

選択された解決策とその理由

チームは、既存のデータベースクラスター内で動作するという厳格なアーキテクチャの制約に適合し、ベンダーの独立性を維持できるため、解決策3を選択しました。ANSI SQLアプローチは、追加のインフラストラクチャを必要とせず、10,000以上のエッジを持つグラフでサブミリ秒のクエリ性能を達成しました。このソリューションにより、クエリはロボット派遣APIのJDBC呼び出しに直接組み込むことができ、中間層を排除しました。

結果

この実装により、500以上の同時ロボットリクエストに対して1秒あたりの平均応答時間が5ms未満で、最短経路が成功裏に計算されました。物流会社はその後、クエリロジックを変更することなく、PostgreSQLからEnterpriseDBにデータベースを移行しました。これにより、ポータビリティの利点が検証されました。このソリューションは、サプライチェーンネットワークにおける循環依存関係の検出を含む、組織内の他のグラフベースのクエリのテンプレートとなりました。

候補者がしばしば見落とすこと

SQL標準のバージョンがCYCLE句をサポートしていない場合、サイクルグラフにおける無限再帰をどのように防ぐか？

候補者は、古いANSI SQL実装にはSEARCHおよびCYCLE句が欠けている可能性があることを見落とすことがよくあります。この解決策は、再帰CTE内の訪問済みノードの区切られた文字列または配列を維持することによる手動サイクル検出を含みます。新しいノードを追加する前に、クエリはその候補ノードが累積されたパス文字列内に既に存在しないことを文字列関数のPOSITIONを使用して確認する必要があります。これには、ノード'11'が適切な区切りなしに'111'内で検出されるのを防ぐために、区切り文字の扱いに注意が必要です。さらに、候補者は深さ制限を含め忘れることがあり、深く接続されたグラフにおける暴走する再帰からの保護策となります。

なぜ、単純な再帰的結合として書かれた場合、最短経路への再帰的CTEアプローチが潜在的に最適でない結果を返す可能性があるのか？

多くの候補者は、再帰的ステップを単純な結合として実装し、ANSI SQLの再帰CTEがデフォルトで深さ優先探索（DFS）を行うこと、幅優先探索（BFS）ではないことを理解していません。無重みグラフの最短経路問題において、BFSは最初に見つけた解が最適であることを保証しますが、DFSはより長い経路を最初に見つけるかもしれません。この詳細は見落とされがちであり、再帰深度を制限したり、最初の一致で停止するためのレベルカウンタを使用しない場合、クエリは無駄に指数的に成長するパスを探索する可能性があります。

同じノードが同じ長さの複数の経路を介して到達可能な場合、再帰的CTEにおけるパフォーマンス劣化をどのように処理するか？

候補者は、SQLでの冗長パス排除の概念を頻繁に見落とします。適切な処理が行われない場合、再帰CTEは中間ノードへのすべての可能なパスのために別々の行を生成し、結果セットが指数成長します。この解決策は、ROW_NUMBER()のようなウィンドウ関数を使用し、ノードごとにパス長で順序付けて、各イテレーションで中間ノードへの最短パスのみを保持します。この最適化により、中間の結果セットが膨張しないようにし、最終的な選択段階ではなく、すぐに既に訪問されたノードへの長い経路を排除します。

無重みの有向グラフにおける2つのノード間の最短経路を、手続き型拡張なしにANSI SQLの再帰的CTEを使用して決定するアプローチを定式化せよ。