Home
%3CLINGO-SUB%20id%3D%22lingo-sub-721240%22%20slang%3D%22en-US%22%3EPublic%20Preview%20of%20Shortest%20Path%20on%20SQL%20Server%202019%3C%2FLINGO-SUB%3E%3CLINGO-BODY%20id%3D%22lingo-body-721240%22%20slang%3D%22en-US%22%3E%3CP%3ESQL%20Server%202017%20and%20Azure%20SQL%20Database%20introduced%20%3CA%20href%3D%22https%3A%2F%2Fdocs.microsoft.com%2Fen-us%2Fsql%2Frelational-databases%2Fgraphs%2Fsql-graph-overview%3Fview%3Dsql-server-2017%22%20target%3D%22_blank%22%20rel%3D%22noopener%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%22%3Enative%20graph%20database%20capabilities%3C%2FA%3E%20used%20to%20model%20many-to-many%20relationships.%20The%20first%20implementation%20of%20SQL%20Graph%20introduced%20support%20for%20nodes%20to%20represent%20entities%2C%20edges%20to%20represent%20relationships%20and%20a%20new%20MATCH%20predicate%20to%20support%20graph%20pattern%20matching%20and%20traversal.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EWe%20are%20expanding%20the%20graph%20database%20capabilities%20with%20several%20new%20features.%20In%20this%20blog%20we%20discuss%20one%20of%20these%20features%20that%20is%20now%20available%20for%20public%20preview%20in%20%3CA%20href%3D%22https%3A%2F%2Fwww.microsoft.com%2Fen-us%2Fsql-server%2Fsql-server-2019%22%20target%3D%22_blank%22%20rel%3D%22noopener%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%22%3ESQL%20Server%202019%3C%2FA%3E%2C%20%3CSTRONG%3EShortest%20Path%3C%2FSTRONG%3E%2C%20which%20can%20be%20used%20to%20find%20a%20shortest%20path%20between%20two%20nodes%20in%26nbsp%3Ba%20graph.%20The%20shortest%20path%20function%20can%20also%20be%20used%20to%20compute%20a%20transitive%20closure%20or%20for%20arbitrary%20length%20traversals.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EWith%20CTP3.1%2C%20we%20are%20introducing%20a%20new%20function%20SHORTEST_PATH%2C%20which%20can%20be%20used%20inside%20MATCH%20to%20find%20a%20shortest%20path%20between%20any%202%20nodes%20in%20a%20graph%20or%20to%20perform%20arbitrary%20length%20traversals.%20Users%20can%20specify%20a%20pattern%20they%20would%20like%20to%20search%20for%20in%20the%20graph%20using%20a%20regular%20expression%20style%20syntax.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3ETo%20understand%20the%20new%20syntax%20and%20how%20shortest%20path%20works%2C%20from%20Adventure%20Works%20Cycles%2C%20a%20bicycle%20wholesaler%20that%20sells%20and%20manufactures%20bicycles.%20We%20have%20converted%20their%20bill%20of%20materials%20hierarchy%20into%20a%20graph%2C%20which%20has%20Product%20node%20and%20IsPartOf%20edge%20table.%20Download%20sample%20scripts%20%3CA%20href%3D%22https%3A%2F%2Fgithub.com%2Fmicrosoft%2Fsql-server-samples%2Ftree%2Fmaster%2Fsamples%2Ffeatures%2Fsql-graph%2FShortestPath%22%20target%3D%22_blank%22%20rel%3D%22noopener%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%22%3Ehere%3C%2FA%3E.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%20style%3D%22text-align%3A%20center%3B%22%3E%3CSPAN%20class%3D%22lia-inline-image-display-wrapper%20lia-image-align-inline%22%20style%3D%22width%3A%20400px%3B%22%3E%3CIMG%20src%3D%22https%3A%2F%2Fgxcuf89792.i.lithium.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F120664i2D33EBEBCE319DE4%2Fimage-size%2Fmedium%3Fv%3D1.0%26amp%3Bpx%3D400%22%20alt%3D%22AdventureWorksBOM.png%22%20title%3D%22AdventureWorksBOM.png%22%20%2F%3E%3C%2FSPAN%3E%3C%2FP%3E%0A%3CP%3ENow%2C%20let%E2%80%99s%20look%20at%20some%20sample%20queries%20to%20see%20how%20shortest%20path%20can%20help%20with%20recursive%20or%20arbitrary%20length%20traversals%20in%20a%20graph%20schema.%20%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%224%22%20color%3D%22%23003366%22%3E%3CSTRONG%3EFind%20all%20assemblies%20where%20a%20given%20product%20is%20used%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3EImagine%20that%20the%20inventory%20of%20a%20given%20product%20(Bearing%20Ball)%20at%20Adventure%20Works%20Cycles%20is%20running%20low%20and%20that%20they%20would%20like%20to%20find%20all%20the%20assemblies%20in%20their%20manufacturing%20pipeline%2C%20where%20a%20Bearing%20Ball%20is%20used.%20This%20will%20tell%20them%20what%20assemblies%20will%20be%20affected%20due%20to%20the%20scarcity%20of%20a%20given%20product.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EThe%20following%20query%20demonstrates%20how%20shortest%20path%20can%20be%20used%20to%20find%20all%20assemblies%20that%20require%20a%20Bearing%20Ball%20in%20the%20bill%20of%20materials%3A%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CPRE%3E--%20Find%20all%20the%20assemblies%20where%20Bearing%20Ball%20is%20used%0ASELECT%20%0A%20P1.ProductID%2C%20%0A%20P1.Name%2C%0A%20%3CSTRONG%3ESTRING_AGG%3C%2FSTRONG%3E(P2.Name%2C'-%26gt%3B')%20%3CSTRONG%3EWITHIN%20GROUP%20(GRAPH%20PATH)%3C%2FSTRONG%3E%20AS%20%5BAssembly%5D%2C%0A%20%3CSTRONG%3ELAST_VALUE%3C%2FSTRONG%3E(P2.ProductID)%20%3CSTRONG%3EWITHIN%20GROUP%20(GRAPH%20PATH)%3C%2FSTRONG%3E%20AS%20%5BFinal%20ProductID%5D%0AFROM%0A%20PRODUCT%20P1%2C%0A%20PRODUCT%20FOR%20PATH%20P2%2C%0A%20ISPARTOF%20FOR%20PATH%20IPO%0AWHERE%20%0A%20MATCH(%3CSTRONG%3ESHORTEST_PATH(P1(-(IPO)-%26gt%3BP2)%2B)%3C%2FSTRONG%3E)%0A%20AND%20P1.ProductID%20%3D%202%0A%20%20%20%20%20%20%20ORDER%20BY%20P1.ProductID%20%0A%3C%2FPRE%3E%0A%3CP%20style%3D%22text-align%3A%20left%3B%22%20dir%3D%22ltr%22%3EThis%20query%20starts%20from%20ProductID%20%3D%202%20(Bearing%20Ball)%20and%20keeps%20traversing%20up%20the%20BOM%20tree%20until%20it%20finds%20all%20products%20that%20contain%20a%20Bearing%20Ball.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EHere%20are%20first%20few%20lines%20from%20the%20result%20set%3A%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%3CSPAN%20class%3D%22lia-inline-image-display-wrapper%20lia-image-align-inline%22%20style%3D%22width%3A%20400px%3B%22%3E%3CIMG%20src%3D%22https%3A%2F%2Fgxcuf89792.i.lithium.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F120667iC55678AD8D592C37%2Fimage-size%2Fmedium%3Fv%3D1.0%26amp%3Bpx%3D400%22%20alt%3D%22image.png%22%20title%3D%22image.png%22%20%2F%3E%3C%2FSPAN%3E%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EThe%20STRING_AGG%20function%20on%20P2.Name%20fetches%20all%20the%20nodes%20that%20were%20traversed%20in%20this%20path%2C%20thereby%2C%20giving%20us%20a%20good%20view%20of%20assembly%20line%20up%20to%20%E2%80%98Touring-3000%20Yellow%2C%2058%E2%80%99%20bike.%20Other%20rows%20in%20the%20result%20set%20show%20the%20other%20assemblies%20which%20have%20dependency%20on%20Bearing%20Ball%20at%20some%20level.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EThis%20query%20uses%20a%20lot%20of%20new%20syntax.%20Let%E2%80%99s%20understand%20what%20this%20new%20syntax%20does.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%223%22%20color%3D%22%23333399%22%3E%3CSTRONG%3ESHORTEST_PATH%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3EThe%20SHORTEST_PATH%20function%20lets%20you%20find%3A%3C%2FP%3E%0A%3COL%3E%0A%3CLI%3EA%20shortest%20path%20between%20two%20given%20nodes%2Fentities%3C%2FLI%3E%0A%3CLI%3ESingle%20source%20shortest%20path(s).%3C%2FLI%3E%0A%3CLI%3EShortest%20path%20from%20multiple%20source%20nodes%20to%20multiple%20target%20nodes.%3C%2FLI%3E%0A%3C%2FOL%3E%0A%3CP%3EIt%20takes%20an%20arbitrary%20length%20pattern%20as%20input%2C%20described%20below.%20It%20returns%20a%20shortest%20path%20that%20exists%20between%20two%20nodes.%26nbsp%3BThis%20function%20can%20only%20be%20used%20inside%20MATCH.%20It%20accepts%20an%20arbitrary%20length%20pattern%20and%20finds%20a%20shortest%20path%20in%20the%20graph%2C%20which%20matches%20that%20pattern.%20If%20there%20exist%20two%20or%20more%20shortest%20paths%20of%20the%20same%20length%20between%20any%20pair%20of%20source%20and%20destination%20node(s)%2C%20the%20function%20will%20return%20the%20one%20that%20was%20found%20first%20during%20traversal.%20Note%20that%2C%20an%20arbitrary%20length%20pattern%20can%20only%20be%20specified%20inside%20a%20SHORTEST_PATH%20function.%20Finding%20weighted%20shortest%20paths%2C%20all%20paths%20or%20all%20shortest%20paths%20is%20not%20supported%20yet.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%223%22%20color%3D%22%23333399%22%3E%3CSTRONG%3EArbitrary%20Length%20Pattern%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3EThis%20pattern%20includes%20the%20nodes%20and%20edges%20that%20must%20be%20traversed%20repeatedly%20until%20the%20desired%20node%20is%20reached%20or%20until%20the%20maximum%20number%20of%20iterations%20as%20specified%20in%20the%20pattern%20is%20met.%20Each%20time%20the%20query%20is%20executed%2C%20the%20result%20of%20executing%20this%20pattern%20will%20be%20a%20collection%20of%20nodes%20and%20edges%20traversed%20along%20the%20path%20from%20the%20start%20node%20to%20the%20end%20node.%20This%20is%20a%20regular%20expression%20style%20syntax%20pattern%20and%20the%20following%20two%20pattern%20quantifiers%20are%20supported%20in%20this%20release%3A%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CSTRONG%3E%E2%80%98%2B%E2%80%99%26nbsp%3B%3C%2FSTRONG%3E%20%3A%26nbsp%3B%26nbsp%3B%20Repeat%20the%20pattern%201%20or%20more%20times.%20Terminate%20as%20soon%20as%20a%20shortest%20path%20is%20found.%3C%2FP%3E%0A%3CP%20dir%3D%22ltr%22%3EWe%20recommend%20that%20users%20provide%20a%20start%20and%20an%20end%20node%2C%20along%20with%20the%20pattern%2C%20whenever%20%E2%80%98%2B%E2%80%99%20is%20used%20in%20the%20pattern%20predicate.%20For%20a%20big%20graph%2C%20a%20query%20with%20%E2%80%98%2B%E2%80%99%20and%20no%20terminating%20condition%20may%20take%20a%20long%20time%20to%20finish.%20Refer%20to%20the%20example%20shown%20in%20%E2%80%98Find%20Shortest%20path%20between%202%20given%20nodes%E2%80%99%20section%20below%2C%20to%20see%20how%20filters%20on%20start%20and%20end%20node%20can%20be%20applied.%3C%2FP%3E%0A%3CP%3E%3CSTRONG%3E%7B1%2Cn%7D%3C%2FSTRONG%3E%20%3A%20Repeat%20the%20pattern%201%20to%20%E2%80%98n%E2%80%99%20times.%20Terminate%20as%20soon%20as%20a%20shortest%20%26nbsp%3Bis%20found%20or%20when%20the%20max%20number%20of%20iterations%20%E2%80%98n%E2%80%99%20specified%20in%20the%20pattern%20is%20reached.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%223%22%20color%3D%22%23333399%22%3E%3CSTRONG%3EFOR%20PATH%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3EFOR%20PATH%20must%20be%20used%20with%20any%20node%20or%20edge%20table%20name%20in%20the%20FROM%20clause%2C%20which%20will%20participate%20in%20an%20arbitrary%20length%20pattern.%20FOR%20PATH%20tells%20the%20engine%20that%20the%20node%20or%20edge%20table%20will%20return%20an%20ordered%20collection%20representing%20the%20list%20of%20nodes%20or%20edges%20along%20the%20path%20from%20the%20start%20node%20to%20the%20end%20node.%20The%20attributes%20from%20these%20tables%20cannot%20be%20projected%20directly%20in%20the%20SELECT%20clause%20and%20cannot%20be%20filtered%20directly%20in%20the%20WHERE%20clause.%20To%20project%20or%20filter%20attributes%20from%20these%20tables%2C%20%3CSPAN%3E%3CSTRONG%3Egraph%20path%20aggregate%20functions%3C%2FSTRONG%3E%3C%2FSPAN%3E%20must%20be%20used.%3C%2FP%3E%0A%3CP%3E%3CSTRONG%3E%26nbsp%3B%3C%2FSTRONG%3E%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%223%22%20color%3D%22%23333399%22%3E%3CSTRONG%3EGraph%20Path%20Aggregate%20Functions%20%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3ESince%20the%20nodes%20and%20edges%20involved%20in%20arbitrary%20length%20pattern%20return%20a%20collection%20(of%20node(s)%20and%20edge(s)%20traversed%20in%20that%20path)%2C%20users%20cannot%20project%20the%20attributes%20directly%20using%20the%20conventional%20tablename.attributename%20syntax.%20For%20queries%20where%20it%20is%20required%20to%20project%20attribute%20values%20from%20the%20intermediate%20node%20or%20edge%20tables%2C%20in%20the%20path%20traversed%2C%20we%20have%20extended%20aggregate%20functions%20to%20work%20with%20graph%20node%20or%20edge%20tables.%20In%20this%20release%2C%20the%20following%20graph%20path%20aggregate%20functions%20are%20available%3A%20STRING_AGG%2C%20LAST_VALUE%2C%20SUM%2C%20AVG%2C%20MIN%2C%20MAX%20and%20COUNT.%26nbsp%3BThese%20functions%20can%20be%20used%20in%20SELECT%20or%20ORDER%20BY%20clause.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%224%22%20color%3D%22%23000080%22%3E%3CSTRONG%3EFind%20all%20the%20products%20which%20are%20up%20to%203%20levels%20away%20from%20a%20given%20product.%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3ENow%2C%20if%20Adventure%20Works%20Cycles%20wants%20to%20find%20products%20in%20their%20BOM%2C%20which%20are%201%20to%203%20levels%20away%20from%20Bearing%20Ball%2C%20they%20can%20just%20modify%20the%20query%20shown%20in%20example%20above%20as%20follows%3A%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CPRE%3ESELECT%20%0A%20P1.ProductID%2C%20%0A%20P1.Name%2C%0A%20STRING_AGG(P2.Name%2C'-%26gt%3B')%20WITHIN%20GROUP%20(GRAPH%20PATH)%20AS%20%5BAssembly%5D%2C%0A%20LAST_VALUE(P2.ProductID)%20WITHIN%20GROUP%20(GRAPH%20PATH)%20AS%20%5BFinal%20ProductID%5D%0AFROM%0A%20PRODUCT%20P1%2C%0A%20PRODUCT%20FOR%20PATH%20P2%2C%0A%20ISPARTOF%20FOR%20PATH%20IPO%0AWHERE%20%0A%20MATCH(SHORTEST_PATH(P1(-(IPO)-%26gt%3BP2)%7B1%2C3%7D))%0A%20AND%20P1.ProductID%20%3D%202%0AORDER%20BY%20P1.ProductID%20%0A%3C%2FPRE%3E%0A%3CP%3EHere%20is%20a%20sample%20result%20set%3A%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%3CSPAN%20class%3D%22lia-inline-image-display-wrapper%20lia-image-align-inline%22%20style%3D%22width%3A%20400px%3B%22%3E%3CIMG%20src%3D%22https%3A%2F%2Fgxcuf89792.i.lithium.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F120668i56178D07780BFA1C%2Fimage-size%2Fmedium%3Fv%3D1.0%26amp%3Bpx%3D400%22%20alt%3D%22image.png%22%20title%3D%22image.png%22%20%2F%3E%3C%2FSPAN%3E%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%224%22%20color%3D%22%23000080%22%3E%3CSTRONG%3EFind%20Shortest%20Path%20between%202%20given%20nodes%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3EThe%20queries%20shown%20above%2C%20start%20from%20a%20given%20node%20(Bearing%20Ball)%20and%20then%20search%20all%20paths%20in%20the%20graph%20starting%20from%20that%20node%2C%20until%20they%20cannot%20find%20any%20other%20paths%20that%20originate%20from%20this%20node%20and%20end%20at%20other%20nodes.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EImagine%20that%20Adventure%20Works%20Cycles%20wants%20to%20find%20the%20shortest%20path%20between%202%20given%20nodes%20in%20the%20assembly.%20They%20can%20use%20following%20query%20to%20do%20this.%20This%20query%20will%20again%20start%20at%20ProductID%20%3D%202%20(Bearing%20Ball)%20but%20terminates%20as%20soon%20as%20it%20finds%20ProductID%20%3D%20768%20(bike%20%E2%80%98Road-650%20Black%2C%2044%E2%80%99).%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CPRE%3ESELECT%0A%20ProductID%2C%20Name%2C%20%5BAssembly%5D%2C%20FinalProductID%2C%20Levels%0AFROM%20(%0A%20SELECT%20%0A%20%20P1.ProductID%2C%20%0A%20%20P1.Name%2C%0A%20%20STRING_AGG(P2.Name%2C'-%26gt%3B')%20WITHIN%20GROUP%20(GRAPH%20PATH)%20AS%20%5BAssembly%5D%2C%0A%20%20LAST_VALUE(P2.ProductID)%20WITHIN%20GROUP%20(GRAPH%20PATH)%20AS%20FinalProductID%2C%0A%20%20COUNT(P2.ProductID)%20WITHIN%20GROUP%20(GRAPH%20PATH)%20AS%20Levels%0A%20FROM%0A%20%20PRODUCT%20P1%2C%0A%20%20PRODUCT%20FOR%20PATH%20P2%2C%0A%20%20ISPARTOF%20FOR%20PATH%20IPO%0A%20WHERE%20%0A%20%20MATCH(SHORTEST_PATH(P1(-(IPO)-%26gt%3BP2)%2B))%0A%20%20AND%20P1.ProductID%20%3D%202%0A%20)%20AS%20Q%0A%20WHERE%20Q.FinalProductID%20%3D%20768%0A%3C%2FPRE%3E%0A%3CP%3ENote%20that%20in%20this%20query%2C%20we%20used%20a%20subquery%20to%20apply%20filter%20on%20the%20last%20node%20traversed%20in%20the%20path%20(FinalProductID%20%3D%20768).%20The%20filter%20on%20the%20FinalProductID%20in%20the%20outer%20query%20is%20pushed%20down%20while%20computing%20the%20shortest%20path.%20Hence%2C%20the%20query%20will%20terminate%20as%20soon%20as%20the%20FinalProductID%20is%20found.%20LAST_VALUE()%20function%2C%20which%20fetches%20the%20attribute%20values%20from%20last%20node%20traversed%2C%20cannot%20be%20used%20in%20the%20WHERE%20clause%2C%20since%20it%20is%20a%20window%20aggregate%20function.%20%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EBy%20using%20the%20COUNT%20graph%20path%20aggregate%20function%20in%20select%20clause%2C%20we%20can%20see%20the%20number%20of%20hops%2Flevels%20between%20the%202%20ProductIDs.%20Here%20is%20the%20result%20set%20of%20this%20query%3A%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%20%26nbsp%3B%20%26nbsp%3B%20%3CSPAN%20class%3D%22lia-inline-image-display-wrapper%20lia-image-align-inline%22%20style%3D%22width%3A%20400px%3B%22%3E%3CIMG%20src%3D%22https%3A%2F%2Fgxcuf89792.i.lithium.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F120669iC581621D0890231B%2Fimage-size%2Fmedium%3Fv%3D1.0%26amp%3Bpx%3D400%22%20alt%3D%22image.png%22%20title%3D%22image.png%22%20%2F%3E%3C%2FSPAN%3E%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3EIn%20this%20query%2C%20the%20predicate%2Ffilter%20on%20last%20node%20(Q.FinalProductID)%20is%20pushed%20down.%20That%20is%2C%20the%20shortest%20path%20query%20terminates%20as%20soon%20as%20it%20finds%20ProductID%20%3D%20768.%3C%2FP%3E%0A%3CP%3EWriting%20a%20shortest%20path%20query%20with%20a%20terminating%20condition%20on%20the%20last%20node%2C%20as%20shown%20in%20the%20query%20above%2C%20is%20highly%20recommended.%20This%20is%20a%20much%20more%20optimal%20query%20than%20the%20ones%20which%20start%20at%20one%20node%20and%20then%20traverse%20the%20entire%20graph%20to%20find%20all%20the%20connections%20that%20exist%20from%20that%20node%20to%20others.%20For%20huge%20graphs%2C%20finding%20the%20shortest%20path%20from%20a%20given%20start%20node%20to%20all%20the%20other%20nodes%20in%20the%20graph%2C%20will%20be%20a%20very%20expensive%20operation.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%224%22%20color%3D%22%23000080%22%3E%3CSTRONG%3EConclusion%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3EStarting%20with%20SQL%20Server%202019%20CTP3.1%2C%20you%20can%20use%20SHORTEST_PATH%20function%20to%20compute%20shortest%20path(s)%20between%20nodes%20in%20a%20graph%2C%20using%20a%20regular%20expression%20style%20search%20pattern.%20SHORTEST_PATH%20can%20only%20be%20used%20inside%20a%20MATCH%20function%20and%20works%20only%20with%20graph%20node%20and%20edge%20tables.%20This%20function%20also%20allows%20you%20to%20write%20transitive%20closure%20or%20arbitrary%20length%20traversal%20query%20from%20a%20given%20%E2%80%98start%E2%80%99%20node.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%0A%3CP%3E%3CFONT%20size%3D%223%22%20color%3D%22%23333399%22%3E%3CSTRONG%3ENext%20Steps%3C%2FSTRONG%3E%3C%2FFONT%3E%3C%2FP%3E%0A%3CP%3EPlease%20download%20and%20give%20this%20feature%20a%20try.%26nbsp%3B%20We%20are%20looking%20forward%20to%20hearing%20your%20comments%20or%20feedback%20for%20this%20feature.%3C%2FP%3E%0A%3CP%3E%26nbsp%3B%3C%2FP%3E%3C%2FLINGO-BODY%3E%3CLINGO-TEASER%20id%3D%22lingo-teaser-721240%22%20slang%3D%22en-US%22%3E%3CP%3EWe%20are%20expanding%20the%20graph%20database%20capabilities%20with%20several%20new%20features.%20In%20this%20blog%20we%20discuss%20one%20of%20these%20features%20that%20is%20now%20available%20for%20public%20preview%20in%20%3CA%20href%3D%22https%3A%2F%2Fwww.microsoft.com%2Fen-us%2Fsql-server%2Fsql-server-2019%22%20rel%3D%22noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%20noopener%20noreferrer%22%20target%3D%22_blank%22%3ESQL%20Server%202019%3C%2FA%3E%2C%20%3CSTRONG%3EShortest%20Path%3C%2FSTRONG%3E%2C%20which%20can%20be%20used%20to%20find%20a%20shortest%20path%20between%20two%20nodes%20in%20a%20graph.%20The%20shortest%20path%20function%20can%20also%20be%20used%20to%20compute%20a%20transitive%20closure%20or%20for%20arbitrary%20length%20traversals.%3C%2FP%3E%0A%3CP%20style%3D%22text-align%3A%20center%3B%22%3E%26nbsp%3B%26nbsp%3B%3CSPAN%20class%3D%22lia-inline-image-display-wrapper%20lia-image-align-inline%22%20style%3D%22width%3A%20999px%3B%22%3E%3CIMG%20src%3D%22https%3A%2F%2Fgxcuf89792.i.lithium.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F120670i2924898F19CEAEFC%2Fimage-size%2Flarge%3Fv%3D1.0%26amp%3Bpx%3D999%22%20alt%3D%22image.png%22%20title%3D%22image.png%22%20%2F%3E%3C%2FSPAN%3E%3C%2FP%3E%3C%2FLINGO-TEASER%3E%3CLINGO-SUB%20id%3D%22lingo-sub-778493%22%20slang%3D%22en-US%22%3ERe%3A%20Public%20Preview%20of%20Shortest%20Path%20on%20SQL%20Server%202019%3C%2FLINGO-SUB%3E%3CLINGO-BODY%20id%3D%22lingo-body-778493%22%20slang%3D%22en-US%22%3E%3CP%3EThis%20all%20sounds%20very%20promising%2C%20but%20how%20can%20it%20be%20used%20for%20weighted%20paths%2C%20eg%3A%20distances%20on%20a%20map%3F%20It%20seems%20it%20is%20only%20useful%20for%20counting%20nodes%2C%20but%20not%20distances.%20Am%20I%20missing%20something%3F%3C%2FP%3E%3CP%3E%26nbsp%3B%3C%2FP%3E%3C%2FLINGO-BODY%3E%3CLINGO-SUB%20id%3D%22lingo-sub-784979%22%20slang%3D%22en-US%22%3ERe%3A%20Public%20Preview%20of%20Shortest%20Path%20on%20SQL%20Server%202019%3C%2FLINGO-SUB%3E%3CLINGO-BODY%20id%3D%22lingo-body-784979%22%20slang%3D%22en-US%22%3E%3CP%3E%3CA%20href%3D%22https%3A%2F%2Ftechcommunity.microsoft.com%2Ft5%2Fuser%2Fviewprofilepage%2Fuser-id%2F384096%22%20target%3D%22_blank%22%3E%40freom%3C%2FA%3E%26nbsp%3BYou%20cannot%20use%20this%20to%20calculate%20a%20weighted%20shortest%20path.%20But%2C%20you%20can%20store%20weights%20as%20edge%20properties%2Fattributes%20and%20calculate%20the%20weight%20for%20the%20shortest%20path%20by%20distance%20using%20the%20aggregate%20functions%20(sum%2C%20in%20this%20case)%20over%20edge%20attributes.%26nbsp%3B%3C%2FP%3E%3C%2FLINGO-BODY%3E%3CLINGO-SUB%20id%3D%22lingo-sub-840755%22%20slang%3D%22en-US%22%3ERe%3A%20Public%20Preview%20of%20Shortest%20Path%20on%20SQL%20Server%202019%3C%2FLINGO-SUB%3E%3CLINGO-BODY%20id%3D%22lingo-body-840755%22%20slang%3D%22en-US%22%3E%3CA%20href%3D%22https%3A%2F%2Ftechcommunity.microsoft.com%2Ft5%2Fuser%2Fviewprofilepage%2Fuser-id%2F73668%22%20target%3D%22_blank%22%3E%40Shreya%20Verma%3C%2FA%3EAre%20there%20any%20plans%20to%20allow%20extra%20edge%20columns%20to%20be%20used%20in%20WHERE%20clauses%3F%20SHORTEST_PATH%20will%20not%20work%20properly%20if%20you%20have%20cycles%20in%20your%20graph%20and%20use%20an%20extra%20column%20(i.e.%20a%20column%20type)%20to%20differentiate%20between%20the%20different%20edge%20types%20(i.e.%20parent%2Fchild)%3C%2FLINGO-BODY%3E
Microsoft

SQL Server 2017 and Azure SQL Database introduced native graph database capabilities used to model many-to-many relationships. The first implementation of SQL Graph introduced support for nodes to represent entities, edges to represent relationships and a new MATCH predicate to support graph pattern matching and traversal.

 

We are expanding the graph database capabilities with several new features. In this blog we discuss one of these features that is now available for public preview in SQL Server 2019, Shortest Path, which can be used to find a shortest path between two nodes in a graph. The shortest path function can also be used to compute a transitive closure or for arbitrary length traversals.

 

With CTP3.1, we are introducing a new function SHORTEST_PATH, which can be used inside MATCH to find a shortest path between any 2 nodes in a graph or to perform arbitrary length traversals. Users can specify a pattern they would like to search for in the graph using a regular expression style syntax.

 

To understand the new syntax and how shortest path works, from Adventure Works Cycles, a bicycle wholesaler that sells and manufactures bicycles. We have converted their bill of materials hierarchy into a graph, which has Product node and IsPartOf edge table. Download sample scripts here.

 

AdventureWorksBOM.png

Now, let’s look at some sample queries to see how shortest path can help with recursive or arbitrary length traversals in a graph schema.  

 

Find all assemblies where a given product is used

Imagine that the inventory of a given product (Bearing Ball) at Adventure Works Cycles is running low and that they would like to find all the assemblies in their manufacturing pipeline, where a Bearing Ball is used. This will tell them what assemblies will be affected due to the scarcity of a given product.

 

The following query demonstrates how shortest path can be used to find all assemblies that require a Bearing Ball in the bill of materials:

 

-- Find all the assemblies where Bearing Ball is used
SELECT 
	P1.ProductID, 
	P1.Name,
	STRING_AGG(P2.Name,'->') WITHIN GROUP (GRAPH PATH) AS [Assembly],
	LAST_VALUE(P2.ProductID) WITHIN GROUP (GRAPH PATH) AS [Final ProductID]
FROM
	PRODUCT P1,
	PRODUCT FOR PATH P2,
	ISPARTOF FOR PATH IPO
WHERE 
	MATCH(SHORTEST_PATH(P1(-(IPO)->P2)+))
	AND P1.ProductID = 2
       ORDER BY P1.ProductID	

This query starts from ProductID = 2 (Bearing Ball) and keeps traversing up the BOM tree until it finds all products that contain a Bearing Ball.

 

Here are first few lines from the result set:

      image.png

 

The STRING_AGG function on P2.Name fetches all the nodes that were traversed in this path, thereby, giving us a good view of assembly line up to ‘Touring-3000 Yellow, 58’ bike. Other rows in the result set show the other assemblies which have dependency on Bearing Ball at some level.

 

This query uses a lot of new syntax. Let’s understand what this new syntax does.

 

SHORTEST_PATH

The SHORTEST_PATH function lets you find:

  1. A shortest path between two given nodes/entities
  2. Single source shortest path(s).
  3. Shortest path from multiple source nodes to multiple target nodes.

It takes an arbitrary length pattern as input, described below. It returns a shortest path that exists between two nodes. This function can only be used inside MATCH. It accepts an arbitrary length pattern and finds a shortest path in the graph, which matches that pattern. If there exist two or more shortest paths of the same length between any pair of source and destination node(s), the function will return the one that was found first during traversal. Note that, an arbitrary length pattern can only be specified inside a SHORTEST_PATH function. Finding weighted shortest paths, all paths or all shortest paths is not supported yet.

 

Arbitrary Length Pattern

This pattern includes the nodes and edges that must be traversed repeatedly until the desired node is reached or until the maximum number of iterations as specified in the pattern is met. Each time the query is executed, the result of executing this pattern will be a collection of nodes and edges traversed along the path from the start node to the end node. This is a regular expression style syntax pattern and the following two pattern quantifiers are supported in this release:

 

‘+’  :   Repeat the pattern 1 or more times. Terminate as soon as a shortest path is found.

We recommend that users provide a start and an end node, along with the pattern, whenever ‘+’ is used in the pattern predicate. For a big graph, a query with ‘+’ and no terminating condition may take a long time to finish. Refer to the example shown in ‘Find Shortest path between 2 given nodes’ section below, to see how filters on start and end node can be applied.

{1,n} : Repeat the pattern 1 to ‘n’ times. Terminate as soon as a shortest  is found or when the max number of iterations ‘n’ specified in the pattern is reached.

 

FOR PATH

FOR PATH must be used with any node or edge table name in the FROM clause, which will participate in an arbitrary length pattern. FOR PATH tells the engine that the node or edge table will return an ordered collection representing the list of nodes or edges along the path from the start node to the end node. The attributes from these tables cannot be projected directly in the SELECT clause and cannot be filtered directly in the WHERE clause. To project or filter attributes from these tables, graph path aggregate functions must be used.

 

Graph Path Aggregate Functions

Since the nodes and edges involved in arbitrary length pattern return a collection (of node(s) and edge(s) traversed in that path), users cannot project the attributes directly using the conventional tablename.attributename syntax. For queries where it is required to project attribute values from the intermediate node or edge tables, in the path traversed, we have extended aggregate functions to work with graph node or edge tables. In this release, the following graph path aggregate functions are available: STRING_AGG, LAST_VALUE, SUM, AVG, MIN, MAX and COUNT. These functions can be used in SELECT or ORDER BY clause.

 

Find all the products which are up to 3 levels away from a given product.

Now, if Adventure Works Cycles wants to find products in their BOM, which are 1 to 3 levels away from Bearing Ball, they can just modify the query shown in example above as follows:

 

SELECT 
	P1.ProductID, 
	P1.Name,
	STRING_AGG(P2.Name,'->') WITHIN GROUP (GRAPH PATH) AS [Assembly],
	LAST_VALUE(P2.ProductID) WITHIN GROUP (GRAPH PATH) AS [Final ProductID]
FROM
	PRODUCT P1,
	PRODUCT FOR PATH P2,
	ISPARTOF FOR PATH IPO
WHERE 
	MATCH(SHORTEST_PATH(P1(-(IPO)->P2){1,3}))
	AND P1.ProductID = 2
ORDER BY P1.ProductID	

Here is a sample result set:

      image.png

 

Find Shortest Path between 2 given nodes

The queries shown above, start from a given node (Bearing Ball) and then search all paths in the graph starting from that node, until they cannot find any other paths that originate from this node and end at other nodes.

 

Imagine that Adventure Works Cycles wants to find the shortest path between 2 given nodes in the assembly. They can use following query to do this. This query will again start at ProductID = 2 (Bearing Ball) but terminates as soon as it finds ProductID = 768 (bike ‘Road-650 Black, 44’).

 

SELECT
	ProductID, Name, [Assembly], FinalProductID, Levels
FROM (
	SELECT 
		P1.ProductID, 
		P1.Name,
		STRING_AGG(P2.Name,'->') WITHIN GROUP (GRAPH PATH) AS [Assembly],
		LAST_VALUE(P2.ProductID) WITHIN GROUP (GRAPH PATH) AS FinalProductID,
		COUNT(P2.ProductID) WITHIN GROUP (GRAPH PATH) AS Levels
	FROM
		PRODUCT P1,
		PRODUCT FOR PATH P2,
		ISPARTOF FOR PATH IPO
	WHERE 
		MATCH(SHORTEST_PATH(P1(-(IPO)->P2)+))
		AND P1.ProductID = 2
 ) AS Q
 WHERE Q.FinalProductID = 768

Note that in this query, we used a subquery to apply filter on the last node traversed in the path (FinalProductID = 768). The filter on the FinalProductID in the outer query is pushed down while computing the shortest path. Hence, the query will terminate as soon as the FinalProductID is found. LAST_VALUE() function, which fetches the attribute values from last node traversed, cannot be used in the WHERE clause, since it is a window aggregate function.  

 

By using the COUNT graph path aggregate function in select clause, we can see the number of hops/levels between the 2 ProductIDs. Here is the result set of this query:

 

      image.png

 

In this query, the predicate/filter on last node (Q.FinalProductID) is pushed down. That is, the shortest path query terminates as soon as it finds ProductID = 768.

Writing a shortest path query with a terminating condition on the last node, as shown in the query above, is highly recommended. This is a much more optimal query than the ones which start at one node and then traverse the entire graph to find all the connections that exist from that node to others. For huge graphs, finding the shortest path from a given start node to all the other nodes in the graph, will be a very expensive operation.

 

Conclusion

Starting with SQL Server 2019 CTP3.1, you can use SHORTEST_PATH function to compute shortest path(s) between nodes in a graph, using a regular expression style search pattern. SHORTEST_PATH can only be used inside a MATCH function and works only with graph node and edge tables. This function also allows you to write transitive closure or arbitrary length traversal query from a given ‘start’ node.

 

Next Steps

Please download and give this feature a try.  We are looking forward to hearing your comments or feedback for this feature.

 

3 Comments
Occasional Visitor

This all sounds very promising, but how can it be used for weighted paths, eg: distances on a map? It seems it is only useful for counting nodes, but not distances. Am I missing something?

 

Microsoft

@freom You cannot use this to calculate a weighted shortest path. But, you can store weights as edge properties/attributes and calculate the weight for the shortest path by distance using the aggregate functions (sum, in this case) over edge attributes. 

Occasional Visitor
@Shreya Verma Are there any plans to allow extra edge columns to be used in WHERE clauses? SHORTEST_PATH will not work properly if you have cycles in your graph and use an extra column (i.e. a column type) to differentiate between the different edge types (i.e. parent/child)