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:
Foreign-Key Relation:
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.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
'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.
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
Anonymous
September 18, 2009
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.Anonymous
April 06, 2010
Thank you for posting this -- we'd encountered this problem, and the fixed SelfReferenceComparer seems to work nicely.