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:
- 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
The contents of the article are listed below.
- Shortest Path Problems
- Two Algorithms
- Example Datasets
- Data Model
- Network Paths by SQL
- Min Pathfinder
- Subnetwork Grouper
- Tuning Subnetwork Grouper
- Unit Testing