You are viewing a plain text version of this content. The canonical link for it is here.
Posted to ojb-dev@db.apache.org by Gerhard Grosse <ge...@lex-com.net> on 2004/11/18 14:06:48 UTC
Java class for ordering SQL statements in ODMG to avoid FK violations
Hi,
for quite some time we were experiencing problems with FK constraint violations
when committing ODMG transactions. We resolved these problems by inserting
TransactionExt.flush() calls wherever necessary. However, this in turn produced
deadlock problems under high server load. Therefore we decided to try and
improve the ordering of the SQL sent to the database. These efforts resulted in
a class org.ojb.odmg.ObjectEnvelopeOrdering which we hereby contribute to the
OJB community, because other users seem to have similar problems.
To use this class, the private method reorder() in class
org.ojb.odmg.ObjectEnvelopeTable must be replaced with:
private void reorder()
{
if (needsCommit)
{
ObjectEnvelopeOrdering ordering =
new ObjectEnvelopeOrdering(transaction,mvOrderOfIds,mhtObjectEnvelopes);
ordering.reorder();
Identity[] newOrder = ordering.getOrdering();
mvOrderOfIds.clear();
for (int i = 0; i < newOrder.length; i++)
{
mvOrderOfIds.add(newOrder[i]);
}
}
}
The ObjectEnvelopeOrdering class addresses the following problems we observed
with the original ordering algorithm:
(1) the ordering is based on the modified state of the objects only; therefore
if a reference in object A is set to null, OJB does not see that before
modification A referenced an object B to be deleted.
(2) 1:n and m:n collections are treated in the same way, although the
FK-location in the DB is quite different.
(3) the ordering algorithm is 'greedy' in the sense that once an object
modification has been put into the ordered list, it will stay at this position
even if later constraints are found that would require to move it to a position
further down.
(4) issue (3) is aggravated by the fact that the ordering does not take into
account the modification state of a referenced object. Therefore objects are
inserted into the ordered list even if there is no real need for ordering. Later
a real constraint me be encountered, but now the object is already frozen at its
new position.
The ObjectEnvelopeOrdering class uses a graph-theoretical approach to order the
object envelopes (see the JavaDoc for details). Edges in this graph are inserted
only if there really is a need for ordering two object envelopes with respect to
each other - determining this need is based on the modification state of both
objects and the type of relation the two have to each other (1:1, 1:n, or m:n).
This addresses issues (2)-(4).
Issue (1) is not addressed as as niftily: Since we did not want to change the
ObjectEnvelope class, we opted for a heuristic solution, where 'potential'
relations between two objects are taken into account based on the class type of
a reference.
Test results:
After using the ObjectEnvelopeOrdering class we were able to remove all flush
statements from our application without any test case failing. The results of
the JUnit tests of OJB did not change either (some fail before and after the
change), with one exception:
org.apache.ojb.broker.sequence.NativeIdentifierTest.testReferenceInsertUpdateODMG.
Before our change, this test failed with a failed assertion, after our change it
now causes an FK violation error. Looking at the test code, I cannot see how the
FK error could be avoided, because there are two tables with FKs referencing
each other and the test attempts to insert two objects with references to each
other in a single transaction. As far as I can see, there is no order of INSERT
statements that could avoid the FK error.
Performance:
The ordering process implemented by the ObjectEnvelopeOrdering class is
certainly slower than the original recursive ordering. This is mainly due to
the need of addressing issue (1). In our real application scenario, however, we
do not notice any perfomance degradation.
AFAIK the OJB mailing list does not accept attachements, therefore I am posting
the class code inline. If anyone knows a better way to submit the code without
distortion due to line breaks, please let me know.
We would be happy if the class would make it into the 'official' OJB. In any
case feel free to use it if it suits you. Of course the usual disclaimer apply
(no warranty of any kind...)
Gerhard
-------------------------------
package org.apache.ojb.odmg;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import org.apache.ojb.broker.Identity;
import org.apache.ojb.broker.OJBRuntimeException;
import org.apache.ojb.broker.PersistenceBroker;
import org.apache.ojb.broker.core.proxy.ProxyHelper;
import org.apache.ojb.broker.metadata.ClassDescriptor;
import org.apache.ojb.broker.metadata.CollectionDescriptor;
import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
import org.apache.ojb.broker.util.logging.Logger;
import org.apache.ojb.broker.util.logging.LoggerFactory;
import org.apache.ojb.odmg.states.ModificationState;
/**
* <p>Implements an algorithm for reordering the object envelopes of a pending
* transaction to minimized the probability of foreign key constraint
* violations.</p>
*
* <p>The algorithm is based on a graph theoretical approach: Each object
* envelope is represented by a vertex in a graph. Each possible constraint
* on the order of database operations is represented by a directed edge
* in this graph, in which the initial vertex represents the object envelope
* to be sent to the database first and the terminal index represents the
* object envelope that might cause a FK violation if the initial vertex
* has not been sent to the database before.</p>
*
* <p>Additionally the edges in this graph are weighted. This is necessary
* because the object envelopes provide only information on the relation
* between objects <strong>after</strong> the transaction. FK violations,
* however, can also occur due to relations that existed <strong>before</strong>
* the transaction. Therefore the algorithm also considers potential relations
* between objects due to the fact that an object is of a class that is
* the item class of a object or collection reference of another object.
* Graph edges representing such potential relationships receive a lower
* weight than edges representing concrete relationships that exist in the
* current state of the object model.</p>
*
* <p>Once all graph edges have been established, the algorithm proceeds as
* follows:</p>
* <ol>
* <li>Iterate through all vertices and sum up the weight of all incoming
* edges (i.e. those edges whose terminal vertex is the current
vertex).</li>
* <li>Find the minimum value of this weight sums (ideally this minimum is
zero,
* meaning that there are object envelopes that can be sent to the
* database without risking FK violations)<il>
* <li>Add all vertices with a weight sum that is equal to this minimum to the
* reordered sequence of object envelopes and remove the vertices
* and all connected edges from the graph.</li>
* <li>If there are vertices left, repeat steps (1) through (3), otherwise
* we are done.
* </ol>
*
* @author Gerhard Grosse
* @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2004/11/18 12:25:28 grosse
Exp $
* @since Nov 15, 2004
*/
public class ObjectEnvelopeOrdering
{
private static final int CONCRETE_EDGE_WEIGHT = 2;
private static final int POTENTIAL_EDGE_WEIGHT = 1;
private static Logger log =
LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
private List originalOrder;
private Map envelopes;
private TransactionImpl transaction;
private Vertex[] vertices;
private Map edgeMap;
private int newOrderIndex;
private Identity[] newOrder;
/**
* Creates an object envelope ordering based on an original ordering
* of Identity objects and an Identity->ObjectEnvelope map
* @param originalOrder a list of Identity objects
* @param envelopes a map with ObjectEnvelope-s with their respective
* Identity-s as key
*/
public ObjectEnvelopeOrdering(
TransactionImpl transaction,
List originalOrder,
Map envelopes)
{
this.originalOrder = originalOrder;
this.envelopes = envelopes;
this.transaction = transaction;
}
/**
* Reorders the object envelopes. The new order is available from the
* <code>ordering</code> property.
* @see #getOrdering()
*/
public void reorder()
{
long t1 = 0, t2 = 0, t3 = 0;
if (log.isDebugEnabled())
{
t1 = System.currentTimeMillis();
}
newOrder = new Identity[originalOrder.size()];
newOrderIndex = 0;
// set up the vertex array in the order the envelopes were added
List vertexList = new ArrayList(originalOrder.size());
int vertexIndex = 0;
for (Iterator it = originalOrder.iterator(); it.hasNext();)
{
ObjectEnvelope envelope = (ObjectEnvelope) envelopes.get(it.next());
if (envelope.needsUpdate()
|| envelope.needsInsert()
|| envelope.needsDelete())
{
Vertex vertex = new Vertex(envelope);
vertexList.add(vertex);
}
else
{
// envelope is clean - just add identity to new order
newOrder[newOrderIndex++] = envelope.getIdentity();
}
}
vertices = (Vertex[]) vertexList.toArray(new Vertex[vertexList.size()]);
// set up the edges
edgeMap = new HashMap(2 * vertices.length, 0.75f);
for (int i = 0; i < vertices.length; i++)
{
addEdgesForVertex(vertices[i]);
}
if (log.isDebugEnabled())
{
t2 = System.currentTimeMillis();
log.debug(
"Building object envelope graph took " + (t2 - t1) + " ms");
log.debug(
"Object envelope graph contains "
+ vertices.length
+ " vertices"
+ " and "
+ edgeMap.size()
+ " edges");
}
int remainingVertices = vertices.length;
int iterationCount = 0;
while (remainingVertices > 0)
{
// update iteration count
iterationCount++;
// update incoming edge counts
for (Iterator it = edgeMap.values().iterator(); it.hasNext();)
{
Edge edge = (Edge) it.next();
if (!edge.isProcessed())
{
edge.getTerminalVertex().incrementIncomingEdgeWeight(
edge.getWeight());
}
}
// find minimum weight of incoming edges of a vertex
int minIncomingEdgeWeight = Integer.MAX_VALUE;
for (int i = 0; i < vertices.length; i++)
{
Vertex vertex = vertices[i];
if (!vertex.isProcessed()
&& minIncomingEdgeWeight > vertex.getIncomingEdgeWeight())
{
minIncomingEdgeWeight = vertex.getIncomingEdgeWeight();
if (minIncomingEdgeWeight == 0)
{
// we won't get any lower
break;
}
}
}
// process vertices having minimum incoming edge weight
int processCount = 0;
for (int i = 0; i < vertices.length; i++)
{
Vertex vertex = vertices[i];
if (!vertex.isProcessed()
&& vertex.getIncomingEdgeWeight() == minIncomingEdgeWeight)
{
newOrder[newOrderIndex++] =
vertex.getEnvelope().getIdentity();
vertex.markProcessed();
processCount++;
}
vertex.resetIncomingEdgeWeight();
}
if (log.isDebugEnabled())
{
log.debug(
"Processed "
+ processCount
+ " of "
+ remainingVertices
+ " remaining vertices in iteration #"
+ iterationCount);
}
remainingVertices -= processCount;
}
if (log.isDebugEnabled())
{
t3 = System.currentTimeMillis();
log.debug(
"Processing object envelope graph took " + (t3 - t2) + " ms");
}
}
/**
* Gets the reordered sequence of object envelopes
* @return an array of Identity objects representing the opimized sequence
* of database operations
*/
public Identity[] getOrdering()
{
if (newOrder == null)
{
reorder();
}
return newOrder;
}
/**
* Adds all edges for a given object envelope vertex. All edges are
* added to the edgeMap map.
* @param vertex the Vertex object to find edges for
*/
private void addEdgesForVertex(Vertex vertex)
{
PersistenceBroker broker = transaction.getBroker();
Object object = vertex.getEnvelope().getObject();
ClassDescriptor cld = broker.getClassDescriptor(object.getClass());
Iterator rdsIter = cld.getObjectReferenceDescriptors().iterator();
while (rdsIter.hasNext())
{
ObjectReferenceDescriptor rds =
(ObjectReferenceDescriptor) rdsIter.next();
addObjectReferenceEdges(vertex, rds);
}
Iterator cdsIter = cld.getCollectionDescriptors().iterator();
while (cdsIter.hasNext())
{
CollectionDescriptor cds = (CollectionDescriptor) cdsIter.next();
addCollectionEdges(vertex, cds);
}
}
/**
* Finds edges based to a specific object reference descriptor and
* adds them to the edge map.
* @param vertex the object envelope vertex holding the object reference
* @param rds the object reference descriptor
*/
private void addObjectReferenceEdges(
Vertex vertex,
ObjectReferenceDescriptor rds)
{
Object refObject =
rds.getPersistentField().get(vertex.getEnvelope().getObject());
Class refClass = rds.getItemClass();
for (int i = 0; i < vertices.length; i++)
{
Edge edge = null;
ObjectEnvelope envelope = vertex.getEnvelope();
Vertex refVertex = vertices[i];
ObjectEnvelope refEnvelope = refVertex.getEnvelope();
if (refObject == refEnvelope.getObject())
{
edge = buildConcrete11Edge(vertex, refVertex);
}
else if (refClass.isInstance(refVertex.getEnvelope().getObject()))
{
edge = buildPotential11Edge(vertex, refVertex);
}
if (edge != null)
{
Edge existingEdge = (Edge) edgeMap.get(edge);
if (existingEdge == null)
{
edgeMap.put(edge, edge);
}
else
{
existingEdge.increaseWeightTo(edge.getWeight());
}
}
}
}
/**
* Finds edges base on a specific collection descriptor (1:n and m:n)
* and adds them to the edge map.
* @param vertex the object envelope vertex holding the collection
* @param cds the collection descriptor
*/
private void addCollectionEdges(Vertex vertex, CollectionDescriptor cds)
{
ObjectEnvelope envelope = vertex.getEnvelope();
Object col = cds.getPersistentField().get(envelope.getObject());
Object[] refObjects;
if (col == null
|| (ProxyHelper.isCollectionProxy(col)
&& !ProxyHelper.getCollectionProxy(col).isLoaded()))
{
refObjects = new Object[0];
}
else
{
if (col instanceof Collection)
{
refObjects = ((Collection) col).toArray();
}
else if (col instanceof Object[])
{
refObjects = (Object[]) col;
}
else
{
throw new OJBRuntimeException(
"Given object collection of type "
+ col.getClass()
+ " can not be managed by OJB. Use Array, Collection or
ManageableCollection instead!");
}
}
Class refClass = cds.getItemClass();
for (int i = 0; i < vertices.length; i++)
{
Edge edge = null;
Vertex refVertex = vertices[i];
ObjectEnvelope refEnvelope = refVertex.getEnvelope();
if (refClass.isInstance(refEnvelope.getObject()))
{
if (containsObject(refEnvelope.getObject(), refObjects))
{
if (cds.isMtoNRelation())
{
edge = buildConcreteMNEdge(vertex, refVertex);
}
else
{
edge = buildConcrete1NEdge(vertex, refVertex);
}
}
else
{
if (cds.isMtoNRelation())
{
edge = buildPotentialMNEdge(vertex, refVertex);
}
else
{
edge = buildPotential1NEdge(vertex, refVertex);
}
}
}
if (edge != null)
{
Edge existingEdge = (Edge) edgeMap.get(edge);
if (existingEdge == null)
{
edgeMap.put(edge, edge);
}
else
{
existingEdge.increaseWeightTo(edge.getWeight());
}
}
}
}
/**
* Helper method that searches an object array for the occurence of a
* specific object based on reference equality
* @param searchFor the object to search for
* @param searchIn the array to search in
* @return true if the object is found, otherwise false
*/
private static boolean containsObject(Object searchFor, Object[] searchIn)
{
for (int i = 0; i < searchIn.length; i++)
{
if (searchFor == searchIn[i])
{
return true;
}
}
return false;
}
/**
* Checks if the database operations associated with two object envelopes
* that are related via an 1:1 (or n:1) reference needs to be performed
* in a particular order and if so builds and returns a corresponding
* directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
* The following cases are considered (* means object needs update, + means
* object needs insert, - means object needs to be deleted):
* <table>
* <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)* -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
* <tr><td>(1)* -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
* <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)+ -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
* <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
* <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
* <table>
* @param vertex1 object envelope vertex of the object holding the reference
* @param vertex2 object envelope vertex of the referenced object
* @return an Edge object or null if the two database operations can
* be performed in any order
*/
protected Edge buildConcrete11Edge(Vertex vertex1, Vertex vertex2)
{
ModificationState state1 = vertex1.getEnvelope().getModificationState();
ModificationState state2 = vertex2.getEnvelope().getModificationState();
if (state1.needsUpdate() || state1.needsInsert())
{
if (state2.needsInsert())
{
// (2) must be inserted before (1) can point to it
return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
}
}
else if (state1.needsDelete())
{
if (state2.needsDelete())
{
// (1) points to (2) and must be deleted first
return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
}
}
return null;
}
/**
* Checks if the database operations associated with two object envelopes
* that might have been related via an 1:1 (or n:1) reference before
* the current transaction needs to be performed
* in a particular order and if so builds and returns a corresponding
* directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
* The following cases are considered (* means object needs update, + means
* object needs insert, - means object needs to be deleted):
* <table>
* <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)* -(1:1)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)* -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
* <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)+ -(1:1)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
* <table>
* @param vertex1 object envelope vertex of the object that might have
* hold the reference
* @param vertex2 object envelope vertex of the potentially referenced
* object
* @return an Edge object or null if the two database operations can
* be performed in any order
*/
protected Edge buildPotential11Edge(Vertex vertex1, Vertex vertex2)
{
ModificationState state1 = vertex1.getEnvelope().getModificationState();
ModificationState state2 = vertex2.getEnvelope().getModificationState();
if (state1.needsUpdate() || state1.needsDelete())
{
if (state2.needsDelete())
{
// old version of (1) might point to (2)
return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
}
}
return null;
}
/**
* Checks if the database operations associated with two object envelopes
* that are related via an 1:n collection reference needs to be performed
* in a particular order and if so builds and returns a corresponding
* directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
* The following cases are considered (* means object needs update, + means
* object needs insert, - means object needs to be deleted):
* <table>
* <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
* <tr><td>(1)+ -(1:n)-> (2)*</td><td>(1)->(2) edge</td></tr>
* <tr><td>(1)+ -(1:n)-> (2)+</td><td>(1)->(2) edge</td></tr>
* <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
* <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
* <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
* <table>
* @param vertex1 object envelope vertex of the object holding the
* collection
* @param vertex2 object envelope vertex of the object contained in the
* collection
* @return an Edge object or null if the two database operations can
* be performed in any order
*/
protected Edge buildConcrete1NEdge(Vertex vertex1, Vertex vertex2)
{
ModificationState state1 = vertex1.getEnvelope().getModificationState();
ModificationState state2 = vertex2.getEnvelope().getModificationState();
if (state1.needsInsert())
{
if (state2.needsUpdate() || state2.needsInsert())
{
// (2) now contains an FK to (1) thus (1) must be inserted first
return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
}
}
else if (state1.needsDelete())
{
if (state2.needsUpdate() || state2.needsDelete())
{
// Before deleting (1) give (2) a chance to drop its FK to it
return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
}
}
return null;
}
/**
* Checks if the database operations associated with two object envelopes
* that are might have been related via an 1:n collection reference before
* the current transaction needs to be performed
* in a particular order and if so builds and returns a corresponding
* directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
* The following cases are considered (* means object needs update, + means
* object needs insert, - means object needs to be deleted):
* <table>
* <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
* <tr><td>(1)+ -(1:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)+ -(1:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
* <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
* <table>
* @param vertex1 object envelope vertex of the object holding the
* collection
* @param vertex2 object envelope vertex of the object that might have
* been contained in the collection
* @return an Edge object or null if the two database operations can
* be performed in any order
*/
protected Edge buildPotential1NEdge(Vertex vertex1, Vertex vertex2)
{
ModificationState state1 = vertex1.getEnvelope().getModificationState();
ModificationState state2 = vertex2.getEnvelope().getModificationState();
if (state1.needsDelete())
{
if (state2.needsUpdate() || state2.needsDelete())
{
// Before deleting (1) give potential previous collection
// members a chance to drop their FKs to it
return new Edge(vertex2, vertex1, POTENTIAL_EDGE_WEIGHT);
}
}
return null;
}
/**
* Checks if the database operations associated with two object envelopes
* that are related via an m:n collection reference needs to be performed
* in a particular order and if so builds and returns a corresponding
* directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
* The following cases are considered (* means object needs update, + means
* object needs insert, - means object needs to be deleted):
* <table>
* <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)* -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
* <tr><td>(1)* -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
* <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)+ -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
* <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
* <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
* <table>
* @param vertex1 object envelope vertex of the object holding the
* collection
* @param vertex2 object envelope vertex of the object contained in the
* collection
* @return an Edge object or null if the two database operations can
* be performed in any order
*/
protected Edge buildConcreteMNEdge(Vertex vertex1, Vertex vertex2)
{
ModificationState state1 = vertex1.getEnvelope().getModificationState();
ModificationState state2 = vertex2.getEnvelope().getModificationState();
if (state1.needsUpdate() || state1.needsInsert())
{
if (state2.needsInsert())
{
// (2) must be inserted before we can create a link to it
return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
}
}
else if (state1.needsDelete())
{
if (state2.needsDelete())
{
// there is a link from (1) to (2) which must be deleted first,
// which will happen when deleting (1) - thus:
return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
}
}
return null;
}
/**
* Checks if the database operations associated with two object envelopes
* that might have been related via an m:n collection reference before
* the current transaction needs to be performed
* in a particular order and if so builds and returns a corresponding
* directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
* The following cases are considered (* means object needs update, + means
* object needs insert, - means object needs to be deleted):
* <table>
* <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)* -(m:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)* -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
* <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)+ -(m:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge</td></tr>
* <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
* <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
* <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
* <table>
* @param vertex1 object envelope vertex of the object holding the
* collection
* @param vertex2 object envelope vertex of the object that might have
* been contained in the collection
* @return an Edge object or null if the two database operations can
* be performed in any order
*/
protected Edge buildPotentialMNEdge(Vertex vertex1, Vertex vertex2)
{
ModificationState state1 = vertex1.getEnvelope().getModificationState();
ModificationState state2 = vertex2.getEnvelope().getModificationState();
if (state1.needsUpdate() || state1.needsDelete())
{
if (state2.needsDelete())
{
// old version of (1) might comprise a link to (2)
return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
}
}
return null;
}
/**
* Represents an edge in the object envelope graph
*/
private static class Edge
{
private Vertex initial;
private Vertex terminal;
private Identity initialIdentity;
private Identity terminalIdentity;
private int weight;
private boolean knownToBeProcessed;
private int hashCode;
public Edge(Vertex initial, Vertex terminal, int weight)
{
this.initial = initial;
this.terminal = terminal;
this.initialIdentity = initial.getEnvelope().getIdentity();
this.terminalIdentity = terminal.getEnvelope().getIdentity();
this.weight = weight;
this.knownToBeProcessed = false;
this.hashCode =
initialIdentity.hashCode() + 13 * terminalIdentity.hashCode();
}
public Vertex getInitialVertex()
{
return initial;
}
public Vertex getTerminalVertex()
{
return terminal;
}
public boolean connects(Vertex vertex)
{
return initial == vertex || terminal == vertex;
}
public void increaseWeightTo(int minWeight)
{
if (weight < minWeight)
{
weight = minWeight;
}
}
public int getWeight()
{
return weight;
}
public boolean isProcessed()
{
if (knownToBeProcessed)
{
return true;
}
else
{
boolean processed =
initial.isProcessed() || terminal.isProcessed();
if (processed)
{
knownToBeProcessed = true;
}
return processed;
}
}
public boolean equals(Object obj)
{
if (obj instanceof Edge)
{
Edge other = (Edge) obj;
return this.initialIdentity.equals(other.initialIdentity)
&& this.terminalIdentity.equals(other.terminalIdentity);
}
else
{
return false;
}
}
public int hashCode()
{
return hashCode;
}
}
/**
* Represents a vertex in the object envelope graph
*/
private static class Vertex
{
private ObjectEnvelope envelope;
private boolean processed;
private int incomingEdgeWeight;
public Vertex(ObjectEnvelope envelope)
{
this.envelope = envelope;
this.incomingEdgeWeight = 0;
this.processed = false;
}
public ObjectEnvelope getEnvelope()
{
return envelope;
}
public void markProcessed()
{
processed = true;
}
public boolean isProcessed()
{
return processed;
}
public void resetIncomingEdgeWeight()
{
incomingEdgeWeight = 0;
}
public void incrementIncomingEdgeWeight(int weight)
{
incomingEdgeWeight += weight;
}
public int getIncomingEdgeWeight()
{
return incomingEdgeWeight;
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-dev-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Brian McCallister <bm...@gmail.com>.
I had an implementation based on commons-graph from
jakarta-commons-sandbox. I ripped it out as I am very uncomfortable
being dependent on a sandbox component for which none of us are a
contributor.
Right now the Dirty* stuff does a very bad sort (INSERT -> UPDATE ->
DELETE) which works as long as no inserts depend on each other, and
you don't use serializable transactions at the DB level (prone to
deadlocks). Not a good option.
-Brian
On Sun, 21 Nov 2004 10:26:35 +0100, Jakob Braeuchi <jb...@gmx.ch> wrote:
> hi brian,
>
> it imports org.apache.ojb.odmg.states.ModificationState.
> do you already have an implementation of the sort ?
>
> jakob
>
> Brian McCallister schrieb:
>
>
> > Fantastic!
> >
> > I haven't looked closely at the code yet, but is it dependent (for
> > operation, not compile ;-) on ODMG classes? I need the exact same
> > topological sort for the object space transaction stuff (against PB)
> > in 1.1 =)
> >
> > Thank you!
> >
> > -Brian
> >
> > On Thu, 18 Nov 2004 14:06:48 +0100, Gerhard Grosse
> > <ge...@lex-com.net> wrote:
> >
> >>Hi,
> >>
> >>for quite some time we were experiencing problems with FK constraint violations
> >>when committing ODMG transactions. We resolved these problems by inserting
> >>TransactionExt.flush() calls wherever necessary. However, this in turn produced
> >>deadlock problems under high server load. Therefore we decided to try and
> >>improve the ordering of the SQL sent to the database. These efforts resulted in
> >>a class org.ojb.odmg.ObjectEnvelopeOrdering which we hereby contribute to the
> >>OJB community, because other users seem to have similar problems.
> >>
> >>To use this class, the private method reorder() in class
> >>org.ojb.odmg.ObjectEnvelopeTable must be replaced with:
> >>
> >>private void reorder()
> >>{
> >> if (needsCommit)
> >> {
> >> ObjectEnvelopeOrdering ordering =
> >> new ObjectEnvelopeOrdering(transaction,mvOrderOfIds,mhtObjectEnvelopes);
> >> ordering.reorder();
> >> Identity[] newOrder = ordering.getOrdering();
> >> mvOrderOfIds.clear();
> >> for (int i = 0; i < newOrder.length; i++)
> >> {
> >> mvOrderOfIds.add(newOrder[i]);
> >> }
> >> }
> >>}
> >>
> >>The ObjectEnvelopeOrdering class addresses the following problems we observed
> >>with the original ordering algorithm:
> >>
> >>(1) the ordering is based on the modified state of the objects only; therefore
> >>if a reference in object A is set to null, OJB does not see that before
> >>modification A referenced an object B to be deleted.
> >>
> >>(2) 1:n and m:n collections are treated in the same way, although the
> >>FK-location in the DB is quite different.
> >>
> >>(3) the ordering algorithm is 'greedy' in the sense that once an object
> >>modification has been put into the ordered list, it will stay at this position
> >>even if later constraints are found that would require to move it to a position
> >>further down.
> >>
> >>(4) issue (3) is aggravated by the fact that the ordering does not take into
> >>account the modification state of a referenced object. Therefore objects are
> >>inserted into the ordered list even if there is no real need for ordering. Later
> >>a real constraint me be encountered, but now the object is already frozen at its
> >>new position.
> >>
> >>The ObjectEnvelopeOrdering class uses a graph-theoretical approach to order the
> >>object envelopes (see the JavaDoc for details). Edges in this graph are inserted
> >>only if there really is a need for ordering two object envelopes with respect to
> >>each other - determining this need is based on the modification state of both
> >>objects and the type of relation the two have to each other (1:1, 1:n, or m:n).
> >>This addresses issues (2)-(4).
> >>
> >>Issue (1) is not addressed as as niftily: Since we did not want to change the
> >>ObjectEnvelope class, we opted for a heuristic solution, where 'potential'
> >>relations between two objects are taken into account based on the class type of
> >>a reference.
> >>
> >>Test results:
> >>After using the ObjectEnvelopeOrdering class we were able to remove all flush
> >>statements from our application without any test case failing. The results of
> >>the JUnit tests of OJB did not change either (some fail before and after the
> >>change), with one exception:
> >>org.apache.ojb.broker.sequence.NativeIdentifierTest.testReferenceInsertUpdateODMG.
> >>Before our change, this test failed with a failed assertion, after our change it
> >>now causes an FK violation error. Looking at the test code, I cannot see how the
> >>FK error could be avoided, because there are two tables with FKs referencing
> >>each other and the test attempts to insert two objects with references to each
> >>other in a single transaction. As far as I can see, there is no order of INSERT
> >>statements that could avoid the FK error.
> >>
> >>Performance:
> >>The ordering process implemented by the ObjectEnvelopeOrdering class is
> >>certainly slower than the original recursive ordering. This is mainly due to
> >>the need of addressing issue (1). In our real application scenario, however, we
> >>do not notice any perfomance degradation.
> >>
> >>AFAIK the OJB mailing list does not accept attachements, therefore I am posting
> >>the class code inline. If anyone knows a better way to submit the code without
> >>distortion due to line breaks, please let me know.
> >>
> >>We would be happy if the class would make it into the 'official' OJB. In any
> >>case feel free to use it if it suits you. Of course the usual disclaimer apply
> >>(no warranty of any kind...)
> >>
> >>Gerhard
> >>
> >>-------------------------------
> >>
> >>package org.apache.ojb.odmg;
> >>
> >>import java.util.ArrayList;
> >>import java.util.Collection;
> >>import java.util.HashMap;
> >>import java.util.Iterator;
> >>import java.util.List;
> >>import java.util.Map;
> >>
> >>import org.apache.ojb.broker.Identity;
> >>import org.apache.ojb.broker.OJBRuntimeException;
> >>import org.apache.ojb.broker.PersistenceBroker;
> >>import org.apache.ojb.broker.core.proxy.ProxyHelper;
> >>import org.apache.ojb.broker.metadata.ClassDescriptor;
> >>import org.apache.ojb.broker.metadata.CollectionDescriptor;
> >>import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
> >>import org.apache.ojb.broker.util.logging.Logger;
> >>import org.apache.ojb.broker.util.logging.LoggerFactory;
> >>import org.apache.ojb.odmg.states.ModificationState;
> >>
> >>/**
> >> * <p>Implements an algorithm for reordering the object envelopes of a pending
> >> * transaction to minimized the probability of foreign key constraint
> >> * violations.</p>
> >> *
> >> * <p>The algorithm is based on a graph theoretical approach: Each object
> >> * envelope is represented by a vertex in a graph. Each possible constraint
> >> * on the order of database operations is represented by a directed edge
> >> * in this graph, in which the initial vertex represents the object envelope
> >> * to be sent to the database first and the terminal index represents the
> >> * object envelope that might cause a FK violation if the initial vertex
> >> * has not been sent to the database before.</p>
> >> *
> >> * <p>Additionally the edges in this graph are weighted. This is necessary
> >> * because the object envelopes provide only information on the relation
> >> * between objects <strong>after</strong> the transaction. FK violations,
> >> * however, can also occur due to relations that existed <strong>before</strong>
> >> * the transaction. Therefore the algorithm also considers potential relations
> >> * between objects due to the fact that an object is of a class that is
> >> * the item class of a object or collection reference of another object.
> >> * Graph edges representing such potential relationships receive a lower
> >> * weight than edges representing concrete relationships that exist in the
> >> * current state of the object model.</p>
> >> *
> >> * <p>Once all graph edges have been established, the algorithm proceeds as
> >> * follows:</p>
> >> * <ol>
> >> * <li>Iterate through all vertices and sum up the weight of all incoming
> >> * edges (i.e. those edges whose terminal vertex is the current
> >>vertex).</li>
> >> * <li>Find the minimum value of this weight sums (ideally this minimum is
> >>zero,
> >> * meaning that there are object envelopes that can be sent to the
> >> * database without risking FK violations)<il>
> >> * <li>Add all vertices with a weight sum that is equal to this minimum to the
> >> * reordered sequence of object envelopes and remove the vertices
> >> * and all connected edges from the graph.</li>
> >> * <li>If there are vertices left, repeat steps (1) through (3), otherwise
> >> * we are done.
> >> * </ol>
> >> *
> >> * @author Gerhard Grosse
> >> * @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2004/11/18 12:25:28 grosse
> >>Exp $
> >> * @since Nov 15, 2004
> >> */
> >>public class ObjectEnvelopeOrdering
> >>{
> >> private static final int CONCRETE_EDGE_WEIGHT = 2;
> >> private static final int POTENTIAL_EDGE_WEIGHT = 1;
> >>
> >> private static Logger log =
> >> LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
> >>
> >> private List originalOrder;
> >> private Map envelopes;
> >> private TransactionImpl transaction;
> >>
> >> private Vertex[] vertices;
> >> private Map edgeMap;
> >>
> >> private int newOrderIndex;
> >> private Identity[] newOrder;
> >>
> >> /**
> >> * Creates an object envelope ordering based on an original ordering
> >> * of Identity objects and an Identity->ObjectEnvelope map
> >> * @param originalOrder a list of Identity objects
> >> * @param envelopes a map with ObjectEnvelope-s with their respective
> >> * Identity-s as key
> >> */
> >> public ObjectEnvelopeOrdering(
> >> TransactionImpl transaction,
> >> List originalOrder,
> >> Map envelopes)
> >> {
> >> this.originalOrder = originalOrder;
> >> this.envelopes = envelopes;
> >> this.transaction = transaction;
> >> }
> >>
> >> /**
> >> * Reorders the object envelopes. The new order is available from the
> >> * <code>ordering</code> property.
> >> * @see #getOrdering()
> >> */
> >> public void reorder()
> >> {
> >> long t1 = 0, t2 = 0, t3 = 0;
> >> if (log.isDebugEnabled())
> >> {
> >> t1 = System.currentTimeMillis();
> >> }
> >> newOrder = new Identity[originalOrder.size()];
> >> newOrderIndex = 0;
> >>
> >> // set up the vertex array in the order the envelopes were added
> >> List vertexList = new ArrayList(originalOrder.size());
> >> int vertexIndex = 0;
> >> for (Iterator it = originalOrder.iterator(); it.hasNext();)
> >> {
> >> ObjectEnvelope envelope = (ObjectEnvelope) envelopes.get(it.next());
> >> if (envelope.needsUpdate()
> >> || envelope.needsInsert()
> >> || envelope.needsDelete())
> >> {
> >> Vertex vertex = new Vertex(envelope);
> >> vertexList.add(vertex);
> >> }
> >> else
> >> {
> >> // envelope is clean - just add identity to new order
> >> newOrder[newOrderIndex++] = envelope.getIdentity();
> >> }
> >> }
> >> vertices = (Vertex[]) vertexList.toArray(new Vertex[vertexList.size()]);
> >>
> >> // set up the edges
> >> edgeMap = new HashMap(2 * vertices.length, 0.75f);
> >> for (int i = 0; i < vertices.length; i++)
> >> {
> >> addEdgesForVertex(vertices[i]);
> >> }
> >>
> >> if (log.isDebugEnabled())
> >> {
> >> t2 = System.currentTimeMillis();
> >> log.debug(
> >> "Building object envelope graph took " + (t2 - t1) + " ms");
> >> log.debug(
> >> "Object envelope graph contains "
> >> + vertices.length
> >> + " vertices"
> >> + " and "
> >> + edgeMap.size()
> >> + " edges");
> >> }
> >>
> >> int remainingVertices = vertices.length;
> >> int iterationCount = 0;
> >> while (remainingVertices > 0)
> >> {
> >> // update iteration count
> >> iterationCount++;
> >>
> >> // update incoming edge counts
> >> for (Iterator it = edgeMap.values().iterator(); it.hasNext();)
> >> {
> >> Edge edge = (Edge) it.next();
> >> if (!edge.isProcessed())
> >> {
> >> edge.getTerminalVertex().incrementIncomingEdgeWeight(
> >> edge.getWeight());
> >> }
> >> }
> >>
> >> // find minimum weight of incoming edges of a vertex
> >> int minIncomingEdgeWeight = Integer.MAX_VALUE;
> >> for (int i = 0; i < vertices.length; i++)
> >> {
> >> Vertex vertex = vertices[i];
> >> if (!vertex.isProcessed()
> >> && minIncomingEdgeWeight > vertex.getIncomingEdgeWeight())
> >> {
> >> minIncomingEdgeWeight = vertex.getIncomingEdgeWeight();
> >> if (minIncomingEdgeWeight == 0)
> >> {
> >> // we won't get any lower
> >> break;
> >> }
> >> }
> >> }
> >>
> >> // process vertices having minimum incoming edge weight
> >> int processCount = 0;
> >> for (int i = 0; i < vertices.length; i++)
> >> {
> >> Vertex vertex = vertices[i];
> >> if (!vertex.isProcessed()
> >> && vertex.getIncomingEdgeWeight() == minIncomingEdgeWeight)
> >> {
> >> newOrder[newOrderIndex++] =
> >> vertex.getEnvelope().getIdentity();
> >> vertex.markProcessed();
> >> processCount++;
> >> }
> >> vertex.resetIncomingEdgeWeight();
> >> }
> >>
> >> if (log.isDebugEnabled())
> >> {
> >> log.debug(
> >> "Processed "
> >> + processCount
> >> + " of "
> >> + remainingVertices
> >> + " remaining vertices in iteration #"
> >> + iterationCount);
> >> }
> >> remainingVertices -= processCount;
> >> }
> >>
> >> if (log.isDebugEnabled())
> >> {
> >> t3 = System.currentTimeMillis();
> >> log.debug(
> >> "Processing object envelope graph took " + (t3 - t2) + " ms");
> >> }
> >>
> >> }
> >>
> >> /**
> >> * Gets the reordered sequence of object envelopes
> >> * @return an array of Identity objects representing the opimized sequence
> >> * of database operations
> >> */
> >> public Identity[] getOrdering()
> >> {
> >> if (newOrder == null)
> >> {
> >> reorder();
> >> }
> >> return newOrder;
> >> }
> >>
> >> /**
> >> * Adds all edges for a given object envelope vertex. All edges are
> >> * added to the edgeMap map.
> >> * @param vertex the Vertex object to find edges for
> >> */
> >> private void addEdgesForVertex(Vertex vertex)
> >> {
> >> PersistenceBroker broker = transaction.getBroker();
> >> Object object = vertex.getEnvelope().getObject();
> >> ClassDescriptor cld = broker.getClassDescriptor(object.getClass());
> >> Iterator rdsIter = cld.getObjectReferenceDescriptors().iterator();
> >> while (rdsIter.hasNext())
> >> {
> >> ObjectReferenceDescriptor rds =
> >> (ObjectReferenceDescriptor) rdsIter.next();
> >> addObjectReferenceEdges(vertex, rds);
> >> }
> >> Iterator cdsIter = cld.getCollectionDescriptors().iterator();
> >> while (cdsIter.hasNext())
> >> {
> >> CollectionDescriptor cds = (CollectionDescriptor) cdsIter.next();
> >> addCollectionEdges(vertex, cds);
> >> }
> >> }
> >>
> >> /**
> >> * Finds edges based to a specific object reference descriptor and
> >> * adds them to the edge map.
> >> * @param vertex the object envelope vertex holding the object reference
> >> * @param rds the object reference descriptor
> >> */
> >> private void addObjectReferenceEdges(
> >> Vertex vertex,
> >> ObjectReferenceDescriptor rds)
> >> {
> >> Object refObject =
> >> rds.getPersistentField().get(vertex.getEnvelope().getObject());
> >> Class refClass = rds.getItemClass();
> >> for (int i = 0; i < vertices.length; i++)
> >> {
> >> Edge edge = null;
> >> ObjectEnvelope envelope = vertex.getEnvelope();
> >> Vertex refVertex = vertices[i];
> >> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
> >> if (refObject == refEnvelope.getObject())
> >> {
> >> edge = buildConcrete11Edge(vertex, refVertex);
> >> }
> >> else if (refClass.isInstance(refVertex.getEnvelope().getObject()))
> >> {
> >> edge = buildPotential11Edge(vertex, refVertex);
> >> }
> >> if (edge != null)
> >> {
> >> Edge existingEdge = (Edge) edgeMap.get(edge);
> >> if (existingEdge == null)
> >> {
> >> edgeMap.put(edge, edge);
> >> }
> >> else
> >> {
> >> existingEdge.increaseWeightTo(edge.getWeight());
> >> }
> >> }
> >> }
> >> }
> >>
> >> /**
> >> * Finds edges base on a specific collection descriptor (1:n and m:n)
> >> * and adds them to the edge map.
> >> * @param vertex the object envelope vertex holding the collection
> >> * @param cds the collection descriptor
> >> */
> >> private void addCollectionEdges(Vertex vertex, CollectionDescriptor cds)
> >> {
> >> ObjectEnvelope envelope = vertex.getEnvelope();
> >> Object col = cds.getPersistentField().get(envelope.getObject());
> >> Object[] refObjects;
> >> if (col == null
> >> || (ProxyHelper.isCollectionProxy(col)
> >> && !ProxyHelper.getCollectionProxy(col).isLoaded()))
> >> {
> >> refObjects = new Object[0];
> >> }
> >> else
> >> {
> >> if (col instanceof Collection)
> >> {
> >> refObjects = ((Collection) col).toArray();
> >>
> >> }
> >> else if (col instanceof Object[])
> >> {
> >> refObjects = (Object[]) col;
> >> }
> >> else
> >> {
> >> throw new OJBRuntimeException(
> >> "Given object collection of type "
> >> + col.getClass()
> >> + " can not be managed by OJB. Use Array, Collection or
> >>ManageableCollection instead!");
> >> }
> >> }
> >> Class refClass = cds.getItemClass();
> >>
> >> for (int i = 0; i < vertices.length; i++)
> >> {
> >> Edge edge = null;
> >> Vertex refVertex = vertices[i];
> >> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
> >>
> >> if (refClass.isInstance(refEnvelope.getObject()))
> >> {
> >> if (containsObject(refEnvelope.getObject(), refObjects))
> >> {
> >> if (cds.isMtoNRelation())
> >> {
> >> edge = buildConcreteMNEdge(vertex, refVertex);
> >> }
> >> else
> >> {
> >> edge = buildConcrete1NEdge(vertex, refVertex);
> >> }
> >> }
> >> else
> >> {
> >> if (cds.isMtoNRelation())
> >> {
> >> edge = buildPotentialMNEdge(vertex, refVertex);
> >> }
> >> else
> >> {
> >> edge = buildPotential1NEdge(vertex, refVertex);
> >> }
> >> }
> >> }
> >> if (edge != null)
> >> {
> >> Edge existingEdge = (Edge) edgeMap.get(edge);
> >> if (existingEdge == null)
> >> {
> >> edgeMap.put(edge, edge);
> >> }
> >> else
> >> {
> >> existingEdge.increaseWeightTo(edge.getWeight());
> >> }
> >> }
> >> }
> >> }
> >>
> >> /**
> >> * Helper method that searches an object array for the occurence of a
> >> * specific object based on reference equality
> >> * @param searchFor the object to search for
> >> * @param searchIn the array to search in
> >> * @return true if the object is found, otherwise false
> >> */
> >> private static boolean containsObject(Object searchFor, Object[] searchIn)
> >> {
> >> for (int i = 0; i < searchIn.length; i++)
> >> {
> >> if (searchFor == searchIn[i])
> >> {
> >> return true;
> >> }
> >> }
> >> return false;
> >> }
> >>
> >> /**
> >> * Checks if the database operations associated with two object envelopes
> >> * that are related via an 1:1 (or n:1) reference needs to be performed
> >> * in a particular order and if so builds and returns a corresponding
> >> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> >> * The following cases are considered (* means object needs update, + means
> >> * object needs insert, - means object needs to be deleted):
> >> * <table>
> >> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
> >> * <tr><td>(1)* -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> >> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
> >> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> >> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> >> * <table>
> >> * @param vertex1 object envelope vertex of the object holding the reference
> >> * @param vertex2 object envelope vertex of the referenced object
> >> * @return an Edge object or null if the two database operations can
> >> * be performed in any order
> >> */
> >> protected Edge buildConcrete11Edge(Vertex vertex1, Vertex vertex2)
> >> {
> >> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> >> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> >> if (state1.needsUpdate() || state1.needsInsert())
> >> {
> >> if (state2.needsInsert())
> >> {
> >> // (2) must be inserted before (1) can point to it
> >> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> >> }
> >> }
> >> else if (state1.needsDelete())
> >> {
> >> if (state2.needsDelete())
> >> {
> >> // (1) points to (2) and must be deleted first
> >> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
> >> }
> >> }
> >> return null;
> >> }
> >>
> >> /**
> >> * Checks if the database operations associated with two object envelopes
> >> * that might have been related via an 1:1 (or n:1) reference before
> >> * the current transaction needs to be performed
> >> * in a particular order and if so builds and returns a corresponding
> >> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> >> * The following cases are considered (* means object needs update, + means
> >> * object needs insert, - means object needs to be deleted):
> >> * <table>
> >> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(1:1)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> >> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> >> * <table>
> >> * @param vertex1 object envelope vertex of the object that might have
> >> * hold the reference
> >> * @param vertex2 object envelope vertex of the potentially referenced
> >> * object
> >> * @return an Edge object or null if the two database operations can
> >> * be performed in any order
> >> */
> >> protected Edge buildPotential11Edge(Vertex vertex1, Vertex vertex2)
> >> {
> >> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> >> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> >> if (state1.needsUpdate() || state1.needsDelete())
> >> {
> >> if (state2.needsDelete())
> >> {
> >> // old version of (1) might point to (2)
> >> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> >> }
> >> }
> >> return null;
> >> }
> >>
> >> /**
> >> * Checks if the database operations associated with two object envelopes
> >> * that are related via an 1:n collection reference needs to be performed
> >> * in a particular order and if so builds and returns a corresponding
> >> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> >> * The following cases are considered (* means object needs update, + means
> >> * object needs insert, - means object needs to be deleted):
> >> * <table>
> >> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>(1)->(2) edge</td></tr>
> >> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>(1)->(2) edge</td></tr>
> >> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> >> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
> >> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
> >> * <table>
> >> * @param vertex1 object envelope vertex of the object holding the
> >> * collection
> >> * @param vertex2 object envelope vertex of the object contained in the
> >> * collection
> >> * @return an Edge object or null if the two database operations can
> >> * be performed in any order
> >> */
> >> protected Edge buildConcrete1NEdge(Vertex vertex1, Vertex vertex2)
> >> {
> >> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> >> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> >> if (state1.needsInsert())
> >> {
> >> if (state2.needsUpdate() || state2.needsInsert())
> >> {
> >> // (2) now contains an FK to (1) thus (1) must be inserted first
> >> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
> >> }
> >> }
> >> else if (state1.needsDelete())
> >> {
> >> if (state2.needsUpdate() || state2.needsDelete())
> >> {
> >> // Before deleting (1) give (2) a chance to drop its FK to it
> >> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> >> }
> >> }
> >> return null;
> >> }
> >>
> >> /**
> >> * Checks if the database operations associated with two object envelopes
> >> * that are might have been related via an 1:n collection reference before
> >> * the current transaction needs to be performed
> >> * in a particular order and if so builds and returns a corresponding
> >> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> >> * The following cases are considered (* means object needs update, + means
> >> * object needs insert, - means object needs to be deleted):
> >> * <table>
> >> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
> >> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
> >> * <table>
> >> * @param vertex1 object envelope vertex of the object holding the
> >> * collection
> >> * @param vertex2 object envelope vertex of the object that might have
> >> * been contained in the collection
> >> * @return an Edge object or null if the two database operations can
> >> * be performed in any order
> >> */
> >> protected Edge buildPotential1NEdge(Vertex vertex1, Vertex vertex2)
> >> {
> >> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> >> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> >> if (state1.needsDelete())
> >> {
> >> if (state2.needsUpdate() || state2.needsDelete())
> >> {
> >> // Before deleting (1) give potential previous collection
> >> // members a chance to drop their FKs to it
> >> return new Edge(vertex2, vertex1, POTENTIAL_EDGE_WEIGHT);
> >> }
> >> }
> >> return null;
> >> }
> >>
> >> /**
> >> * Checks if the database operations associated with two object envelopes
> >> * that are related via an m:n collection reference needs to be performed
> >> * in a particular order and if so builds and returns a corresponding
> >> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> >> * The following cases are considered (* means object needs update, + means
> >> * object needs insert, - means object needs to be deleted):
> >> * <table>
> >> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
> >> * <tr><td>(1)* -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> >> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
> >> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> >> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> >> * <table>
> >> * @param vertex1 object envelope vertex of the object holding the
> >> * collection
> >> * @param vertex2 object envelope vertex of the object contained in the
> >> * collection
> >> * @return an Edge object or null if the two database operations can
> >> * be performed in any order
> >> */
> >> protected Edge buildConcreteMNEdge(Vertex vertex1, Vertex vertex2)
> >> {
> >> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> >> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> >> if (state1.needsUpdate() || state1.needsInsert())
> >> {
> >> if (state2.needsInsert())
> >> {
> >> // (2) must be inserted before we can create a link to it
> >> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> >> }
> >> }
> >> else if (state1.needsDelete())
> >> {
> >> if (state2.needsDelete())
> >> {
> >> // there is a link from (1) to (2) which must be deleted first,
> >> // which will happen when deleting (1) - thus:
> >> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> >> }
> >> }
> >> return null;
> >> }
> >>
> >> /**
> >> * Checks if the database operations associated with two object envelopes
> >> * that might have been related via an m:n collection reference before
> >> * the current transaction needs to be performed
> >> * in a particular order and if so builds and returns a corresponding
> >> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> >> * The following cases are considered (* means object needs update, + means
> >> * object needs insert, - means object needs to be deleted):
> >> * <table>
> >> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(m:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)* -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> >> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
> >> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> >> * <table>
> >> * @param vertex1 object envelope vertex of the object holding the
> >> * collection
> >> * @param vertex2 object envelope vertex of the object that might have
> >> * been contained in the collection
> >> * @return an Edge object or null if the two database operations can
> >> * be performed in any order
> >> */
> >> protected Edge buildPotentialMNEdge(Vertex vertex1, Vertex vertex2)
> >> {
> >> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> >> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> >> if (state1.needsUpdate() || state1.needsDelete())
> >> {
> >> if (state2.needsDelete())
> >> {
> >> // old version of (1) might comprise a link to (2)
> >> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> >> }
> >> }
> >> return null;
> >> }
> >>
> >> /**
> >> * Represents an edge in the object envelope graph
> >> */
> >> private static class Edge
> >> {
> >> private Vertex initial;
> >> private Vertex terminal;
> >> private Identity initialIdentity;
> >> private Identity terminalIdentity;
> >> private int weight;
> >> private boolean knownToBeProcessed;
> >> private int hashCode;
> >>
> >> public Edge(Vertex initial, Vertex terminal, int weight)
> >> {
> >> this.initial = initial;
> >> this.terminal = terminal;
> >> this.initialIdentity = initial.getEnvelope().getIdentity();
> >> this.terminalIdentity = terminal.getEnvelope().getIdentity();
> >> this.weight = weight;
> >> this.knownToBeProcessed = false;
> >> this.hashCode =
> >> initialIdentity.hashCode() + 13 * terminalIdentity.hashCode();
> >> }
> >> public Vertex getInitialVertex()
> >> {
> >> return initial;
> >> }
> >> public Vertex getTerminalVertex()
> >> {
> >> return terminal;
> >> }
> >> public boolean connects(Vertex vertex)
> >> {
> >> return initial == vertex || terminal == vertex;
> >> }
> >> public void increaseWeightTo(int minWeight)
> >> {
> >> if (weight < minWeight)
> >> {
> >> weight = minWeight;
> >> }
> >> }
> >> public int getWeight()
> >> {
> >> return weight;
> >> }
> >> public boolean isProcessed()
> >> {
> >> if (knownToBeProcessed)
> >> {
> >> return true;
> >> }
> >> else
> >> {
> >> boolean processed =
> >> initial.isProcessed() || terminal.isProcessed();
> >> if (processed)
> >> {
> >> knownToBeProcessed = true;
> >> }
> >> return processed;
> >> }
> >> }
> >> public boolean equals(Object obj)
> >> {
> >> if (obj instanceof Edge)
> >> {
> >> Edge other = (Edge) obj;
> >> return this.initialIdentity.equals(other.initialIdentity)
> >> && this.terminalIdentity.equals(other.terminalIdentity);
> >> }
> >> else
> >> {
> >> return false;
> >> }
> >> }
> >> public int hashCode()
> >> {
> >> return hashCode;
> >> }
> >> }
> >>
> >> /**
> >> * Represents a vertex in the object envelope graph
> >> */
> >> private static class Vertex
> >> {
> >> private ObjectEnvelope envelope;
> >> private boolean processed;
> >> private int incomingEdgeWeight;
> >>
> >> public Vertex(ObjectEnvelope envelope)
> >> {
> >> this.envelope = envelope;
> >> this.incomingEdgeWeight = 0;
> >> this.processed = false;
> >> }
> >> public ObjectEnvelope getEnvelope()
> >> {
> >> return envelope;
> >> }
> >> public void markProcessed()
> >> {
> >> processed = true;
> >> }
> >> public boolean isProcessed()
> >> {
> >> return processed;
> >> }
> >> public void resetIncomingEdgeWeight()
> >> {
> >> incomingEdgeWeight = 0;
> >> }
> >> public void incrementIncomingEdgeWeight(int weight)
> >> {
> >> incomingEdgeWeight += weight;
> >> }
> >> public int getIncomingEdgeWeight()
> >> {
> >> return incomingEdgeWeight;
> >> }
> >> }
> >>
> >>}
> >>
> >>---------------------------------------------------------------------
> >>To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
> >>For additional commands, e-mail: ojb-dev-help@db.apache.org
> >>
> >>
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
> > For additional commands, e-mail: ojb-dev-help@db.apache.org
> >
> >
>
> ---------------------------------------------------------------------
>
>
> To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-dev-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-dev-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Jakob Braeuchi <jb...@gmx.ch>.
hi brian,
it imports org.apache.ojb.odmg.states.ModificationState.
do you already have an implementation of the sort ?
jakob
Brian McCallister schrieb:
> Fantastic!
>
> I haven't looked closely at the code yet, but is it dependent (for
> operation, not compile ;-) on ODMG classes? I need the exact same
> topological sort for the object space transaction stuff (against PB)
> in 1.1 =)
>
> Thank you!
>
> -Brian
>
> On Thu, 18 Nov 2004 14:06:48 +0100, Gerhard Grosse
> <ge...@lex-com.net> wrote:
>
>>Hi,
>>
>>for quite some time we were experiencing problems with FK constraint violations
>>when committing ODMG transactions. We resolved these problems by inserting
>>TransactionExt.flush() calls wherever necessary. However, this in turn produced
>>deadlock problems under high server load. Therefore we decided to try and
>>improve the ordering of the SQL sent to the database. These efforts resulted in
>>a class org.ojb.odmg.ObjectEnvelopeOrdering which we hereby contribute to the
>>OJB community, because other users seem to have similar problems.
>>
>>To use this class, the private method reorder() in class
>>org.ojb.odmg.ObjectEnvelopeTable must be replaced with:
>>
>>private void reorder()
>>{
>> if (needsCommit)
>> {
>> ObjectEnvelopeOrdering ordering =
>> new ObjectEnvelopeOrdering(transaction,mvOrderOfIds,mhtObjectEnvelopes);
>> ordering.reorder();
>> Identity[] newOrder = ordering.getOrdering();
>> mvOrderOfIds.clear();
>> for (int i = 0; i < newOrder.length; i++)
>> {
>> mvOrderOfIds.add(newOrder[i]);
>> }
>> }
>>}
>>
>>The ObjectEnvelopeOrdering class addresses the following problems we observed
>>with the original ordering algorithm:
>>
>>(1) the ordering is based on the modified state of the objects only; therefore
>>if a reference in object A is set to null, OJB does not see that before
>>modification A referenced an object B to be deleted.
>>
>>(2) 1:n and m:n collections are treated in the same way, although the
>>FK-location in the DB is quite different.
>>
>>(3) the ordering algorithm is 'greedy' in the sense that once an object
>>modification has been put into the ordered list, it will stay at this position
>>even if later constraints are found that would require to move it to a position
>>further down.
>>
>>(4) issue (3) is aggravated by the fact that the ordering does not take into
>>account the modification state of a referenced object. Therefore objects are
>>inserted into the ordered list even if there is no real need for ordering. Later
>>a real constraint me be encountered, but now the object is already frozen at its
>>new position.
>>
>>The ObjectEnvelopeOrdering class uses a graph-theoretical approach to order the
>>object envelopes (see the JavaDoc for details). Edges in this graph are inserted
>>only if there really is a need for ordering two object envelopes with respect to
>>each other - determining this need is based on the modification state of both
>>objects and the type of relation the two have to each other (1:1, 1:n, or m:n).
>>This addresses issues (2)-(4).
>>
>>Issue (1) is not addressed as as niftily: Since we did not want to change the
>>ObjectEnvelope class, we opted for a heuristic solution, where 'potential'
>>relations between two objects are taken into account based on the class type of
>>a reference.
>>
>>Test results:
>>After using the ObjectEnvelopeOrdering class we were able to remove all flush
>>statements from our application without any test case failing. The results of
>>the JUnit tests of OJB did not change either (some fail before and after the
>>change), with one exception:
>>org.apache.ojb.broker.sequence.NativeIdentifierTest.testReferenceInsertUpdateODMG.
>>Before our change, this test failed with a failed assertion, after our change it
>>now causes an FK violation error. Looking at the test code, I cannot see how the
>>FK error could be avoided, because there are two tables with FKs referencing
>>each other and the test attempts to insert two objects with references to each
>>other in a single transaction. As far as I can see, there is no order of INSERT
>>statements that could avoid the FK error.
>>
>>Performance:
>>The ordering process implemented by the ObjectEnvelopeOrdering class is
>>certainly slower than the original recursive ordering. This is mainly due to
>>the need of addressing issue (1). In our real application scenario, however, we
>>do not notice any perfomance degradation.
>>
>>AFAIK the OJB mailing list does not accept attachements, therefore I am posting
>>the class code inline. If anyone knows a better way to submit the code without
>>distortion due to line breaks, please let me know.
>>
>>We would be happy if the class would make it into the 'official' OJB. In any
>>case feel free to use it if it suits you. Of course the usual disclaimer apply
>>(no warranty of any kind...)
>>
>>Gerhard
>>
>>-------------------------------
>>
>>package org.apache.ojb.odmg;
>>
>>import java.util.ArrayList;
>>import java.util.Collection;
>>import java.util.HashMap;
>>import java.util.Iterator;
>>import java.util.List;
>>import java.util.Map;
>>
>>import org.apache.ojb.broker.Identity;
>>import org.apache.ojb.broker.OJBRuntimeException;
>>import org.apache.ojb.broker.PersistenceBroker;
>>import org.apache.ojb.broker.core.proxy.ProxyHelper;
>>import org.apache.ojb.broker.metadata.ClassDescriptor;
>>import org.apache.ojb.broker.metadata.CollectionDescriptor;
>>import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
>>import org.apache.ojb.broker.util.logging.Logger;
>>import org.apache.ojb.broker.util.logging.LoggerFactory;
>>import org.apache.ojb.odmg.states.ModificationState;
>>
>>/**
>> * <p>Implements an algorithm for reordering the object envelopes of a pending
>> * transaction to minimized the probability of foreign key constraint
>> * violations.</p>
>> *
>> * <p>The algorithm is based on a graph theoretical approach: Each object
>> * envelope is represented by a vertex in a graph. Each possible constraint
>> * on the order of database operations is represented by a directed edge
>> * in this graph, in which the initial vertex represents the object envelope
>> * to be sent to the database first and the terminal index represents the
>> * object envelope that might cause a FK violation if the initial vertex
>> * has not been sent to the database before.</p>
>> *
>> * <p>Additionally the edges in this graph are weighted. This is necessary
>> * because the object envelopes provide only information on the relation
>> * between objects <strong>after</strong> the transaction. FK violations,
>> * however, can also occur due to relations that existed <strong>before</strong>
>> * the transaction. Therefore the algorithm also considers potential relations
>> * between objects due to the fact that an object is of a class that is
>> * the item class of a object or collection reference of another object.
>> * Graph edges representing such potential relationships receive a lower
>> * weight than edges representing concrete relationships that exist in the
>> * current state of the object model.</p>
>> *
>> * <p>Once all graph edges have been established, the algorithm proceeds as
>> * follows:</p>
>> * <ol>
>> * <li>Iterate through all vertices and sum up the weight of all incoming
>> * edges (i.e. those edges whose terminal vertex is the current
>>vertex).</li>
>> * <li>Find the minimum value of this weight sums (ideally this minimum is
>>zero,
>> * meaning that there are object envelopes that can be sent to the
>> * database without risking FK violations)<il>
>> * <li>Add all vertices with a weight sum that is equal to this minimum to the
>> * reordered sequence of object envelopes and remove the vertices
>> * and all connected edges from the graph.</li>
>> * <li>If there are vertices left, repeat steps (1) through (3), otherwise
>> * we are done.
>> * </ol>
>> *
>> * @author Gerhard Grosse
>> * @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2004/11/18 12:25:28 grosse
>>Exp $
>> * @since Nov 15, 2004
>> */
>>public class ObjectEnvelopeOrdering
>>{
>> private static final int CONCRETE_EDGE_WEIGHT = 2;
>> private static final int POTENTIAL_EDGE_WEIGHT = 1;
>>
>> private static Logger log =
>> LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
>>
>> private List originalOrder;
>> private Map envelopes;
>> private TransactionImpl transaction;
>>
>> private Vertex[] vertices;
>> private Map edgeMap;
>>
>> private int newOrderIndex;
>> private Identity[] newOrder;
>>
>> /**
>> * Creates an object envelope ordering based on an original ordering
>> * of Identity objects and an Identity->ObjectEnvelope map
>> * @param originalOrder a list of Identity objects
>> * @param envelopes a map with ObjectEnvelope-s with their respective
>> * Identity-s as key
>> */
>> public ObjectEnvelopeOrdering(
>> TransactionImpl transaction,
>> List originalOrder,
>> Map envelopes)
>> {
>> this.originalOrder = originalOrder;
>> this.envelopes = envelopes;
>> this.transaction = transaction;
>> }
>>
>> /**
>> * Reorders the object envelopes. The new order is available from the
>> * <code>ordering</code> property.
>> * @see #getOrdering()
>> */
>> public void reorder()
>> {
>> long t1 = 0, t2 = 0, t3 = 0;
>> if (log.isDebugEnabled())
>> {
>> t1 = System.currentTimeMillis();
>> }
>> newOrder = new Identity[originalOrder.size()];
>> newOrderIndex = 0;
>>
>> // set up the vertex array in the order the envelopes were added
>> List vertexList = new ArrayList(originalOrder.size());
>> int vertexIndex = 0;
>> for (Iterator it = originalOrder.iterator(); it.hasNext();)
>> {
>> ObjectEnvelope envelope = (ObjectEnvelope) envelopes.get(it.next());
>> if (envelope.needsUpdate()
>> || envelope.needsInsert()
>> || envelope.needsDelete())
>> {
>> Vertex vertex = new Vertex(envelope);
>> vertexList.add(vertex);
>> }
>> else
>> {
>> // envelope is clean - just add identity to new order
>> newOrder[newOrderIndex++] = envelope.getIdentity();
>> }
>> }
>> vertices = (Vertex[]) vertexList.toArray(new Vertex[vertexList.size()]);
>>
>> // set up the edges
>> edgeMap = new HashMap(2 * vertices.length, 0.75f);
>> for (int i = 0; i < vertices.length; i++)
>> {
>> addEdgesForVertex(vertices[i]);
>> }
>>
>> if (log.isDebugEnabled())
>> {
>> t2 = System.currentTimeMillis();
>> log.debug(
>> "Building object envelope graph took " + (t2 - t1) + " ms");
>> log.debug(
>> "Object envelope graph contains "
>> + vertices.length
>> + " vertices"
>> + " and "
>> + edgeMap.size()
>> + " edges");
>> }
>>
>> int remainingVertices = vertices.length;
>> int iterationCount = 0;
>> while (remainingVertices > 0)
>> {
>> // update iteration count
>> iterationCount++;
>>
>> // update incoming edge counts
>> for (Iterator it = edgeMap.values().iterator(); it.hasNext();)
>> {
>> Edge edge = (Edge) it.next();
>> if (!edge.isProcessed())
>> {
>> edge.getTerminalVertex().incrementIncomingEdgeWeight(
>> edge.getWeight());
>> }
>> }
>>
>> // find minimum weight of incoming edges of a vertex
>> int minIncomingEdgeWeight = Integer.MAX_VALUE;
>> for (int i = 0; i < vertices.length; i++)
>> {
>> Vertex vertex = vertices[i];
>> if (!vertex.isProcessed()
>> && minIncomingEdgeWeight > vertex.getIncomingEdgeWeight())
>> {
>> minIncomingEdgeWeight = vertex.getIncomingEdgeWeight();
>> if (minIncomingEdgeWeight == 0)
>> {
>> // we won't get any lower
>> break;
>> }
>> }
>> }
>>
>> // process vertices having minimum incoming edge weight
>> int processCount = 0;
>> for (int i = 0; i < vertices.length; i++)
>> {
>> Vertex vertex = vertices[i];
>> if (!vertex.isProcessed()
>> && vertex.getIncomingEdgeWeight() == minIncomingEdgeWeight)
>> {
>> newOrder[newOrderIndex++] =
>> vertex.getEnvelope().getIdentity();
>> vertex.markProcessed();
>> processCount++;
>> }
>> vertex.resetIncomingEdgeWeight();
>> }
>>
>> if (log.isDebugEnabled())
>> {
>> log.debug(
>> "Processed "
>> + processCount
>> + " of "
>> + remainingVertices
>> + " remaining vertices in iteration #"
>> + iterationCount);
>> }
>> remainingVertices -= processCount;
>> }
>>
>> if (log.isDebugEnabled())
>> {
>> t3 = System.currentTimeMillis();
>> log.debug(
>> "Processing object envelope graph took " + (t3 - t2) + " ms");
>> }
>>
>> }
>>
>> /**
>> * Gets the reordered sequence of object envelopes
>> * @return an array of Identity objects representing the opimized sequence
>> * of database operations
>> */
>> public Identity[] getOrdering()
>> {
>> if (newOrder == null)
>> {
>> reorder();
>> }
>> return newOrder;
>> }
>>
>> /**
>> * Adds all edges for a given object envelope vertex. All edges are
>> * added to the edgeMap map.
>> * @param vertex the Vertex object to find edges for
>> */
>> private void addEdgesForVertex(Vertex vertex)
>> {
>> PersistenceBroker broker = transaction.getBroker();
>> Object object = vertex.getEnvelope().getObject();
>> ClassDescriptor cld = broker.getClassDescriptor(object.getClass());
>> Iterator rdsIter = cld.getObjectReferenceDescriptors().iterator();
>> while (rdsIter.hasNext())
>> {
>> ObjectReferenceDescriptor rds =
>> (ObjectReferenceDescriptor) rdsIter.next();
>> addObjectReferenceEdges(vertex, rds);
>> }
>> Iterator cdsIter = cld.getCollectionDescriptors().iterator();
>> while (cdsIter.hasNext())
>> {
>> CollectionDescriptor cds = (CollectionDescriptor) cdsIter.next();
>> addCollectionEdges(vertex, cds);
>> }
>> }
>>
>> /**
>> * Finds edges based to a specific object reference descriptor and
>> * adds them to the edge map.
>> * @param vertex the object envelope vertex holding the object reference
>> * @param rds the object reference descriptor
>> */
>> private void addObjectReferenceEdges(
>> Vertex vertex,
>> ObjectReferenceDescriptor rds)
>> {
>> Object refObject =
>> rds.getPersistentField().get(vertex.getEnvelope().getObject());
>> Class refClass = rds.getItemClass();
>> for (int i = 0; i < vertices.length; i++)
>> {
>> Edge edge = null;
>> ObjectEnvelope envelope = vertex.getEnvelope();
>> Vertex refVertex = vertices[i];
>> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
>> if (refObject == refEnvelope.getObject())
>> {
>> edge = buildConcrete11Edge(vertex, refVertex);
>> }
>> else if (refClass.isInstance(refVertex.getEnvelope().getObject()))
>> {
>> edge = buildPotential11Edge(vertex, refVertex);
>> }
>> if (edge != null)
>> {
>> Edge existingEdge = (Edge) edgeMap.get(edge);
>> if (existingEdge == null)
>> {
>> edgeMap.put(edge, edge);
>> }
>> else
>> {
>> existingEdge.increaseWeightTo(edge.getWeight());
>> }
>> }
>> }
>> }
>>
>> /**
>> * Finds edges base on a specific collection descriptor (1:n and m:n)
>> * and adds them to the edge map.
>> * @param vertex the object envelope vertex holding the collection
>> * @param cds the collection descriptor
>> */
>> private void addCollectionEdges(Vertex vertex, CollectionDescriptor cds)
>> {
>> ObjectEnvelope envelope = vertex.getEnvelope();
>> Object col = cds.getPersistentField().get(envelope.getObject());
>> Object[] refObjects;
>> if (col == null
>> || (ProxyHelper.isCollectionProxy(col)
>> && !ProxyHelper.getCollectionProxy(col).isLoaded()))
>> {
>> refObjects = new Object[0];
>> }
>> else
>> {
>> if (col instanceof Collection)
>> {
>> refObjects = ((Collection) col).toArray();
>>
>> }
>> else if (col instanceof Object[])
>> {
>> refObjects = (Object[]) col;
>> }
>> else
>> {
>> throw new OJBRuntimeException(
>> "Given object collection of type "
>> + col.getClass()
>> + " can not be managed by OJB. Use Array, Collection or
>>ManageableCollection instead!");
>> }
>> }
>> Class refClass = cds.getItemClass();
>>
>> for (int i = 0; i < vertices.length; i++)
>> {
>> Edge edge = null;
>> Vertex refVertex = vertices[i];
>> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
>>
>> if (refClass.isInstance(refEnvelope.getObject()))
>> {
>> if (containsObject(refEnvelope.getObject(), refObjects))
>> {
>> if (cds.isMtoNRelation())
>> {
>> edge = buildConcreteMNEdge(vertex, refVertex);
>> }
>> else
>> {
>> edge = buildConcrete1NEdge(vertex, refVertex);
>> }
>> }
>> else
>> {
>> if (cds.isMtoNRelation())
>> {
>> edge = buildPotentialMNEdge(vertex, refVertex);
>> }
>> else
>> {
>> edge = buildPotential1NEdge(vertex, refVertex);
>> }
>> }
>> }
>> if (edge != null)
>> {
>> Edge existingEdge = (Edge) edgeMap.get(edge);
>> if (existingEdge == null)
>> {
>> edgeMap.put(edge, edge);
>> }
>> else
>> {
>> existingEdge.increaseWeightTo(edge.getWeight());
>> }
>> }
>> }
>> }
>>
>> /**
>> * Helper method that searches an object array for the occurence of a
>> * specific object based on reference equality
>> * @param searchFor the object to search for
>> * @param searchIn the array to search in
>> * @return true if the object is found, otherwise false
>> */
>> private static boolean containsObject(Object searchFor, Object[] searchIn)
>> {
>> for (int i = 0; i < searchIn.length; i++)
>> {
>> if (searchFor == searchIn[i])
>> {
>> return true;
>> }
>> }
>> return false;
>> }
>>
>> /**
>> * Checks if the database operations associated with two object envelopes
>> * that are related via an 1:1 (or n:1) reference needs to be performed
>> * in a particular order and if so builds and returns a corresponding
>> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
>> * The following cases are considered (* means object needs update, + means
>> * object needs insert, - means object needs to be deleted):
>> * <table>
>> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
>> * <tr><td>(1)* -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
>> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
>> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
>> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
>> * <table>
>> * @param vertex1 object envelope vertex of the object holding the reference
>> * @param vertex2 object envelope vertex of the referenced object
>> * @return an Edge object or null if the two database operations can
>> * be performed in any order
>> */
>> protected Edge buildConcrete11Edge(Vertex vertex1, Vertex vertex2)
>> {
>> ModificationState state1 = vertex1.getEnvelope().getModificationState();
>> ModificationState state2 = vertex2.getEnvelope().getModificationState();
>> if (state1.needsUpdate() || state1.needsInsert())
>> {
>> if (state2.needsInsert())
>> {
>> // (2) must be inserted before (1) can point to it
>> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
>> }
>> }
>> else if (state1.needsDelete())
>> {
>> if (state2.needsDelete())
>> {
>> // (1) points to (2) and must be deleted first
>> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
>> }
>> }
>> return null;
>> }
>>
>> /**
>> * Checks if the database operations associated with two object envelopes
>> * that might have been related via an 1:1 (or n:1) reference before
>> * the current transaction needs to be performed
>> * in a particular order and if so builds and returns a corresponding
>> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
>> * The following cases are considered (* means object needs update, + means
>> * object needs insert, - means object needs to be deleted):
>> * <table>
>> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(1:1)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
>> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
>> * <table>
>> * @param vertex1 object envelope vertex of the object that might have
>> * hold the reference
>> * @param vertex2 object envelope vertex of the potentially referenced
>> * object
>> * @return an Edge object or null if the two database operations can
>> * be performed in any order
>> */
>> protected Edge buildPotential11Edge(Vertex vertex1, Vertex vertex2)
>> {
>> ModificationState state1 = vertex1.getEnvelope().getModificationState();
>> ModificationState state2 = vertex2.getEnvelope().getModificationState();
>> if (state1.needsUpdate() || state1.needsDelete())
>> {
>> if (state2.needsDelete())
>> {
>> // old version of (1) might point to (2)
>> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
>> }
>> }
>> return null;
>> }
>>
>> /**
>> * Checks if the database operations associated with two object envelopes
>> * that are related via an 1:n collection reference needs to be performed
>> * in a particular order and if so builds and returns a corresponding
>> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
>> * The following cases are considered (* means object needs update, + means
>> * object needs insert, - means object needs to be deleted):
>> * <table>
>> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>(1)->(2) edge</td></tr>
>> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>(1)->(2) edge</td></tr>
>> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
>> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
>> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
>> * <table>
>> * @param vertex1 object envelope vertex of the object holding the
>> * collection
>> * @param vertex2 object envelope vertex of the object contained in the
>> * collection
>> * @return an Edge object or null if the two database operations can
>> * be performed in any order
>> */
>> protected Edge buildConcrete1NEdge(Vertex vertex1, Vertex vertex2)
>> {
>> ModificationState state1 = vertex1.getEnvelope().getModificationState();
>> ModificationState state2 = vertex2.getEnvelope().getModificationState();
>> if (state1.needsInsert())
>> {
>> if (state2.needsUpdate() || state2.needsInsert())
>> {
>> // (2) now contains an FK to (1) thus (1) must be inserted first
>> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
>> }
>> }
>> else if (state1.needsDelete())
>> {
>> if (state2.needsUpdate() || state2.needsDelete())
>> {
>> // Before deleting (1) give (2) a chance to drop its FK to it
>> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
>> }
>> }
>> return null;
>> }
>>
>> /**
>> * Checks if the database operations associated with two object envelopes
>> * that are might have been related via an 1:n collection reference before
>> * the current transaction needs to be performed
>> * in a particular order and if so builds and returns a corresponding
>> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
>> * The following cases are considered (* means object needs update, + means
>> * object needs insert, - means object needs to be deleted):
>> * <table>
>> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
>> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
>> * <table>
>> * @param vertex1 object envelope vertex of the object holding the
>> * collection
>> * @param vertex2 object envelope vertex of the object that might have
>> * been contained in the collection
>> * @return an Edge object or null if the two database operations can
>> * be performed in any order
>> */
>> protected Edge buildPotential1NEdge(Vertex vertex1, Vertex vertex2)
>> {
>> ModificationState state1 = vertex1.getEnvelope().getModificationState();
>> ModificationState state2 = vertex2.getEnvelope().getModificationState();
>> if (state1.needsDelete())
>> {
>> if (state2.needsUpdate() || state2.needsDelete())
>> {
>> // Before deleting (1) give potential previous collection
>> // members a chance to drop their FKs to it
>> return new Edge(vertex2, vertex1, POTENTIAL_EDGE_WEIGHT);
>> }
>> }
>> return null;
>> }
>>
>> /**
>> * Checks if the database operations associated with two object envelopes
>> * that are related via an m:n collection reference needs to be performed
>> * in a particular order and if so builds and returns a corresponding
>> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
>> * The following cases are considered (* means object needs update, + means
>> * object needs insert, - means object needs to be deleted):
>> * <table>
>> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
>> * <tr><td>(1)* -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
>> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
>> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
>> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
>> * <table>
>> * @param vertex1 object envelope vertex of the object holding the
>> * collection
>> * @param vertex2 object envelope vertex of the object contained in the
>> * collection
>> * @return an Edge object or null if the two database operations can
>> * be performed in any order
>> */
>> protected Edge buildConcreteMNEdge(Vertex vertex1, Vertex vertex2)
>> {
>> ModificationState state1 = vertex1.getEnvelope().getModificationState();
>> ModificationState state2 = vertex2.getEnvelope().getModificationState();
>> if (state1.needsUpdate() || state1.needsInsert())
>> {
>> if (state2.needsInsert())
>> {
>> // (2) must be inserted before we can create a link to it
>> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
>> }
>> }
>> else if (state1.needsDelete())
>> {
>> if (state2.needsDelete())
>> {
>> // there is a link from (1) to (2) which must be deleted first,
>> // which will happen when deleting (1) - thus:
>> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
>> }
>> }
>> return null;
>> }
>>
>> /**
>> * Checks if the database operations associated with two object envelopes
>> * that might have been related via an m:n collection reference before
>> * the current transaction needs to be performed
>> * in a particular order and if so builds and returns a corresponding
>> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
>> * The following cases are considered (* means object needs update, + means
>> * object needs insert, - means object needs to be deleted):
>> * <table>
>> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(m:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)* -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
>> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
>> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
>> * <table>
>> * @param vertex1 object envelope vertex of the object holding the
>> * collection
>> * @param vertex2 object envelope vertex of the object that might have
>> * been contained in the collection
>> * @return an Edge object or null if the two database operations can
>> * be performed in any order
>> */
>> protected Edge buildPotentialMNEdge(Vertex vertex1, Vertex vertex2)
>> {
>> ModificationState state1 = vertex1.getEnvelope().getModificationState();
>> ModificationState state2 = vertex2.getEnvelope().getModificationState();
>> if (state1.needsUpdate() || state1.needsDelete())
>> {
>> if (state2.needsDelete())
>> {
>> // old version of (1) might comprise a link to (2)
>> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
>> }
>> }
>> return null;
>> }
>>
>> /**
>> * Represents an edge in the object envelope graph
>> */
>> private static class Edge
>> {
>> private Vertex initial;
>> private Vertex terminal;
>> private Identity initialIdentity;
>> private Identity terminalIdentity;
>> private int weight;
>> private boolean knownToBeProcessed;
>> private int hashCode;
>>
>> public Edge(Vertex initial, Vertex terminal, int weight)
>> {
>> this.initial = initial;
>> this.terminal = terminal;
>> this.initialIdentity = initial.getEnvelope().getIdentity();
>> this.terminalIdentity = terminal.getEnvelope().getIdentity();
>> this.weight = weight;
>> this.knownToBeProcessed = false;
>> this.hashCode =
>> initialIdentity.hashCode() + 13 * terminalIdentity.hashCode();
>> }
>> public Vertex getInitialVertex()
>> {
>> return initial;
>> }
>> public Vertex getTerminalVertex()
>> {
>> return terminal;
>> }
>> public boolean connects(Vertex vertex)
>> {
>> return initial == vertex || terminal == vertex;
>> }
>> public void increaseWeightTo(int minWeight)
>> {
>> if (weight < minWeight)
>> {
>> weight = minWeight;
>> }
>> }
>> public int getWeight()
>> {
>> return weight;
>> }
>> public boolean isProcessed()
>> {
>> if (knownToBeProcessed)
>> {
>> return true;
>> }
>> else
>> {
>> boolean processed =
>> initial.isProcessed() || terminal.isProcessed();
>> if (processed)
>> {
>> knownToBeProcessed = true;
>> }
>> return processed;
>> }
>> }
>> public boolean equals(Object obj)
>> {
>> if (obj instanceof Edge)
>> {
>> Edge other = (Edge) obj;
>> return this.initialIdentity.equals(other.initialIdentity)
>> && this.terminalIdentity.equals(other.terminalIdentity);
>> }
>> else
>> {
>> return false;
>> }
>> }
>> public int hashCode()
>> {
>> return hashCode;
>> }
>> }
>>
>> /**
>> * Represents a vertex in the object envelope graph
>> */
>> private static class Vertex
>> {
>> private ObjectEnvelope envelope;
>> private boolean processed;
>> private int incomingEdgeWeight;
>>
>> public Vertex(ObjectEnvelope envelope)
>> {
>> this.envelope = envelope;
>> this.incomingEdgeWeight = 0;
>> this.processed = false;
>> }
>> public ObjectEnvelope getEnvelope()
>> {
>> return envelope;
>> }
>> public void markProcessed()
>> {
>> processed = true;
>> }
>> public boolean isProcessed()
>> {
>> return processed;
>> }
>> public void resetIncomingEdgeWeight()
>> {
>> incomingEdgeWeight = 0;
>> }
>> public void incrementIncomingEdgeWeight(int weight)
>> {
>> incomingEdgeWeight += weight;
>> }
>> public int getIncomingEdgeWeight()
>> {
>> return incomingEdgeWeight;
>> }
>> }
>>
>>}
>>
>>---------------------------------------------------------------------
>>To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
>>For additional commands, e-mail: ojb-dev-help@db.apache.org
>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-dev-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-dev-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Gerhard Grosse <ge...@lex-com.net>.
On Thu, 18 Nov 2004 16:18:04 -0800, Brian McCallister <bm...@gmail.com>
wrote:
>Fantastic!
>
>I haven't looked closely at the code yet, but is it dependent (for
>operation, not compile ;-) on ODMG classes? I need the exact same
>topological sort for the object space transaction stuff (against PB)
>in 1.1 =)
>
>Thank you!
>
>-Brian
>
Hi Brian,
The class makes use of ObjectEnvelopes and ModificationStates. Methods invoked
on ObjectEnvelope are getObject, getIdentity and needsUpdate/Insert/Delete,
nothing else. I believe this should be easy to generalize.
Cheers,
Gerhard
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-dev-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Brian McCallister <bm...@gmail.com>.
Fantastic!
I haven't looked closely at the code yet, but is it dependent (for
operation, not compile ;-) on ODMG classes? I need the exact same
topological sort for the object space transaction stuff (against PB)
in 1.1 =)
Thank you!
-Brian
On Thu, 18 Nov 2004 14:06:48 +0100, Gerhard Grosse
<ge...@lex-com.net> wrote:
> Hi,
>
> for quite some time we were experiencing problems with FK constraint violations
> when committing ODMG transactions. We resolved these problems by inserting
> TransactionExt.flush() calls wherever necessary. However, this in turn produced
> deadlock problems under high server load. Therefore we decided to try and
> improve the ordering of the SQL sent to the database. These efforts resulted in
> a class org.ojb.odmg.ObjectEnvelopeOrdering which we hereby contribute to the
> OJB community, because other users seem to have similar problems.
>
> To use this class, the private method reorder() in class
> org.ojb.odmg.ObjectEnvelopeTable must be replaced with:
>
> private void reorder()
> {
> if (needsCommit)
> {
> ObjectEnvelopeOrdering ordering =
> new ObjectEnvelopeOrdering(transaction,mvOrderOfIds,mhtObjectEnvelopes);
> ordering.reorder();
> Identity[] newOrder = ordering.getOrdering();
> mvOrderOfIds.clear();
> for (int i = 0; i < newOrder.length; i++)
> {
> mvOrderOfIds.add(newOrder[i]);
> }
> }
> }
>
> The ObjectEnvelopeOrdering class addresses the following problems we observed
> with the original ordering algorithm:
>
> (1) the ordering is based on the modified state of the objects only; therefore
> if a reference in object A is set to null, OJB does not see that before
> modification A referenced an object B to be deleted.
>
> (2) 1:n and m:n collections are treated in the same way, although the
> FK-location in the DB is quite different.
>
> (3) the ordering algorithm is 'greedy' in the sense that once an object
> modification has been put into the ordered list, it will stay at this position
> even if later constraints are found that would require to move it to a position
> further down.
>
> (4) issue (3) is aggravated by the fact that the ordering does not take into
> account the modification state of a referenced object. Therefore objects are
> inserted into the ordered list even if there is no real need for ordering. Later
> a real constraint me be encountered, but now the object is already frozen at its
> new position.
>
> The ObjectEnvelopeOrdering class uses a graph-theoretical approach to order the
> object envelopes (see the JavaDoc for details). Edges in this graph are inserted
> only if there really is a need for ordering two object envelopes with respect to
> each other - determining this need is based on the modification state of both
> objects and the type of relation the two have to each other (1:1, 1:n, or m:n).
> This addresses issues (2)-(4).
>
> Issue (1) is not addressed as as niftily: Since we did not want to change the
> ObjectEnvelope class, we opted for a heuristic solution, where 'potential'
> relations between two objects are taken into account based on the class type of
> a reference.
>
> Test results:
> After using the ObjectEnvelopeOrdering class we were able to remove all flush
> statements from our application without any test case failing. The results of
> the JUnit tests of OJB did not change either (some fail before and after the
> change), with one exception:
> org.apache.ojb.broker.sequence.NativeIdentifierTest.testReferenceInsertUpdateODMG.
> Before our change, this test failed with a failed assertion, after our change it
> now causes an FK violation error. Looking at the test code, I cannot see how the
> FK error could be avoided, because there are two tables with FKs referencing
> each other and the test attempts to insert two objects with references to each
> other in a single transaction. As far as I can see, there is no order of INSERT
> statements that could avoid the FK error.
>
> Performance:
> The ordering process implemented by the ObjectEnvelopeOrdering class is
> certainly slower than the original recursive ordering. This is mainly due to
> the need of addressing issue (1). In our real application scenario, however, we
> do not notice any perfomance degradation.
>
> AFAIK the OJB mailing list does not accept attachements, therefore I am posting
> the class code inline. If anyone knows a better way to submit the code without
> distortion due to line breaks, please let me know.
>
> We would be happy if the class would make it into the 'official' OJB. In any
> case feel free to use it if it suits you. Of course the usual disclaimer apply
> (no warranty of any kind...)
>
> Gerhard
>
> -------------------------------
>
> package org.apache.ojb.odmg;
>
> import java.util.ArrayList;
> import java.util.Collection;
> import java.util.HashMap;
> import java.util.Iterator;
> import java.util.List;
> import java.util.Map;
>
> import org.apache.ojb.broker.Identity;
> import org.apache.ojb.broker.OJBRuntimeException;
> import org.apache.ojb.broker.PersistenceBroker;
> import org.apache.ojb.broker.core.proxy.ProxyHelper;
> import org.apache.ojb.broker.metadata.ClassDescriptor;
> import org.apache.ojb.broker.metadata.CollectionDescriptor;
> import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
> import org.apache.ojb.broker.util.logging.Logger;
> import org.apache.ojb.broker.util.logging.LoggerFactory;
> import org.apache.ojb.odmg.states.ModificationState;
>
> /**
> * <p>Implements an algorithm for reordering the object envelopes of a pending
> * transaction to minimized the probability of foreign key constraint
> * violations.</p>
> *
> * <p>The algorithm is based on a graph theoretical approach: Each object
> * envelope is represented by a vertex in a graph. Each possible constraint
> * on the order of database operations is represented by a directed edge
> * in this graph, in which the initial vertex represents the object envelope
> * to be sent to the database first and the terminal index represents the
> * object envelope that might cause a FK violation if the initial vertex
> * has not been sent to the database before.</p>
> *
> * <p>Additionally the edges in this graph are weighted. This is necessary
> * because the object envelopes provide only information on the relation
> * between objects <strong>after</strong> the transaction. FK violations,
> * however, can also occur due to relations that existed <strong>before</strong>
> * the transaction. Therefore the algorithm also considers potential relations
> * between objects due to the fact that an object is of a class that is
> * the item class of a object or collection reference of another object.
> * Graph edges representing such potential relationships receive a lower
> * weight than edges representing concrete relationships that exist in the
> * current state of the object model.</p>
> *
> * <p>Once all graph edges have been established, the algorithm proceeds as
> * follows:</p>
> * <ol>
> * <li>Iterate through all vertices and sum up the weight of all incoming
> * edges (i.e. those edges whose terminal vertex is the current
> vertex).</li>
> * <li>Find the minimum value of this weight sums (ideally this minimum is
> zero,
> * meaning that there are object envelopes that can be sent to the
> * database without risking FK violations)<il>
> * <li>Add all vertices with a weight sum that is equal to this minimum to the
> * reordered sequence of object envelopes and remove the vertices
> * and all connected edges from the graph.</li>
> * <li>If there are vertices left, repeat steps (1) through (3), otherwise
> * we are done.
> * </ol>
> *
> * @author Gerhard Grosse
> * @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2004/11/18 12:25:28 grosse
> Exp $
> * @since Nov 15, 2004
> */
> public class ObjectEnvelopeOrdering
> {
> private static final int CONCRETE_EDGE_WEIGHT = 2;
> private static final int POTENTIAL_EDGE_WEIGHT = 1;
>
> private static Logger log =
> LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
>
> private List originalOrder;
> private Map envelopes;
> private TransactionImpl transaction;
>
> private Vertex[] vertices;
> private Map edgeMap;
>
> private int newOrderIndex;
> private Identity[] newOrder;
>
> /**
> * Creates an object envelope ordering based on an original ordering
> * of Identity objects and an Identity->ObjectEnvelope map
> * @param originalOrder a list of Identity objects
> * @param envelopes a map with ObjectEnvelope-s with their respective
> * Identity-s as key
> */
> public ObjectEnvelopeOrdering(
> TransactionImpl transaction,
> List originalOrder,
> Map envelopes)
> {
> this.originalOrder = originalOrder;
> this.envelopes = envelopes;
> this.transaction = transaction;
> }
>
> /**
> * Reorders the object envelopes. The new order is available from the
> * <code>ordering</code> property.
> * @see #getOrdering()
> */
> public void reorder()
> {
> long t1 = 0, t2 = 0, t3 = 0;
> if (log.isDebugEnabled())
> {
> t1 = System.currentTimeMillis();
> }
> newOrder = new Identity[originalOrder.size()];
> newOrderIndex = 0;
>
> // set up the vertex array in the order the envelopes were added
> List vertexList = new ArrayList(originalOrder.size());
> int vertexIndex = 0;
> for (Iterator it = originalOrder.iterator(); it.hasNext();)
> {
> ObjectEnvelope envelope = (ObjectEnvelope) envelopes.get(it.next());
> if (envelope.needsUpdate()
> || envelope.needsInsert()
> || envelope.needsDelete())
> {
> Vertex vertex = new Vertex(envelope);
> vertexList.add(vertex);
> }
> else
> {
> // envelope is clean - just add identity to new order
> newOrder[newOrderIndex++] = envelope.getIdentity();
> }
> }
> vertices = (Vertex[]) vertexList.toArray(new Vertex[vertexList.size()]);
>
> // set up the edges
> edgeMap = new HashMap(2 * vertices.length, 0.75f);
> for (int i = 0; i < vertices.length; i++)
> {
> addEdgesForVertex(vertices[i]);
> }
>
> if (log.isDebugEnabled())
> {
> t2 = System.currentTimeMillis();
> log.debug(
> "Building object envelope graph took " + (t2 - t1) + " ms");
> log.debug(
> "Object envelope graph contains "
> + vertices.length
> + " vertices"
> + " and "
> + edgeMap.size()
> + " edges");
> }
>
> int remainingVertices = vertices.length;
> int iterationCount = 0;
> while (remainingVertices > 0)
> {
> // update iteration count
> iterationCount++;
>
> // update incoming edge counts
> for (Iterator it = edgeMap.values().iterator(); it.hasNext();)
> {
> Edge edge = (Edge) it.next();
> if (!edge.isProcessed())
> {
> edge.getTerminalVertex().incrementIncomingEdgeWeight(
> edge.getWeight());
> }
> }
>
> // find minimum weight of incoming edges of a vertex
> int minIncomingEdgeWeight = Integer.MAX_VALUE;
> for (int i = 0; i < vertices.length; i++)
> {
> Vertex vertex = vertices[i];
> if (!vertex.isProcessed()
> && minIncomingEdgeWeight > vertex.getIncomingEdgeWeight())
> {
> minIncomingEdgeWeight = vertex.getIncomingEdgeWeight();
> if (minIncomingEdgeWeight == 0)
> {
> // we won't get any lower
> break;
> }
> }
> }
>
> // process vertices having minimum incoming edge weight
> int processCount = 0;
> for (int i = 0; i < vertices.length; i++)
> {
> Vertex vertex = vertices[i];
> if (!vertex.isProcessed()
> && vertex.getIncomingEdgeWeight() == minIncomingEdgeWeight)
> {
> newOrder[newOrderIndex++] =
> vertex.getEnvelope().getIdentity();
> vertex.markProcessed();
> processCount++;
> }
> vertex.resetIncomingEdgeWeight();
> }
>
> if (log.isDebugEnabled())
> {
> log.debug(
> "Processed "
> + processCount
> + " of "
> + remainingVertices
> + " remaining vertices in iteration #"
> + iterationCount);
> }
> remainingVertices -= processCount;
> }
>
> if (log.isDebugEnabled())
> {
> t3 = System.currentTimeMillis();
> log.debug(
> "Processing object envelope graph took " + (t3 - t2) + " ms");
> }
>
> }
>
> /**
> * Gets the reordered sequence of object envelopes
> * @return an array of Identity objects representing the opimized sequence
> * of database operations
> */
> public Identity[] getOrdering()
> {
> if (newOrder == null)
> {
> reorder();
> }
> return newOrder;
> }
>
> /**
> * Adds all edges for a given object envelope vertex. All edges are
> * added to the edgeMap map.
> * @param vertex the Vertex object to find edges for
> */
> private void addEdgesForVertex(Vertex vertex)
> {
> PersistenceBroker broker = transaction.getBroker();
> Object object = vertex.getEnvelope().getObject();
> ClassDescriptor cld = broker.getClassDescriptor(object.getClass());
> Iterator rdsIter = cld.getObjectReferenceDescriptors().iterator();
> while (rdsIter.hasNext())
> {
> ObjectReferenceDescriptor rds =
> (ObjectReferenceDescriptor) rdsIter.next();
> addObjectReferenceEdges(vertex, rds);
> }
> Iterator cdsIter = cld.getCollectionDescriptors().iterator();
> while (cdsIter.hasNext())
> {
> CollectionDescriptor cds = (CollectionDescriptor) cdsIter.next();
> addCollectionEdges(vertex, cds);
> }
> }
>
> /**
> * Finds edges based to a specific object reference descriptor and
> * adds them to the edge map.
> * @param vertex the object envelope vertex holding the object reference
> * @param rds the object reference descriptor
> */
> private void addObjectReferenceEdges(
> Vertex vertex,
> ObjectReferenceDescriptor rds)
> {
> Object refObject =
> rds.getPersistentField().get(vertex.getEnvelope().getObject());
> Class refClass = rds.getItemClass();
> for (int i = 0; i < vertices.length; i++)
> {
> Edge edge = null;
> ObjectEnvelope envelope = vertex.getEnvelope();
> Vertex refVertex = vertices[i];
> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
> if (refObject == refEnvelope.getObject())
> {
> edge = buildConcrete11Edge(vertex, refVertex);
> }
> else if (refClass.isInstance(refVertex.getEnvelope().getObject()))
> {
> edge = buildPotential11Edge(vertex, refVertex);
> }
> if (edge != null)
> {
> Edge existingEdge = (Edge) edgeMap.get(edge);
> if (existingEdge == null)
> {
> edgeMap.put(edge, edge);
> }
> else
> {
> existingEdge.increaseWeightTo(edge.getWeight());
> }
> }
> }
> }
>
> /**
> * Finds edges base on a specific collection descriptor (1:n and m:n)
> * and adds them to the edge map.
> * @param vertex the object envelope vertex holding the collection
> * @param cds the collection descriptor
> */
> private void addCollectionEdges(Vertex vertex, CollectionDescriptor cds)
> {
> ObjectEnvelope envelope = vertex.getEnvelope();
> Object col = cds.getPersistentField().get(envelope.getObject());
> Object[] refObjects;
> if (col == null
> || (ProxyHelper.isCollectionProxy(col)
> && !ProxyHelper.getCollectionProxy(col).isLoaded()))
> {
> refObjects = new Object[0];
> }
> else
> {
> if (col instanceof Collection)
> {
> refObjects = ((Collection) col).toArray();
>
> }
> else if (col instanceof Object[])
> {
> refObjects = (Object[]) col;
> }
> else
> {
> throw new OJBRuntimeException(
> "Given object collection of type "
> + col.getClass()
> + " can not be managed by OJB. Use Array, Collection or
> ManageableCollection instead!");
> }
> }
> Class refClass = cds.getItemClass();
>
> for (int i = 0; i < vertices.length; i++)
> {
> Edge edge = null;
> Vertex refVertex = vertices[i];
> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
>
> if (refClass.isInstance(refEnvelope.getObject()))
> {
> if (containsObject(refEnvelope.getObject(), refObjects))
> {
> if (cds.isMtoNRelation())
> {
> edge = buildConcreteMNEdge(vertex, refVertex);
> }
> else
> {
> edge = buildConcrete1NEdge(vertex, refVertex);
> }
> }
> else
> {
> if (cds.isMtoNRelation())
> {
> edge = buildPotentialMNEdge(vertex, refVertex);
> }
> else
> {
> edge = buildPotential1NEdge(vertex, refVertex);
> }
> }
> }
> if (edge != null)
> {
> Edge existingEdge = (Edge) edgeMap.get(edge);
> if (existingEdge == null)
> {
> edgeMap.put(edge, edge);
> }
> else
> {
> existingEdge.increaseWeightTo(edge.getWeight());
> }
> }
> }
> }
>
> /**
> * Helper method that searches an object array for the occurence of a
> * specific object based on reference equality
> * @param searchFor the object to search for
> * @param searchIn the array to search in
> * @return true if the object is found, otherwise false
> */
> private static boolean containsObject(Object searchFor, Object[] searchIn)
> {
> for (int i = 0; i < searchIn.length; i++)
> {
> if (searchFor == searchIn[i])
> {
> return true;
> }
> }
> return false;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are related via an 1:1 (or n:1) reference needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the reference
> * @param vertex2 object envelope vertex of the referenced object
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildConcrete11Edge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsInsert())
> {
> if (state2.needsInsert())
> {
> // (2) must be inserted before (1) can point to it
> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> }
> }
> else if (state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // (1) points to (2) and must be deleted first
> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that might have been related via an 1:1 (or n:1) reference before
> * the current transaction needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object that might have
> * hold the reference
> * @param vertex2 object envelope vertex of the potentially referenced
> * object
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildPotential11Edge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // old version of (1) might point to (2)
> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are related via an 1:n collection reference needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object contained in the
> * collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildConcrete1NEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsInsert())
> {
> if (state2.needsUpdate() || state2.needsInsert())
> {
> // (2) now contains an FK to (1) thus (1) must be inserted first
> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
> }
> }
> else if (state1.needsDelete())
> {
> if (state2.needsUpdate() || state2.needsDelete())
> {
> // Before deleting (1) give (2) a chance to drop its FK to it
> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are might have been related via an 1:n collection reference before
> * the current transaction needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object that might have
> * been contained in the collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildPotential1NEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsDelete())
> {
> if (state2.needsUpdate() || state2.needsDelete())
> {
> // Before deleting (1) give potential previous collection
> // members a chance to drop their FKs to it
> return new Edge(vertex2, vertex1, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are related via an m:n collection reference needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object contained in the
> * collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildConcreteMNEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsInsert())
> {
> if (state2.needsInsert())
> {
> // (2) must be inserted before we can create a link to it
> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> }
> }
> else if (state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // there is a link from (1) to (2) which must be deleted first,
> // which will happen when deleting (1) - thus:
> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that might have been related via an m:n collection reference before
> * the current transaction needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object that might have
> * been contained in the collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildPotentialMNEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // old version of (1) might comprise a link to (2)
> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Represents an edge in the object envelope graph
> */
> private static class Edge
> {
> private Vertex initial;
> private Vertex terminal;
> private Identity initialIdentity;
> private Identity terminalIdentity;
> private int weight;
> private boolean knownToBeProcessed;
> private int hashCode;
>
> public Edge(Vertex initial, Vertex terminal, int weight)
> {
> this.initial = initial;
> this.terminal = terminal;
> this.initialIdentity = initial.getEnvelope().getIdentity();
> this.terminalIdentity = terminal.getEnvelope().getIdentity();
> this.weight = weight;
> this.knownToBeProcessed = false;
> this.hashCode =
> initialIdentity.hashCode() + 13 * terminalIdentity.hashCode();
> }
> public Vertex getInitialVertex()
> {
> return initial;
> }
> public Vertex getTerminalVertex()
> {
> return terminal;
> }
> public boolean connects(Vertex vertex)
> {
> return initial == vertex || terminal == vertex;
> }
> public void increaseWeightTo(int minWeight)
> {
> if (weight < minWeight)
> {
> weight = minWeight;
> }
> }
> public int getWeight()
> {
> return weight;
> }
> public boolean isProcessed()
> {
> if (knownToBeProcessed)
> {
> return true;
> }
> else
> {
> boolean processed =
> initial.isProcessed() || terminal.isProcessed();
> if (processed)
> {
> knownToBeProcessed = true;
> }
> return processed;
> }
> }
> public boolean equals(Object obj)
> {
> if (obj instanceof Edge)
> {
> Edge other = (Edge) obj;
> return this.initialIdentity.equals(other.initialIdentity)
> && this.terminalIdentity.equals(other.terminalIdentity);
> }
> else
> {
> return false;
> }
> }
> public int hashCode()
> {
> return hashCode;
> }
> }
>
> /**
> * Represents a vertex in the object envelope graph
> */
> private static class Vertex
> {
> private ObjectEnvelope envelope;
> private boolean processed;
> private int incomingEdgeWeight;
>
> public Vertex(ObjectEnvelope envelope)
> {
> this.envelope = envelope;
> this.incomingEdgeWeight = 0;
> this.processed = false;
> }
> public ObjectEnvelope getEnvelope()
> {
> return envelope;
> }
> public void markProcessed()
> {
> processed = true;
> }
> public boolean isProcessed()
> {
> return processed;
> }
> public void resetIncomingEdgeWeight()
> {
> incomingEdgeWeight = 0;
> }
> public void incrementIncomingEdgeWeight(int weight)
> {
> incomingEdgeWeight += weight;
> }
> public int getIncomingEdgeWeight()
> {
> return incomingEdgeWeight;
> }
> }
>
> }
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-dev-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-dev-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Jakob Braeuchi <jb...@gmx.ch>.
hi gerhard,
i commited your patch to 1.1 trunk.
jakob
Gerhard Grosse schrieb:
> Hi,
>
> for quite some time we were experiencing problems with FK constraint violations
> when committing ODMG transactions. We resolved these problems by inserting
> TransactionExt.flush() calls wherever necessary. However, this in turn produced
> deadlock problems under high server load. Therefore we decided to try and
> improve the ordering of the SQL sent to the database. These efforts resulted in
> a class org.ojb.odmg.ObjectEnvelopeOrdering which we hereby contribute to the
> OJB community, because other users seem to have similar problems.
>
> To use this class, the private method reorder() in class
> org.ojb.odmg.ObjectEnvelopeTable must be replaced with:
>
> private void reorder()
> {
> if (needsCommit)
> {
> ObjectEnvelopeOrdering ordering =
> new ObjectEnvelopeOrdering(transaction,mvOrderOfIds,mhtObjectEnvelopes);
> ordering.reorder();
> Identity[] newOrder = ordering.getOrdering();
> mvOrderOfIds.clear();
> for (int i = 0; i < newOrder.length; i++)
> {
> mvOrderOfIds.add(newOrder[i]);
> }
> }
> }
>
> The ObjectEnvelopeOrdering class addresses the following problems we observed
> with the original ordering algorithm:
>
> (1) the ordering is based on the modified state of the objects only; therefore
> if a reference in object A is set to null, OJB does not see that before
> modification A referenced an object B to be deleted.
>
> (2) 1:n and m:n collections are treated in the same way, although the
> FK-location in the DB is quite different.
>
> (3) the ordering algorithm is 'greedy' in the sense that once an object
> modification has been put into the ordered list, it will stay at this position
> even if later constraints are found that would require to move it to a position
> further down.
>
> (4) issue (3) is aggravated by the fact that the ordering does not take into
> account the modification state of a referenced object. Therefore objects are
> inserted into the ordered list even if there is no real need for ordering. Later
> a real constraint me be encountered, but now the object is already frozen at its
> new position.
>
> The ObjectEnvelopeOrdering class uses a graph-theoretical approach to order the
> object envelopes (see the JavaDoc for details). Edges in this graph are inserted
> only if there really is a need for ordering two object envelopes with respect to
> each other - determining this need is based on the modification state of both
> objects and the type of relation the two have to each other (1:1, 1:n, or m:n).
> This addresses issues (2)-(4).
>
> Issue (1) is not addressed as as niftily: Since we did not want to change the
> ObjectEnvelope class, we opted for a heuristic solution, where 'potential'
> relations between two objects are taken into account based on the class type of
> a reference.
>
> Test results:
> After using the ObjectEnvelopeOrdering class we were able to remove all flush
> statements from our application without any test case failing. The results of
> the JUnit tests of OJB did not change either (some fail before and after the
> change), with one exception:
> org.apache.ojb.broker.sequence.NativeIdentifierTest.testReferenceInsertUpdateODMG.
> Before our change, this test failed with a failed assertion, after our change it
> now causes an FK violation error. Looking at the test code, I cannot see how the
> FK error could be avoided, because there are two tables with FKs referencing
> each other and the test attempts to insert two objects with references to each
> other in a single transaction. As far as I can see, there is no order of INSERT
> statements that could avoid the FK error.
>
> Performance:
> The ordering process implemented by the ObjectEnvelopeOrdering class is
> certainly slower than the original recursive ordering. This is mainly due to
> the need of addressing issue (1). In our real application scenario, however, we
> do not notice any perfomance degradation.
>
> AFAIK the OJB mailing list does not accept attachements, therefore I am posting
> the class code inline. If anyone knows a better way to submit the code without
> distortion due to line breaks, please let me know.
>
> We would be happy if the class would make it into the 'official' OJB. In any
> case feel free to use it if it suits you. Of course the usual disclaimer apply
> (no warranty of any kind...)
>
> Gerhard
>
> -------------------------------
>
> package org.apache.ojb.odmg;
>
> import java.util.ArrayList;
> import java.util.Collection;
> import java.util.HashMap;
> import java.util.Iterator;
> import java.util.List;
> import java.util.Map;
>
> import org.apache.ojb.broker.Identity;
> import org.apache.ojb.broker.OJBRuntimeException;
> import org.apache.ojb.broker.PersistenceBroker;
> import org.apache.ojb.broker.core.proxy.ProxyHelper;
> import org.apache.ojb.broker.metadata.ClassDescriptor;
> import org.apache.ojb.broker.metadata.CollectionDescriptor;
> import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
> import org.apache.ojb.broker.util.logging.Logger;
> import org.apache.ojb.broker.util.logging.LoggerFactory;
> import org.apache.ojb.odmg.states.ModificationState;
>
> /**
> * <p>Implements an algorithm for reordering the object envelopes of a pending
> * transaction to minimized the probability of foreign key constraint
> * violations.</p>
> *
> * <p>The algorithm is based on a graph theoretical approach: Each object
> * envelope is represented by a vertex in a graph. Each possible constraint
> * on the order of database operations is represented by a directed edge
> * in this graph, in which the initial vertex represents the object envelope
> * to be sent to the database first and the terminal index represents the
> * object envelope that might cause a FK violation if the initial vertex
> * has not been sent to the database before.</p>
> *
> * <p>Additionally the edges in this graph are weighted. This is necessary
> * because the object envelopes provide only information on the relation
> * between objects <strong>after</strong> the transaction. FK violations,
> * however, can also occur due to relations that existed <strong>before</strong>
> * the transaction. Therefore the algorithm also considers potential relations
> * between objects due to the fact that an object is of a class that is
> * the item class of a object or collection reference of another object.
> * Graph edges representing such potential relationships receive a lower
> * weight than edges representing concrete relationships that exist in the
> * current state of the object model.</p>
> *
> * <p>Once all graph edges have been established, the algorithm proceeds as
> * follows:</p>
> * <ol>
> * <li>Iterate through all vertices and sum up the weight of all incoming
> * edges (i.e. those edges whose terminal vertex is the current
> vertex).</li>
> * <li>Find the minimum value of this weight sums (ideally this minimum is
> zero,
> * meaning that there are object envelopes that can be sent to the
> * database without risking FK violations)<il>
> * <li>Add all vertices with a weight sum that is equal to this minimum to the
> * reordered sequence of object envelopes and remove the vertices
> * and all connected edges from the graph.</li>
> * <li>If there are vertices left, repeat steps (1) through (3), otherwise
> * we are done.
> * </ol>
> *
> * @author Gerhard Grosse
> * @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2004/11/18 12:25:28 grosse
> Exp $
> * @since Nov 15, 2004
> */
> public class ObjectEnvelopeOrdering
> {
> private static final int CONCRETE_EDGE_WEIGHT = 2;
> private static final int POTENTIAL_EDGE_WEIGHT = 1;
>
> private static Logger log =
> LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
>
> private List originalOrder;
> private Map envelopes;
> private TransactionImpl transaction;
>
> private Vertex[] vertices;
> private Map edgeMap;
>
> private int newOrderIndex;
> private Identity[] newOrder;
>
> /**
> * Creates an object envelope ordering based on an original ordering
> * of Identity objects and an Identity->ObjectEnvelope map
> * @param originalOrder a list of Identity objects
> * @param envelopes a map with ObjectEnvelope-s with their respective
> * Identity-s as key
> */
> public ObjectEnvelopeOrdering(
> TransactionImpl transaction,
> List originalOrder,
> Map envelopes)
> {
> this.originalOrder = originalOrder;
> this.envelopes = envelopes;
> this.transaction = transaction;
> }
>
> /**
> * Reorders the object envelopes. The new order is available from the
> * <code>ordering</code> property.
> * @see #getOrdering()
> */
> public void reorder()
> {
> long t1 = 0, t2 = 0, t3 = 0;
> if (log.isDebugEnabled())
> {
> t1 = System.currentTimeMillis();
> }
> newOrder = new Identity[originalOrder.size()];
> newOrderIndex = 0;
>
> // set up the vertex array in the order the envelopes were added
> List vertexList = new ArrayList(originalOrder.size());
> int vertexIndex = 0;
> for (Iterator it = originalOrder.iterator(); it.hasNext();)
> {
> ObjectEnvelope envelope = (ObjectEnvelope) envelopes.get(it.next());
> if (envelope.needsUpdate()
> || envelope.needsInsert()
> || envelope.needsDelete())
> {
> Vertex vertex = new Vertex(envelope);
> vertexList.add(vertex);
> }
> else
> {
> // envelope is clean - just add identity to new order
> newOrder[newOrderIndex++] = envelope.getIdentity();
> }
> }
> vertices = (Vertex[]) vertexList.toArray(new Vertex[vertexList.size()]);
>
> // set up the edges
> edgeMap = new HashMap(2 * vertices.length, 0.75f);
> for (int i = 0; i < vertices.length; i++)
> {
> addEdgesForVertex(vertices[i]);
> }
>
> if (log.isDebugEnabled())
> {
> t2 = System.currentTimeMillis();
> log.debug(
> "Building object envelope graph took " + (t2 - t1) + " ms");
> log.debug(
> "Object envelope graph contains "
> + vertices.length
> + " vertices"
> + " and "
> + edgeMap.size()
> + " edges");
> }
>
> int remainingVertices = vertices.length;
> int iterationCount = 0;
> while (remainingVertices > 0)
> {
> // update iteration count
> iterationCount++;
>
> // update incoming edge counts
> for (Iterator it = edgeMap.values().iterator(); it.hasNext();)
> {
> Edge edge = (Edge) it.next();
> if (!edge.isProcessed())
> {
> edge.getTerminalVertex().incrementIncomingEdgeWeight(
> edge.getWeight());
> }
> }
>
> // find minimum weight of incoming edges of a vertex
> int minIncomingEdgeWeight = Integer.MAX_VALUE;
> for (int i = 0; i < vertices.length; i++)
> {
> Vertex vertex = vertices[i];
> if (!vertex.isProcessed()
> && minIncomingEdgeWeight > vertex.getIncomingEdgeWeight())
> {
> minIncomingEdgeWeight = vertex.getIncomingEdgeWeight();
> if (minIncomingEdgeWeight == 0)
> {
> // we won't get any lower
> break;
> }
> }
> }
>
> // process vertices having minimum incoming edge weight
> int processCount = 0;
> for (int i = 0; i < vertices.length; i++)
> {
> Vertex vertex = vertices[i];
> if (!vertex.isProcessed()
> && vertex.getIncomingEdgeWeight() == minIncomingEdgeWeight)
> {
> newOrder[newOrderIndex++] =
> vertex.getEnvelope().getIdentity();
> vertex.markProcessed();
> processCount++;
> }
> vertex.resetIncomingEdgeWeight();
> }
>
> if (log.isDebugEnabled())
> {
> log.debug(
> "Processed "
> + processCount
> + " of "
> + remainingVertices
> + " remaining vertices in iteration #"
> + iterationCount);
> }
> remainingVertices -= processCount;
> }
>
> if (log.isDebugEnabled())
> {
> t3 = System.currentTimeMillis();
> log.debug(
> "Processing object envelope graph took " + (t3 - t2) + " ms");
> }
>
> }
>
> /**
> * Gets the reordered sequence of object envelopes
> * @return an array of Identity objects representing the opimized sequence
> * of database operations
> */
> public Identity[] getOrdering()
> {
> if (newOrder == null)
> {
> reorder();
> }
> return newOrder;
> }
>
> /**
> * Adds all edges for a given object envelope vertex. All edges are
> * added to the edgeMap map.
> * @param vertex the Vertex object to find edges for
> */
> private void addEdgesForVertex(Vertex vertex)
> {
> PersistenceBroker broker = transaction.getBroker();
> Object object = vertex.getEnvelope().getObject();
> ClassDescriptor cld = broker.getClassDescriptor(object.getClass());
> Iterator rdsIter = cld.getObjectReferenceDescriptors().iterator();
> while (rdsIter.hasNext())
> {
> ObjectReferenceDescriptor rds =
> (ObjectReferenceDescriptor) rdsIter.next();
> addObjectReferenceEdges(vertex, rds);
> }
> Iterator cdsIter = cld.getCollectionDescriptors().iterator();
> while (cdsIter.hasNext())
> {
> CollectionDescriptor cds = (CollectionDescriptor) cdsIter.next();
> addCollectionEdges(vertex, cds);
> }
> }
>
> /**
> * Finds edges based to a specific object reference descriptor and
> * adds them to the edge map.
> * @param vertex the object envelope vertex holding the object reference
> * @param rds the object reference descriptor
> */
> private void addObjectReferenceEdges(
> Vertex vertex,
> ObjectReferenceDescriptor rds)
> {
> Object refObject =
> rds.getPersistentField().get(vertex.getEnvelope().getObject());
> Class refClass = rds.getItemClass();
> for (int i = 0; i < vertices.length; i++)
> {
> Edge edge = null;
> ObjectEnvelope envelope = vertex.getEnvelope();
> Vertex refVertex = vertices[i];
> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
> if (refObject == refEnvelope.getObject())
> {
> edge = buildConcrete11Edge(vertex, refVertex);
> }
> else if (refClass.isInstance(refVertex.getEnvelope().getObject()))
> {
> edge = buildPotential11Edge(vertex, refVertex);
> }
> if (edge != null)
> {
> Edge existingEdge = (Edge) edgeMap.get(edge);
> if (existingEdge == null)
> {
> edgeMap.put(edge, edge);
> }
> else
> {
> existingEdge.increaseWeightTo(edge.getWeight());
> }
> }
> }
> }
>
> /**
> * Finds edges base on a specific collection descriptor (1:n and m:n)
> * and adds them to the edge map.
> * @param vertex the object envelope vertex holding the collection
> * @param cds the collection descriptor
> */
> private void addCollectionEdges(Vertex vertex, CollectionDescriptor cds)
> {
> ObjectEnvelope envelope = vertex.getEnvelope();
> Object col = cds.getPersistentField().get(envelope.getObject());
> Object[] refObjects;
> if (col == null
> || (ProxyHelper.isCollectionProxy(col)
> && !ProxyHelper.getCollectionProxy(col).isLoaded()))
> {
> refObjects = new Object[0];
> }
> else
> {
> if (col instanceof Collection)
> {
> refObjects = ((Collection) col).toArray();
>
> }
> else if (col instanceof Object[])
> {
> refObjects = (Object[]) col;
> }
> else
> {
> throw new OJBRuntimeException(
> "Given object collection of type "
> + col.getClass()
> + " can not be managed by OJB. Use Array, Collection or
> ManageableCollection instead!");
> }
> }
> Class refClass = cds.getItemClass();
>
> for (int i = 0; i < vertices.length; i++)
> {
> Edge edge = null;
> Vertex refVertex = vertices[i];
> ObjectEnvelope refEnvelope = refVertex.getEnvelope();
>
> if (refClass.isInstance(refEnvelope.getObject()))
> {
> if (containsObject(refEnvelope.getObject(), refObjects))
> {
> if (cds.isMtoNRelation())
> {
> edge = buildConcreteMNEdge(vertex, refVertex);
> }
> else
> {
> edge = buildConcrete1NEdge(vertex, refVertex);
> }
> }
> else
> {
> if (cds.isMtoNRelation())
> {
> edge = buildPotentialMNEdge(vertex, refVertex);
> }
> else
> {
> edge = buildPotential1NEdge(vertex, refVertex);
> }
> }
> }
> if (edge != null)
> {
> Edge existingEdge = (Edge) edgeMap.get(edge);
> if (existingEdge == null)
> {
> edgeMap.put(edge, edge);
> }
> else
> {
> existingEdge.increaseWeightTo(edge.getWeight());
> }
> }
> }
> }
>
> /**
> * Helper method that searches an object array for the occurence of a
> * specific object based on reference equality
> * @param searchFor the object to search for
> * @param searchIn the array to search in
> * @return true if the object is found, otherwise false
> */
> private static boolean containsObject(Object searchFor, Object[] searchIn)
> {
> for (int i = 0; i < searchIn.length; i++)
> {
> if (searchFor == searchIn[i])
> {
> return true;
> }
> }
> return false;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are related via an 1:1 (or n:1) reference needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the reference
> * @param vertex2 object envelope vertex of the referenced object
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildConcrete11Edge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsInsert())
> {
> if (state2.needsInsert())
> {
> // (2) must be inserted before (1) can point to it
> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> }
> }
> else if (state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // (1) points to (2) and must be deleted first
> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that might have been related via an 1:1 (or n:1) reference before
> * the current transaction needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:1)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:1)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object that might have
> * hold the reference
> * @param vertex2 object envelope vertex of the potentially referenced
> * object
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildPotential11Edge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // old version of (1) might point to (2)
> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are related via an 1:n collection reference needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object contained in the
> * collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildConcrete1NEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsInsert())
> {
> if (state2.needsUpdate() || state2.needsInsert())
> {
> // (2) now contains an FK to (1) thus (1) must be inserted first
> return new Edge(vertex1, vertex2, CONCRETE_EDGE_WEIGHT);
> }
> }
> else if (state1.needsDelete())
> {
> if (state2.needsUpdate() || state2.needsDelete())
> {
> // Before deleting (1) give (2) a chance to drop its FK to it
> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are might have been related via an 1:n collection reference before
> * the current transaction needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(1:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(1:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(1:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)*</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(1:n)-> (2)-</td><td>(2)->(1) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object that might have
> * been contained in the collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildPotential1NEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsDelete())
> {
> if (state2.needsUpdate() || state2.needsDelete())
> {
> // Before deleting (1) give potential previous collection
> // members a chance to drop their FKs to it
> return new Edge(vertex2, vertex1, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that are related via an m:n collection reference needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>CONCRETE_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>(2)->(1) edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge (cannot occur)</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object contained in the
> * collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildConcreteMNEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsInsert())
> {
> if (state2.needsInsert())
> {
> // (2) must be inserted before we can create a link to it
> return new Edge(vertex2, vertex1, CONCRETE_EDGE_WEIGHT);
> }
> }
> else if (state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // there is a link from (1) to (2) which must be deleted first,
> // which will happen when deleting (1) - thus:
> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Checks if the database operations associated with two object envelopes
> * that might have been related via an m:n collection reference before
> * the current transaction needs to be performed
> * in a particular order and if so builds and returns a corresponding
> * directed edge weighted with <code>POTENTIAL_EDGE_WEIGHT</code>.
> * The following cases are considered (* means object needs update, + means
> * object needs insert, - means object needs to be deleted):
> * <table>
> * <tr><td>(1)* -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)* -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)+ -(m:n)-> (2)-</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)*</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)+</td><td>no edge</td></tr>
> * <tr><td>(1)- -(m:n)-> (2)-</td><td>(1)->(2) edge</td></tr>
> * <table>
> * @param vertex1 object envelope vertex of the object holding the
> * collection
> * @param vertex2 object envelope vertex of the object that might have
> * been contained in the collection
> * @return an Edge object or null if the two database operations can
> * be performed in any order
> */
> protected Edge buildPotentialMNEdge(Vertex vertex1, Vertex vertex2)
> {
> ModificationState state1 = vertex1.getEnvelope().getModificationState();
> ModificationState state2 = vertex2.getEnvelope().getModificationState();
> if (state1.needsUpdate() || state1.needsDelete())
> {
> if (state2.needsDelete())
> {
> // old version of (1) might comprise a link to (2)
> return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
> }
> }
> return null;
> }
>
> /**
> * Represents an edge in the object envelope graph
> */
> private static class Edge
> {
> private Vertex initial;
> private Vertex terminal;
> private Identity initialIdentity;
> private Identity terminalIdentity;
> private int weight;
> private boolean knownToBeProcessed;
> private int hashCode;
>
> public Edge(Vertex initial, Vertex terminal, int weight)
> {
> this.initial = initial;
> this.terminal = terminal;
> this.initialIdentity = initial.getEnvelope().getIdentity();
> this.terminalIdentity = terminal.getEnvelope().getIdentity();
> this.weight = weight;
> this.knownToBeProcessed = false;
> this.hashCode =
> initialIdentity.hashCode() + 13 * terminalIdentity.hashCode();
> }
> public Vertex getInitialVertex()
> {
> return initial;
> }
> public Vertex getTerminalVertex()
> {
> return terminal;
> }
> public boolean connects(Vertex vertex)
> {
> return initial == vertex || terminal == vertex;
> }
> public void increaseWeightTo(int minWeight)
> {
> if (weight < minWeight)
> {
> weight = minWeight;
> }
> }
> public int getWeight()
> {
> return weight;
> }
> public boolean isProcessed()
> {
> if (knownToBeProcessed)
> {
> return true;
> }
> else
> {
> boolean processed =
> initial.isProcessed() || terminal.isProcessed();
> if (processed)
> {
> knownToBeProcessed = true;
> }
> return processed;
> }
> }
> public boolean equals(Object obj)
> {
> if (obj instanceof Edge)
> {
> Edge other = (Edge) obj;
> return this.initialIdentity.equals(other.initialIdentity)
> && this.terminalIdentity.equals(other.terminalIdentity);
> }
> else
> {
> return false;
> }
> }
> public int hashCode()
> {
> return hashCode;
> }
> }
>
> /**
> * Represents a vertex in the object envelope graph
> */
> private static class Vertex
> {
> private ObjectEnvelope envelope;
> private boolean processed;
> private int incomingEdgeWeight;
>
> public Vertex(ObjectEnvelope envelope)
> {
> this.envelope = envelope;
> this.incomingEdgeWeight = 0;
> this.processed = false;
> }
> public ObjectEnvelope getEnvelope()
> {
> return envelope;
> }
> public void markProcessed()
> {
> processed = true;
> }
> public boolean isProcessed()
> {
> return processed;
> }
> public void resetIncomingEdgeWeight()
> {
> incomingEdgeWeight = 0;
> }
> public void incrementIncomingEdgeWeight(int weight)
> {
> incomingEdgeWeight += weight;
> }
> public int getIncomingEdgeWeight()
> {
> return incomingEdgeWeight;
> }
> }
>
> }
>
>
>
>
>
>
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-dev-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-dev-help@db.apache.org