This is an introduction to an article, Shortest Path Analysis of Large Networks by SQL and PL/SQL, on the use of SQL and PL/SQL to solve shortest path network problems on an Oracle database. It provides solutions in pure SQL (based on previous articles by the author), and solutions in PL/SQL with embedded SQL that scale better for larger problems.

It applies the solutions to a range of problems, upto a size of 2,800,309 nodes and 109,262,592 links.

Standard and custom methods for execution time profiling of the code are included, and one of the algorithms implemented in PL/SQL is tuned based on the profiling.

The two PL/SQL entry points have automated unit tests using the Math Function Unit Testing design pattern, Trapit – Oracle PL/SQL unit testing module.

Movie Morsel: Six Degrees of Kevin Bacon

All code and examples are available on GitHub.

There is a series of mp4 recordings, in the mp4 folder on GitHub, briefly going through the sections of the blog post, which can also be viewed via Twitter:

Twitter Recordings

• 1: Overview
• 2: Shortest Path Problems
• 3: Two Algorithms
• 4: Example Datasets
• 5: Data Model TBA
• 6: Network Paths by SQL TBA
• 7: Min Pathfinder TBA

Contents

The contents of the article are listed below.

• Background
• Shortest Path Problems
• Two Algorithms
• Example Datasets
• Data Model
• Network Paths by SQL
• Min Pathfinder
• Subnetwork Grouper
• Tuning Subnetwork Grouper
• Unit Testing
• Conclusion
• References