How to Workaround Sorting Errors when Updating Self-Referencing DataSet Tables with Visual Studio 2008 SP1


Hierarchical update is an important feature of typed dataset that refers to the process of saving updated data back to a database while maintaining referential integrity rules. This feature is enhanced in Visual Studio 2008 by introducing a TableAdapterManger component to manage all TableApdaters in a typed dataset. When updating related tables, TableAdapterManager uses foreign-key relationships to determine the correct order to send Insert, Update, and Delete commands from a dataset to the database without violating the foreign-key constraints (referential integrity) in the database.


TableAdpaterManager is automatically generated when you create a typed-dataset in a project with Hierarchical Update enabled (For more information, see How to Enable and Disable Hierarchical Update), and it could greatly reduce the code to save data to multiple related tables. Users just need to call TableAdpaterManager.UpdateAll(DataSet). You could see how easy it is to use this class in “Sample Code Snippet to Update the Database” section of this article. However, when updating self-referencing tables, TableAdpaterManager has some defects in determining the correct order of affected rows, which could cause constraint violation errors when committing the changes to database. We have noticed this problem and are investigating how to resolve it. I’ll explain the idea of the solution and how to work around this issue with Visual Studio 2008 SP1.


What the Problem is

Sample Table


Suppose that you have a self-referencing table named Temp with three columns and a foreign-key relationship.


Table Definition:


clip_image002


Foreign-Key Relation:


clip_image004


Generated Typed-DataSet Code Snippet

Suppose you add a typed-dataset (say, dataset1) to your application, and drag-drop the Temp table from Server Explorer to the dataset designer, Visual Studio will generate code of the typed-dataset for you. Below is the code snippet that is related to this topic.


[C#]

public partial class TableAdapterManager : global::System.ComponentModel.Component {


    public virtual int UpdateAll(DataSet1 dataSet) {


        . . . . . .


        this.UpdateInsertedRows(dataSet, allAddedRows));


        . . . . . .


        this.UpdateDeletedRows(dataSet, allChangedRows));


        . . . . . .


    }


    private int UpdateInsertedRows(DataSet1 dataSet, global::System.Collections.Generic.List<global::System.Data.DataRow> allAddedRows) {


        . . . . . .


        this.SortSelfReferenceRows(addedRows, dataSet.Relations[“FK_Temp_Temp”], false);


        . . . . . .


    }  


    private int UpdateDeletedRows(DataSet1 dataSet, global::System.Collections.Generic.List<global::System.Data.DataRow> allChangedRows) {


        . . . . . .


        this.SortSelfReferenceRows(addedRows, dataSet.Relations[“FK_Temp_Temp”], true);


        . . . . . .


    }


    protected virtual void SortSelfReferenceRows(global::System.Data.DataRow[] rows, global::System.Data.DataRelation relation, bool childFirst) {


            global::System.Array.Sort<global::System.Data.DataRow>(rows, new SelfReferenceComparer(relation, childFirst));


    }


    private class SelfReferenceComparer : object, global::System.Collections.Generic.IComparer<global::System.Data.DataRow> {


        private global::System.Data.DataRelation _relation;


        private int _childFirst;


        . . . . . .


        public int Compare(global::System.Data.DataRow row1, global::System.Data.DataRow row2) {


             if (object.ReferenceEquals(row1, row2)) {


                 return 0;


             }


             if ((row1 == null)) {


                 return 1;


             }


             if ((row2 == null)) {


                 return 1;


             }


             // Is row1 the child or grandchild of row2


             if (this.IsChildAndParent(row1, row2)) {


                 return this._childFirst;


             }


             // Is row2 the child or grandchild of row1


             if (this.IsChildAndParent(row2, row1)) {


                 return (1 * this._childFirst);


             }


             return 0;


            }


   }


}


 



[VB]

Partial Public Class TableAdapterManager


        Inherits Global.System.ComponentModel.Component


    Public Overridable Function UpdateAll(ByVal dataSet As DataSet1) As Integer


        . . . . . .


        Me.UpdateInsertedRows(dataSet, allAddedRows)


        . . . . . .


        Me.UpdateDeletedRows(dataSet, allChangedRows)


        . . . . . .


    End Function


    Private Function UpdateInsertedRows(ByVal dataSet As DataSet1, ByVal allAddedRows As Global.System.Collections.Generic.List(Of Global.System.Data.DataRow)) As Integer


          . . . . . .


          Me.SortSelfReferenceRows(addedRows, dataSet.Relations(“FK_Temp_Temp”), False)


          . . . . . .


    End Function


 


    Private Function UpdateDeletedRows(ByVal dataSet As DataSet1, ByVal allChangedRows As Global.System.Collections.Generic.List(Of Global.System.Data.DataRow)) As Integer


          . . . . . .


          Me.SortSelfReferenceRows(addedRows, dataSet.Relations(“FK_Temp_Temp”), True)


          . . . . . .


    End Function


 



    Protected Overridable Sub SortSelfReferenceRows(ByVal rows() As Global.System.Data.DataRow, ByVal relation As Global.System.Data.DataRelation, ByVal childFirst As Boolean)

        Global.System.Array.Sort(Of Global.System.Data.DataRow)(rows, New SelfReferenceComparer(relation, childFirst))


    End Sub


   


    Private Class SelfReferenceComparer


              Inherits Object


              Implements Global.System.Collections.Generic.IComparer(Of Global.System.Data.DataRow)


        Private _relation As Global.System.Data.DataRelation


        Private _childFirst As Integer


        . . . . . .


        Public Function Compare(ByVal row1 As Global.System.Data.DataRowByVal row2 As Global.System.Data.DataRow) As Integer


                 Implements Global.System.Collections.Generic.IComparer(Of Global.System.Data.DataRow).Compare


            If Object.ReferenceEquals(row1, row2) Then


                Return 0


            End If


            If (row1 Is Nothing) Then


                Return -1


             End If


            If (row2 Is Nothing) Then


                Return 1


            End If


 



           ‘Is row1 the child or grandchild of row2

            If Me.IsChildAndParent(row1, row2) Then


                Return Me._childFirst


            End If


 



            ‘ row2 the child or grandchild of row1

            If Me.IsChildAndParent(row2, row1) Then


                Return (-1 * Me._childFirst)


            End If


            Return 0


        End Function


    End Class


End Class


 



Sample Code Snippet to Update the Database

Then, you could update the table with the help of TableAdapterManager. Below is snippet of sample code to insert some rows to the self-referencing Temp table, and then delete them.



[C#]

    DataSet1 ds = new DataSet1();


 


    DataSet1.TempRow row1 = ds.Temp.AddTempRow(1, null, “Row 1”);


    DataSet1.TempRow row4 = ds.Temp.AddTempRow(4, null, “Row 4”);


    DataSet1.TempRow row2 = ds.Temp.AddTempRow(2, row1, “Row 2”);


    DataSet1.TempRow row3 = ds.Temp.AddTempRow(3, row4, “Row 3”);


 



    DataSet1TableAdapters.TableAdapterManager manager = new DataSet1TableAdapters.TableAdapterManager();

    . . . . . .


    manager.UpdateAll(ds);  // Insert the rows


 


    row1.Delete();


    row2.Delete();


    row3.Delete();


    row4.Delete();


 



    manager.UpdateAll(ds);  // Delete the rows

 



[VB]

    Dim ds As DataSet1 = New DataSet1


 


    Dim row1 As DataSet1.TempRow = ds.Temp.AddTempRow(1, Nothing, “Row 1”)


    Dim row4 As DataSet1.TempRow = ds.Temp.AddTempRow(4, Nothing, “Row 4”)


    Dim row2 As DataSet1.TempRow = ds.Temp.AddTempRow(2, row1, “Row 2”)


    Dim row3 As DataSet1.TempRow = ds.Temp.AddTempRow(3, row4, “Row 3”)


 


    Dim manager As DataSet1TableAdapters.TableAdapterManager = New DataSet1TableAdapters.TableAdapterManager


    manager.UpdateAll(ds)  ‘ Insert the rows


 


    row1.Delete()


    row2.Delete()


    row3.Delete()


    row4.Delete()


 


    manager.UpdateAll(ds)  ‘ Delete the rows


 



What is the Problem and Why

From the code at the beginning of the post, we can see that TableAdapterManager uses System.Array.Sort<T>(T, IComparer<T>) to sort all rows before inserting them into or deleting them from database so that no violations to foreign-key constraints occur. The expected sorting result is: parent first for inserted rows, and child first for deleted rows. Take the sample code above for example, before calling SortSelfReferenceRows method, content of the array to insert is <R1, R4, R2, R3>. After calling the sorting method, R1 should come before R2, and R4 should come before R3. Because R1 is Parent of R2, and R4 is Parent of R3. Sequence between two rows that do not have Parent-Child (or Grandparent-Grandchild, etc) relationships are undetermined, e.g., R1 could come either before or after R4.


For each pair <row1, row2> in the array to sort, SortSelfReferenceRows.Compare() will be called to determine their sequence in the output array. From the implementation of SortSelfReferenceRows.Compare, we could see that any two rows that do not have a Parent-Child (or Grandparent-Grandchild, etc) relationship are treated equal. This is OK if all possible row pairs are compared, e.g. < R1, R4>, < R1, R2>, < R1, R3>, < R4, R2>, < R4, R3>, < R2, R3> are all explicitly compared by passing them to SortSelfReferenceRows.Compare. However, System.Array.Sort is implemented using QuickSort, it does not compare every possible row pair. Instead, equation relationships of rows are treated transitive. For example, if < R1, R4>is compared and the result is R1 == R4, < R4, R2> is compared and the result is R4 == R2, then System.Array.Sort will indicate that R1 == R2, and does NOT compare < R1, R2> at all! Clearly, you could see that R1 is Parent of R2, < R1, R2> should be explicitly compared and the result should be R1 < R2.


The Idea of the Solution

So, how to sort the array so that no foreign-key constraints are violated? The idea is to treat the array as a forest, group all rows that have the same root into a tree, and compare the rows based on their root and their distance to the root. For example, suppose we have an array < R1, R2, …, R14>, and the Parent-Child relationships among its elements are shown like picture below.


Untitled


We still use System.Array.Sort<T>(T, ICompare<T>) to sort the array. That means we do not have direct control over the sorting algorithm, and we do not know what row pairs to be compared or the sequence of these comparisons. However, we do could impact the sorting process by controlling the comparison result of row pairs. That’s why we need to re-write the SelfReferenceComparer.Compare method.


The pseudo code of the new Compare method is (suppose Parent First):


                int Compare (DataRow row1, DataRow row2)

                                DataRow root1 = row1’s root;


                                int distance1 = row1’s distance to root1


                                DataRow root2 = row2’s root;


                                int distance2 = row2’s distance to root2;


                                if (root1 == root2)


                                                return distance1 – distance2;


                                else


                                                return root1.RowIndex – root2.RowIndex;


                end


 


How to Work-Around The Problem with Visual Studio 2008 SP1

With Visual Studio 2008 SP1, as a workaround, you could derive from the generated TableAdpaterManager and override its SortSelfReferenceRows method to implement this algorithm by yourself. Of course, you could put your code anywhere of your project, but it’s recommended to put them in the typed-dataset’s source code file. Right-click the typed-dataset (say, DataSet1.xsd), and choose “View Code”, Visual Studio will automatically create the source code file for you (DataSet1.cs in this case). It’s recommended you put your implementation code here.


Your code could be like this:


[C#]

    // Derive from the generated TableAdapterManager and use it in your code instead


    public class MyTableAdpaterManager : DataSet1TableAdapters.TableAdapterManager {


        // Override this virtual method, and pass your own IComparer class


        protected override void SortSelfReferenceRows(System.Data.DataRow[] rows, System.Data.DataRelation relation, bool childFirst) {


            System.Array.Sort<System.Data.DataRow>(rows, new MySelfReferenceComparer(relation, childFirst));


        }


        private class MySelfReferenceComparer : object, global::System.Collections.Generic.IComparer<global::System.Data.DataRow>  {


            private global::System.Data.DataRelation _relation;


            private int _childFirst;


            internal MySelfReferenceComparer(global::System.Data.DataRelation relation, bool childFirst) {


                this._relation = relation;


                if (childFirst) {


                    this._childFirst = 1;


                }


                else {


                    this._childFirst = 1;


                }


            }


 



            // Get the root of a row, and calculate its distance to the root

            private global::System.Data.DataRow GetRoot(global::System.Data.DataRow row, out int distance) {


                global::System.Diagnostics.Debug.Assert((row != null));


                global::System.Data.DataRow root = row;


                distance = 0;


 


                // Save all traversed rows to avoid infinite loop


                global::System.Collections.Generic.IDictionary<global::System.Data.DataRow, global::System.Data.DataRow> traversedRows = new global::System.Collections.Generic.Dictionary<global::System.Data.DataRow, global::System.Data.DataRow>();


                traversedRows[row] = row;


 


                global::System.Data.DataRow parent = row.GetParentRow(this._relation, global::System.Data.DataRowVersion.Default);


                while ((parent != null) && !traversedRows.ContainsKey(parent)) {


                    distance++;


                    root = parent;


                    traversedRows[parent] = parent;


                    parent = parent.GetParentRow(this._relation, global::System.Data.DataRowVersion.Default);


                }


 



                // This is mainly for Deleted rows

                if (distance == 0) {


                    traversedRows.Clear();


                    traversedRows[row] = row;


                    parent = row.GetParentRow(this._relation, global::System.Data.DataRowVersion.Original);


                    while ((parent != null) && !traversedRows.ContainsKey(parent)) {


                        distance++;


                        root = parent;


                        traversedRows[parent] = parent;


                        parent = parent.GetParentRow(this._relation, global::System.Data.DataRowVersion.Original);


                    }


                }


                return root;


            }


 



            public int Compare(global::System.Data.DataRow row1, global::System.Data.DataRow row2) {

                if (object.ReferenceEquals(row1, row2)) {


                    return 0;


                }


 


                if ((row1 == null)) {

                    return 1;


                }


 


                if ((row2 == null)) {

                    return 1;


                }


 



                // Get root of row1 and calculate its distance to the root

                int distance1 = 0;


                global::System.Data.DataRow root1 = this.GetRoot(row1, out distance1);


 



                // Get root of row2 and calculate its distance to the root

                int distance2 = 0;


                global::System.Data.DataRow root2 = this.GetRoot(row2, out distance2);


 




                if (object.ReferenceEquals(root1, root2)) {

                    return this._childFirst * distance1.CompareTo(distance2);


                }


                else {


                    // Compare root1 and root2 with their row index to ensure the correct sort order


                    global::System.Diagnostics.Debug.Assert((root1.Table != null) && (root2.Table != null));


                    if (root1.Table.Rows.IndexOf(root1) < root2.Table.Rows.IndexOf(root2)) {


                        return 1;


                    }


                    else {


                        return 1;


                    }


                }


            }


        }


    }


 


[VB]


    ‘ Derive from the generated TableAdapterManager and use it in your code instead


    Public Class MyTableAdapterManager


        Inherits DataSet1TableAdapters.TableAdapterManager


        ‘ Override this virtual method, and pass your own IComparer class


        Protected Overrides Sub SortSelfReferenceRows(ByVal rows() As System.Data.DataRow, ByVal relation As System.Data.DataRelation, ByVal childFirst As Boolean)


            Global.System.Array.Sort(Of Global.System.Data.DataRow)(rows, New MySelfReferenceComparer(relation, childFirst))


        End Sub


 



        Private Class MySelfReferenceComparer

            Inherits Object


            Implements Global.System.Collections.Generic.IComparer(Of Global.System.Data.DataRow)


            Private _relation As Global.System.Data.DataRelation


            Private _childFirst As Integer


 



            Friend Sub New(ByVal relation As Global.System.Data.DataRelation, ByVal childFirst As Boolean)

                Me._relation = relation


                If childFirst Then


                    Me._childFirst = -1


                Else


                    Me._childFirst = 1


                End If


            End Sub


 



            ‘ Get root of a row, and calculate its distance to the root

            Private Function GetRoot(ByVal row As Global.System.Data.DataRow, ByRef distance As Integer) As Global.System.Data.DataRow


                Global.System.Diagnostics.Debug.Assert((Not (row) Is Nothing))


                Dim root As Global.System.Data.DataRow = row


                distance = 0


                


                ‘ Save all traversed rows to avoid infinite loop


                Dim traversedRows As Global.System.Collections.Generic.IDictionary(Of Global.System.Data.DataRow, Global.System.Data.DataRow) = New Global.System.Collections.Generic.Dictionary(Of Global.System.Data.DataRow, Global.System.Data.DataRow)()


                traversedRows(row) = row


 


                Dim parent As Global.System.Data.DataRow = row.GetParentRow(Me._relation, Global.System.Data.DataRowVersion.[Default])


                Do While ((Not (parent Is Nothing)) _


                            AndAlso (traversedRows.ContainsKey(parent) = False))


                    distance = distance + 1


                    root = parent


                    traversedRows(parent) = parent


                    parent = parent.GetParentRow(Me._relation, Global.System.Data.DataRowVersion.Default)


                Loop


 



                ‘ This is mainly for Deleted rows

                If (distance = 0) Then


                    parent = row.GetParentRow(Me._relation, Global.System.Data.DataRowVersion.Original)


                    Do While ((Not (parent Is Nothing)) _


                            AndAlso (traversedRows.ContainsKey(parent) = False)) 


                        distance = distance + 1


                        root = parent


                        traversedRows(parent) = parent


                        parent = parent.GetParentRow(Me._relation, Global.System.Data.DataRowVersion.Original)


                    Loop


                End If


                Return root


            End Function


 


            Public Function Compare(ByVal row1 As Global.System.Data.DataRow, ByVal row2 As Global.System.Data.DataRow) As Integer Implements Global.System.Collections.Generic.IComparer(Of Global.System.Data.DataRow).Compare


                If Object.ReferenceEquals(row1, row2) Then


                    Return 0


                End If


 


                If (row1 Is Nothing) Then

                    Return -1


                End If


 


                If (row2 Is Nothing) Then

                    Return 1


                End If


 



                ‘Get root of row1 and calculate its distance to root

                Dim distance1 As Integer = 0


                Dim root1 As Global.System.Data.DataRow = Me.GetRoot(row1, distance1)


 



                ‘Get root of row2 and calculate its distance to root

                Dim distance2 As Integer = 0


                Dim root2 As Global.System.Data.DataRow = Me.GetRoot(row2, distance2)


 



                If Object.ReferenceEquals(root1, root2) Then

                    Return Me._childFirst * distance1.CompareTo(distance2)


                Else


                    ‘ Compare root1 and root2 with their row index to ensure the correct sort order



                    Global.System.Diagnostics.Debug.Assert((Not root1.Table Is Nothing) AndAlso (Not root2.Table Is Nothing))


                    If (root1.Table.Rows.IndexOf(root1) < root2.Table.Rows.IndexOf(root2)) Then


                        Return -1


                    Else


                        Return 1


                    End If


                End If


            End Function


        End Class


End Class


 



For the complete sample code, you could download it at Code Gallery.  Cheers!

 

Comments (2)

  1. I am creating my project on c# and this tips is really helpful for me in my project for database connection of self reference tables.

  2. Anthony says:

    Thank you for posting this — we’d encountered this problem, and the fixed SelfReferenceComparer seems to work nicely.