Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am trying to answer this question by using a breadth-first search from each node of the graph represented by the tables mapSolarSystems and mapSolarSystemJumps in the data dump at http://community.eveonline.com/community/toolkit.asp (important parts of schema below) in order to find the node with the lowest average edge count to all points on the subgraph of nodes with security >= 0.45.

I managed to hack together this beauty of T-SQL from various tutorials across the web. Sadly, although I managed to get it to function, I am not confident that it is correct. I've never created quite such a complicated piece of SQL before.

At the same time, I would like some assistance with idiomatic T-SQL - looks like CapWords for identifiers, usp_ for stored procedures, BEGIN always on new line. I've tried to take the worst offenders out of the first working version of the code at http://gaming.stackexchange.com/a/103876/9760 - things which I can spot. I was able to reduce the execution time to 4:21 minutes from 7:01 minutes in the process.

My priorities are:

  1. Correctness vetting or fixed
  2. Readability / Clarity (eg, idomatic)
  3. Execution speed

T-SQL:

CREATE PROCEDURE dbo.usp_Eve_BFS
AS
BEGIN
    SET XACT_ABORT ON
    BEGIN TRAN
    SET NOCOUNT ON;

    CREATE TABLE #Result (Id int NOT NULL PRIMARY KEY, Name nvarchar(100), Average int, Maximum int)
    INSERT INTO #Result (Id, Name) SELECT solarSystemID, solarSystemName FROM mapSolarSystems WHERE security >= 0.45

    DECLARE @StartNode int
    DECLARE c CURSOR FOR SELECT Id FROM #Result
    OPEN c
    FETCH NEXT FROM c INTO @StartNode

    WHILE @@FETCH_STATUS=0
    BEGIN
        CREATE TABLE #Discovered (Id int NOT NULL PRIMARY KEY, Parent int NULL, Depth int)
        INSERT INTO #Discovered (Id, parent, depth) VALUES (@StartNode, NULL, 0)

        WHILE @@ROWCOUNT > 0
        BEGIN
            INSERT INTO #Discovered (Id, Parent, Depth)
            SELECT toSolarSystemID, MAX(fromSolarSystemID), MIN(Depth) + 1
            FROM #Discovered d JOIN mapSolarSystemJumps ON d.Id = fromSolarSystemID
            JOIN #Result ON (mapSolarSystemJumps.toSolarSystemID = #Result.Id)
            WHERE toSolarSystemID NOT IN (SELECT Id From #Discovered)
            AND Depth = ( -- make sure the fromSolarSystemID matches the MIN(depth)!
                SELECT MIN(Depth) FROM #Discovered d JOIN mapSolarSystemJumps ON d.Id = fromSolarSystemID
                JOIN #Result ON (mapSolarSystemJumps.toSolarSystemID = #Result.Id)
                WHERE toSolarSystemID NOT IN (SELECT Id From #Discovered)
            )
            GROUP BY toSolarSystemID
        END;

        WITH BacktraceCTE(Id, Depth) AS
        (
            SELECT Id, Depth
            FROM #Discovered d
            WHERE d.Id = @StartNode
        UNION ALL
            SELECT d.Id, d.Depth
            FROM #Discovered d JOIN BacktraceCTE cte ON d.Parent = cte.Id
        )
        UPDATE #Result
        SET Average = a.Average, Maximum = a.Maximum
        FROM (SELECT AVG(Depth) AS Average, MAX(Depth) AS Maximum FROM BacktraceCTE) AS a
        WHERE #Result.Id = @StartNode

        DROP TABLE #Discovered

        FETCH NEXT FROM c INTO @StartNode
    END

    SELECT * FROM #Result ORDER BY Average, Maximum;
    DROP TABLE #Result

    COMMIT TRAN
    RETURN 0
END

The basic shape came from http://hansolav.net/sql/graphs.html#bfs.

Edit: mapSolarSystems relevant columns:

regionID    int
constellationID int
solarSystemID   int
solarSystemName nvarchar(100)
security    float

mapSolarSystems relevant indexes:

mapSolarSystems_IX_constellation    nonclustered located on PRIMARY constellationID
mapSolarSystems_IX_region   nonclustered located on PRIMARY regionID
mapSolarSystems_IX_security nonclustered located on PRIMARY security
mapSolarSystems_PK  clustered, unique, primary key located on PRIMARY solarSystemID

mapSolarSystemJumps relevant columns:

fromRegionID    int
fromConstellationID int
fromSolarSystemID   int
toSolarSystemID int
toConstellationID   int
toRegionID  int

mapSolarSystemJumps relevant indexes:

mapSolarSystemJumps_IX_fromConstellation    nonclustered located on PRIMARY fromConstellationID
mapSolarSystemJumps_IX_fromRegion   nonclustered located on PRIMARY fromRegionID
mapSolarSystemJumps_PK  clustered, unique, primary key located on PRIMARY fromSolarSystemID, toSolarSystemID
share|improve this question

closed as unclear what you're asking by Jamal Dec 16 '13 at 2:02

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Please specify the structure of tables you're using, and what do you need to do. Currently it looks like asking a passing by pedestrian "Am I going in a right direction?" without telling your destination ;) –  almaz Feb 6 '13 at 13:52
    
@almaz - Good point, I've added the relevant portions of the schema and my intent above. –  michaelc Feb 6 '13 at 17:33
add comment