Tuesday, 07 July 2009
I while ago I developed a Windows Vista Sidebar Gadget for tracking packages shipped using the Norwegian Postal Service, Posten - or Bring as they call themselves these days.

A couple of users (thanks Haakon and Morten) made me aware of that it's not working anymore. I've looked into it and found that Posten has changed the address to the page I'm downloading the tracking data from.

I've now updated it, so it should be working again. It looks like there's a delay for updating gadgets at the Live Gallery, so in the meantime you can download it here.

posted on Tuesday, 07 July 2009 14:25:57 (W. Europe Standard Time, UTC+01:00)  #    Comments [14]
 Friday, 30 January 2009
I'm in my last semester here at the Norwegian University of Science and Technology, which means that I'm starting on my master thesis these days. Actually, I'm not starting now, I'm continuing on the "pre-project" I worked on together with my friend, Alex Brasetvik from August to December last year.

Our master thesis is about building a query optimizer for Fast's (now a subsidiary of Microsoft, they bought them) new Enterprise Search solution.

The report itself can be found here: MasterProjectReport.pdf, and the abstract is included below:
This document is the report for the authors’ joint effort in researching and designing a query optimizer for fast’s next-generation search platform, known as MARS. This work was done during the pre-project to the master thesis at the Department of Computer and Information Science at the Norwegian University of Science and Technology, autumn 2008.

MARS does not currently employ any form of query optimizer, but does have a parser and a runtime system. The report therefore focuses on the core query optimizing aspects, like plan generation and optimizer design. First, we give an introduction to query optimizers and selected problems. Then, we describe previous and ongoing efforts regarding query optimizers, before shifting focus to our own design and results.

MARS supports
DAG-structured query plans, which means that the optimizer must do so too. This turned out to be a greater task than what it might seem like. The optimizer also needed to be extensible, including the ability to deal with query operators it does not know, as well as supporting arbitrary cost models.

During the course of the project, we have laid out the design of an optimizer we believe satisfies these goals. DAGs are currently not
fully supported, but the design can be extended to do so. Extensibility is solved by loose coupling between optimizer components. Rules are used to model operators, and the cost model is a separate, customizable component. We have also implemented a prototype that demonstrates that the design actually works.

posted on Friday, 30 January 2009 03:08:08 (W. Europe Standard Time, UTC+01:00)  #    Comments [1]
 Tuesday, 08 January 2008

When living on the edge (read: running the latest betas of everything) as I do, you get trouble from time to time. This time it was Visual Studio 2008 "Data Dude" combined with SQL Server 2008. For those of you not familiar with it, "Data Dude" is an extension to Visual Studio for working with databases; unit testing of your database, automatic data generation etc.

My problem was that I kept getting a message saying "Object reference not set to an instance of an object." all the time when I tried to create a new database project. I suspected that SQL 2008 was the cause, and I was right. It turns out that "Data Dude" creates a temporary database when you're opening or creating a project. In my case this happened in the default SQL Server instance on the machine, which is SQL Server 2008 CTP5 Dev Edition. "Data Dude" didn't like that very much.

The solution (at least in my case) was to configure it to use the installed SQL Server 2005 Express Edition instead. You do that by going to Tools -> Options -> Database Tools -> "Data Connections" and
"Design-time Validation Database". Fill in the instance name of a SQL 2005 instance in the text boxes. So now you know!

posted on Tuesday, 08 January 2008 01:23:28 (W. Europe Standard Time, UTC+01:00)  #    Comments [0]
 Wednesday, 20 December 2006

School is out for Christmas (I had my last exam last Friday), so now I have time do fun things, like coding (surprise).

I think algorithmic programming and databases and SQL queries are cool things, so why not combine them? Yesterday I got an idea of implementing some well-known algorithm in SQL, and I figured out that Dijkstra's Shortest Path algorithm should be fun to implement.

Dijkstra's shortest path algorithm finds, well, the shortest path from one vertex to the other vertexes in a weighted graph. The edges have lengths (or costs or whatever), and the shortest path from one vertex to another is the path where the sum of these lengths are as small as possible. Take a look at the illustration below, showing a graph with some Norwegian cities. The shortest path from Trondheim to Fredrikstad has been highlighted (for those of you that know Norway, not very realistic, but let's pretend it is just for the fun of it).

The algorithm works like a breadth first search that takes the edge weights into account, starting at one vertex and traversing through the graph.

So, how do we implement this in Transact-SQL (MS SQL Server's SQL dialect)? Well, first we need some way to represent the graph. I've created two tables:


The City table is pretty straightforward. The Road table contains one row for every road from one city to another, and the length of that road. Notice that we have two rows for every two cities we have a road between them, one each way. But, now to the real stuff: The implementation of the algorithm:

CREATE PROCEDURE [dbo].[Dijkstra]
    @StartCity Int
    -- Automatically rollback the transaction if something goes wrong.    
    -- SET NOCOUNT ON added to prevent extra result sets from
    -- interfering with SELECT statements.

    -- Create a temporary table for storing the estimates as the algorithm runs
    CREATE TABLE #CityList
        CityId Int NOT NULL,    -- The City Id
        Estimate Int NOT NULL,    -- What is the distance to this city, so far?
        Predecessor Int NULL,    -- The city we came from to get to this city with this distance.
        Done bit NOT NULL        -- Are we done with this city yet (is the estimate the final distance)?

    -- Fill the temporary table with initial data
    INSERT INTO #CityList (CityId, Estimate, Predecessor, Done)
    SELECT CityId, 2147483647, NULL, 0 FROM City
    -- Set the estimate for the city we start in to be 0.
    UPDATE #CityList SET Estimate = 0 WHERE CityID = @StartCity
    IF @@rowcount <> 1
        RAISERROR ('Couldn''t set start city', 11, 1)
        ROLLBACK TRAN        

    DECLARE @FromCity Int, @CurrentEstimate Int

    -- Run the algorithm until we decide that we are finished
    WHILE 1=1
        -- Reset the variable, so we can detect getting no records in the next step.
        SELECT @FromCity = NULL

        -- Select the CityID and current estimate for a city not done, with the lowest estimate.
        SELECT TOP 1 @FromCity = CityId, @CurrentEstimate = Estimate
        FROM #CityList WHERE Done = 0 AND Estimate < 2147483647
        ORDER BY Estimate
        -- Stop if we have no more unvisited, reachable cities.
        IF @FromCity IS NULL BREAK

        -- We are now done with this city.
        UPDATE #CityList SET Done = 1 WHERE CityId = @FromCity

        -- Update the estimates to all neighbour cities of this one (all the cities
        -- there are roads to from this city). Only update the estimate if the new
        -- proposal (to go via the current city) is better (lower).
        UPDATE #CityList SET #CityList.Estimate = @CurrentEstimate + Road.Distance,
            #CityList.Predecessor = @FromCity
        FROM #CityList INNER JOIN Road ON #CityList.CityID = Road.ToCity
        WHERE Road.FromCity = @FromCity AND (@CurrentEstimate + Road.Distance) < #CityList.Estimate
    -- Select the results.
    SELECT City1.Name AS ToCity, Estimate AS Distance, city2.Name AS Predecessor FROM #CityList
    INNER JOIN City city1 ON #CityList.CityId = City1.CityID
    LEFT OUTER JOIN City city2 ON #CityList.Predecessor = city2.CityID
    -- Drop the temp table.
    DROP TABLE #CityList

If we run it with Trondheim as start city (@StartCity = 1), we get this result table:


This says that from Trondheim, we have a distance 0 to Trondheim, 2 to Bergen and so on, and 6 to Fredrikstad. The Predecessor column says what city we came from when we went to each city. We can see that to get to Fredrikstad, we came from Oslo, and to get to Oslo, we came from Bergen. To get to Bergen, we came from Trondheim. Therefore, to get to Fredrikstad, we took the path Trondheim, Bergen, Oslo, Fredrikstad.

I have included the SQL script to create the database:

Dijkstra.txt (8,03 KB)
TestScript.txt (1,26 KB)

posted on Wednesday, 20 December 2006 17:45:10 (W. Europe Standard Time, UTC+01:00)  #    Comments [12]
 Wednesday, 03 May 2006

Coding too much and sleeping too little is a setting I'm not too unfamiliar with. You know you should sleep a bit more and code a bit less when you have nightmares about debugging and are wondering what method of which class to call to shut off the wakeup alarm in the morning. I'm coding on a project with a few friends these days and came over some interesting code, probably caused by the setting above:

public string MyProp
   set {value = value; }

Hmm... useful property...

if (valueQueues[queueId].Count != null)
   return valueQueues[queueId].Dequeue();
   return null;

Hmmm.. Nullable types is an interesting thing, but I don't think this is the right setting to use them...

posted on Wednesday, 03 May 2006 02:16:04 (W. Europe Standard Time, UTC+01:00)  #    Comments [1]