From: Rick Elbers <>
Date: Tue, 26 Sep 2006 18:32:54 +0200
Message-ID: <>

Dear fellow programmers,

The problem with an in memory database which you want in case of 2 tier applications is that you dont know where to start inserting or deleting records in the actual (server) database. Thats why you might have a good use in 2-tier apps for an UpdatableView.

An important part of the updatable view problem is topological sort as someone pointed out before. Especially with autojoins. Finally I found some time to crank out some code in c#.

 I am asking everyone to verify the code below on his sql database to see if it comes up with a good topological sort of every table. (test code is added)


using System;

using System.Collections.Generic;
using System.Text;
using System.Data;

namespace Graph

    public class DataSetTopologicalSorter     {

        DataTableCollection m_Tables;

        public DataSetTopologicalSorter(DataSet set)
            m_Tables = set.Tables;
        private int NrOfAutoJoins(string  tablename)
            int Nr = 0;
            DataTable table = m_Tables[tablename];
            foreach (DataRelation Rel in table.ParentRelations)

if (Rel.ParentTable.Equals(table)) Nr++; } return Nr; } public List<DataTable> Sort() { List<DataTable> SortedTables = new List<DataTable>(); Dictionary<string, int> graph_in_process = new Dictionary<string,int>(); foreach(DataTable table in m_Tables) //put all datatables in graph..
// in that process find out the nr of in_degrees per
table, use parentrelations corrected for autojoins


                //autojoin solved
            Queue<DataTable> IndependentVertexes = new
            foreach(string name in graph_in_process.Keys)

// put all datatables with zero in_degrees in queue. // also datatables with only itself as in_degree if( graph_in_process[ name ] == 0) IndependentVertexes.Enqueue(m_Tables[name]); } while(IndependentVertexes.Count>0)
//go until gueue is empty... //start with a in_degree_zero node van de stapel.. DataTable aTable = IndependentVertexes.Dequeue() as DataTable; //if we want visitor replace this line by //visitor.visit(aTable) SortedTables.Add(aTable); //get to successors (childrelations) foreach(DataRelation aRelation in aTable.ChildRelations) { // decrement all connected vertexes( use
getchildtables corrected for autojoins in child)


                  // if the connected vertex is now in_degree zero 
                  //  add it to the queue
                    if ( (
                        == 0)

            //if queue is not empty we have cycles..
            if (IndependentVertexes.Count > 0)

SortedTables = null; throw new Exception("DataTables are containing cyclic dependcies"); } return SortedTables; }



To test this code in c#.20
make a datasource of your favorite complex database. That gives a typed dataset. Instantiate that like for instance:

TestDBDataSet set = new TestDBDataSet();

Then gui design a form with a listbox names lstTables and put the following code in form_load:

   private void Form1_Load(object sender, EventArgs e)

            List < DataTable > sortedTables = 
                new Graph.DataSetTopologicalSorter(set).Sort();

            foreach(DataTable aTable in sortedTables)


Rick Received on Tue Sep 26 2006 - 18:32:54 CEST

Original text of this message