You are viewing a plain text version of this content. The canonical link for it is here.
Posted to ojb-user@db.apache.org by Gerhard Grosse <ge...@lex-com.net> on 2004/11/18 14:54:35 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-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-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>.
Hi Jakob,
On Fri, 19 Nov 2004 08:20:53 +0100 (MET), "Jakob Braeuchi" <jb...@gmx.ch>
wrote:
>hi armin,
>
>in the testcase i mentioned the auto-update is set to LINK.
>does the scenario you describe also work for odmg ? i was thinking of
>something similar in PB: the PB keeps track of the mn-implementors to be
>inserted and inserts them when the main objects are in the tables.
>
If something like this could be realalized at PB level, it would remove the need
for any ordering of m:n related objects. And this would in turn further reduce
the probability of contradicting constraints. Note that of course deletions in
the link table would have to occur before any deletion / update of the main
objects.
BTW, are the remaining failing test cases all in M2NTest and due to the
bidirectional m:n relationship? I ran my tests against version 1.0.1 and got
only the 2 failures in org.apache.ojb.odmg.CollectionsTest
(testRemoveCollectionElementWithoutBackReference and
testStoreDeleteCollectionElementWithBackReference) which also failed with the
original ordering.
Gerhard
>gerhards new class correctly orders the objects to be inserted, but cannot
>control the settings of auto-update. so the first obj inserted tries to
>update the indirection-table.
>
>jakob
>
>> Jakob Braeuchi wrote:
>>
>> > hi gerhard,
>> >
>> > the failing testcases in org.apache.ojb.odmg.M2NTest can not at all be
>> > fixed by reordering.
>> >
>> > the problem is the bidirectional m:n relationship with auto-update =
>> > LINK on both sides. no matter what side is inserted first pb tries to
>> > insert into the indirection-table as well. this will always fail.
>> > setting auto-update to OBJECT does also not help in this case because
>> > objects are inserted more than once which leads to a unique key
>> violation.
>> >
>> > the only solution i see is to _defer_ the insertion of the
>> > indirection-table until all main objects are saved. unfortunately i have
>> > no idea how to do this :(
>> >
>>
>> hmm, if we change auto-update to NONE (instead false) for m:n relations,
>> insert/update both sides, "mark" these objects with m:n relation for
>> postprocessing and then populate the Indirection Table by using
>> PBImpl#linkMtoN(Object obj, CollectionDescriptor cod, boolean insert).
>> Note: I never tried this ;-)
>>
>> regards,
>> Armin
>>
>>
>> > jakob
>> >
>> > Jakob Braeuchi schrieb:
>> >
>> >> hi gerhard,
>> >>
>> >> thanks for your contribution. it looks really impressive !
>> >> i integrated your class into to current 1.0.x branch an ran all odmg
>> >> testcases without skipping known issues.
>> >> with the old reorder i get:
>> >>
>> >> Tests run: 207, Failures: 2, Errors: 8
>> >>
>> >> with your ordering i still have 6 errors:
>> >>
>> >> Tests run: 207, Failures: 2, Errors: 6
>> >>
>> >> ie this one:
>> >>
>> >> 3)
>> >>
>>
>testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
>
>> >>
>> >> at
>> >>
>>
>org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
>
>> >>
>> >> at
>> >>
>>
>org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
>
>> >>
>> >> at
>> >> org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
>> >> at
>> >> org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
>> >> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
>> >> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
>> >> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
>> >> at
>> >>
>>
>sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>
>> >>
>> >> at
>> >>
>>
>sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>
>> >>
>> >> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
>> >> Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
>> >> collection of type class
>> >> org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be
>> >> managed by OJB. Use Array, Collection or ManageableCollection instead!
>> >> at
>> >>
>>
>org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
>
>> >>
>> >> at
>> >>
>>
>org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
>
>> >>
>> >> at
>> >>
>>
>org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
>
>> >>
>> >> at
>> >>
>>
>org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
>
>> >>
>> >> at
>> >>
>>
>org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
>
>> >>
>> >>
>> >> jakob
>> >>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-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 armin, gerhard
Armin Waibel schrieb:
> Hi Jakob,
>
> Jakob Braeuchi wrote:
>
>> hi armin,
>>
>> in the testcase i mentioned the auto-update is set to LINK. does the
>> scenario you describe also work for odmg ?
>
>
> suggestion only made for odmg
>
>
> i was thinking of
>
>> something similar in PB: the PB keeps track of the mn-implementors to be
>> inserted and inserts them when the main objects are in the tables.
>>
>
> With PB-api this isn't possible I think, because with PB#store one
> object of the n-side is specified, you will never get all n-side objects
> at once. Current behavior is store n side object + all m-side objects
> and then insert indirection table entries - or I'm wrong?
pb works already works the way i described but only when auto-update is OBJECT
and the whole object graph is stored in one call. you're right, it's not
possible for pb to defer insertion of mn-implementors over multibple store() calls.
>
>
>> gerhards new class correctly orders the objects to be inserted, but
>> cannot
>> control the settings of auto-update. so the first obj inserted tries to
>> update the indirection-table.
>>
>
> That's why I suggest to set auto-update NONE for m:n relations in odmg.
> The main problem is to populate the m:n indirection table, currently we
> don't have the possibility to do this in a high-performance manner.
> For insert only we can use PB#addMtoNImplementor to populate indirection
> table, but this will fire many single sql-statements and will only work
> if we know which indirection entry we have to insert.
another way would be to use INSERT into 'indirection-table' SELECT from
'main-tables' but i'm not sure whether this will work because we'll have to
select from 2 main-tables ??
but i'd be happy with a correct solution, be it a little slow or not ;)
jakob
>
> An alternative way could be to use the link/unlink methods in
> BrokerHelper. An example using PB-api see
> ...broker.M2NTest#doTestStoreFFFX(Movie movie, String postfix)
>
> if we do something similar in an odmg-postprocess it should be possible
> to make m:n work.
>
> regards,
> Armin
>
>
>> jakob
>>
>>
>>> Jakob Braeuchi wrote:
>>>
>>>
>>>> hi gerhard,
>>>>
>>>> the failing testcases in org.apache.ojb.odmg.M2NTest can not at all
>>>> be fixed by reordering.
>>>>
>>>> the problem is the bidirectional m:n relationship with auto-update =
>>>> LINK on both sides. no matter what side is inserted first pb tries
>>>> to insert into the indirection-table as well. this will always fail.
>>>> setting auto-update to OBJECT does also not help in this case
>>>> because objects are inserted more than once which leads to a unique key
>>>
>>>
>>> violation.
>>>
>>>> the only solution i see is to _defer_ the insertion of the
>>>> indirection-table until all main objects are saved. unfortunately i
>>>> have
>>>> no idea how to do this :(
>>>>
>>>
>>> hmm, if we change auto-update to NONE (instead false) for m:n
>>> relations, insert/update both sides, "mark" these objects with m:n
>>> relation for postprocessing and then populate the Indirection Table
>>> by using PBImpl#linkMtoN(Object obj, CollectionDescriptor cod,
>>> boolean insert).
>>> Note: I never tried this ;-)
>>>
>>> regards,
>>> Armin
>>>
>>>
>>>
>>>> jakob
>>>>
>>>> Jakob Braeuchi schrieb:
>>>>
>>>>
>>>>> hi gerhard,
>>>>>
>>>>> thanks for your contribution. it looks really impressive !
>>>>> i integrated your class into to current 1.0.x branch an ran all
>>>>> odmg testcases without skipping known issues.
>>>>> with the old reorder i get:
>>>>>
>>>>> Tests run: 207, Failures: 2, Errors: 8
>>>>>
>>>>> with your ordering i still have 6 errors:
>>>>>
>>>>> Tests run: 207, Failures: 2, Errors: 6
>>>>>
>>>>> ie this one:
>>>>>
>>>>> 3)
>>>
>>>
>> testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
>>
>>
>>
>>>>> at
>>>
>>>
>> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
>>
>>
>>
>>>>> at
>>>
>>>
>> org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
>>
>>
>>
>>>>> at
>>>>> org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
>>>>> at
>>>>> org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
>>>>> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
>>>>> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
>>>>> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
>>>>> at
>>>
>>>
>> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>>
>>
>>
>>>>> at
>>>
>>>
>> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>>
>>
>>
>>>>> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
>>>>> Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
>>>>> collection of type class
>>>>> org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be
>>>>> managed by OJB. Use Array, Collection or ManageableCollection instead!
>>>>> at
>>>
>>>
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
>>
>>
>>
>>>>> at
>>>
>>>
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
>>
>>
>>
>>>>> at
>>>
>>>
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
>>
>>
>>
>>>>> at
>>>
>>>
>> org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
>>
>>
>>
>>>>> at
>>>
>>>
>> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
>>
>>
>>
>>>>>
>>>>> 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-user-unsubscribe@db.apache.org
>>>>>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>>>>>
>>>>>>
>>>>>
>>>>> ---------------------------------------------------------------------
>>>>> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
>>>>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>>>>
>>>>>
>>>>
>>>> ---------------------------------------------------------------------
>>>> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
>>>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>>>
>>>>
>>>>
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
>>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>>
>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-user-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Armin Waibel <ar...@apache.org>.
Hi Jakob,
Jakob Braeuchi wrote:
> hi armin,
>
> in the testcase i mentioned the auto-update is set to LINK.
> does the scenario you describe also work for odmg ?
suggestion only made for odmg
i was thinking of
> something similar in PB: the PB keeps track of the mn-implementors to be
> inserted and inserts them when the main objects are in the tables.
>
With PB-api this isn't possible I think, because with PB#store one
object of the n-side is specified, you will never get all n-side objects
at once. Current behavior is store n side object + all m-side objects
and then insert indirection table entries - or I'm wrong?
> gerhards new class correctly orders the objects to be inserted, but cannot
> control the settings of auto-update. so the first obj inserted tries to
> update the indirection-table.
>
That's why I suggest to set auto-update NONE for m:n relations in odmg.
The main problem is to populate the m:n indirection table, currently we
don't have the possibility to do this in a high-performance manner.
For insert only we can use PB#addMtoNImplementor to populate indirection
table, but this will fire many single sql-statements and will only work
if we know which indirection entry we have to insert.
An alternative way could be to use the link/unlink methods in
BrokerHelper. An example using PB-api see
...broker.M2NTest#doTestStoreFFFX(Movie movie, String postfix)
if we do something similar in an odmg-postprocess it should be possible
to make m:n work.
regards,
Armin
> jakob
>
>
>>Jakob Braeuchi wrote:
>>
>>
>>>hi gerhard,
>>>
>>>the failing testcases in org.apache.ojb.odmg.M2NTest can not at all be
>>>fixed by reordering.
>>>
>>>the problem is the bidirectional m:n relationship with auto-update =
>>>LINK on both sides. no matter what side is inserted first pb tries to
>>>insert into the indirection-table as well. this will always fail.
>>>setting auto-update to OBJECT does also not help in this case because
>>>objects are inserted more than once which leads to a unique key
>>
>>violation.
>>
>>>the only solution i see is to _defer_ the insertion of the
>>>indirection-table until all main objects are saved. unfortunately i have
>>>no idea how to do this :(
>>>
>>
>>hmm, if we change auto-update to NONE (instead false) for m:n relations,
>>insert/update both sides, "mark" these objects with m:n relation for
>>postprocessing and then populate the Indirection Table by using
>>PBImpl#linkMtoN(Object obj, CollectionDescriptor cod, boolean insert).
>>Note: I never tried this ;-)
>>
>>regards,
>>Armin
>>
>>
>>
>>>jakob
>>>
>>>Jakob Braeuchi schrieb:
>>>
>>>
>>>>hi gerhard,
>>>>
>>>>thanks for your contribution. it looks really impressive !
>>>>i integrated your class into to current 1.0.x branch an ran all odmg
>>>>testcases without skipping known issues.
>>>>with the old reorder i get:
>>>>
>>>>Tests run: 207, Failures: 2, Errors: 8
>>>>
>>>>with your ordering i still have 6 errors:
>>>>
>>>>Tests run: 207, Failures: 2, Errors: 6
>>>>
>>>>ie this one:
>>>>
>>>>3)
>>>>
>>
> testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
>
>
>>>> at
>>>>
>>
> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
>
>
>>>> at
>>>>
>>
> org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
>
>
>>>> at
>>>>org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
>>>> at
>>>>org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
>>>> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
>>>> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
>>>> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
>>>> at
>>>>
>>
> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>
>
>>>> at
>>>>
>>
> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>
>
>>>> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
>>>>Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
>>>>collection of type class
>>>>org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be
>>>>managed by OJB. Use Array, Collection or ManageableCollection instead!
>>>> at
>>>>
>>
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
>
>
>>>> at
>>>>
>>
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
>
>
>>>> at
>>>>
>>
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
>
>
>>>> at
>>>>
>>
> org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
>
>
>>>> at
>>>>
>>
> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
>
>
>>>>
>>>>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-user-unsubscribe@db.apache.org
>>>>>For additional commands, e-mail: ojb-user-help@db.apache.org
>>>>>
>>>>>
>>>>
>>>>---------------------------------------------------------------------
>>>>To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
>>>>For additional commands, e-mail: ojb-user-help@db.apache.org
>>>>
>>>>
>>>
>>>---------------------------------------------------------------------
>>>To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
>>>For additional commands, e-mail: ojb-user-help@db.apache.org
>>>
>>>
>>>
>>
>>---------------------------------------------------------------------
>>To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
>>For additional commands, e-mail: ojb-user-help@db.apache.org
>>
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-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 armin,
in the testcase i mentioned the auto-update is set to LINK.
does the scenario you describe also work for odmg ? i was thinking of
something similar in PB: the PB keeps track of the mn-implementors to be
inserted and inserts them when the main objects are in the tables.
gerhards new class correctly orders the objects to be inserted, but cannot
control the settings of auto-update. so the first obj inserted tries to
update the indirection-table.
jakob
> Jakob Braeuchi wrote:
>
> > hi gerhard,
> >
> > the failing testcases in org.apache.ojb.odmg.M2NTest can not at all be
> > fixed by reordering.
> >
> > the problem is the bidirectional m:n relationship with auto-update =
> > LINK on both sides. no matter what side is inserted first pb tries to
> > insert into the indirection-table as well. this will always fail.
> > setting auto-update to OBJECT does also not help in this case because
> > objects are inserted more than once which leads to a unique key
> violation.
> >
> > the only solution i see is to _defer_ the insertion of the
> > indirection-table until all main objects are saved. unfortunately i have
> > no idea how to do this :(
> >
>
> hmm, if we change auto-update to NONE (instead false) for m:n relations,
> insert/update both sides, "mark" these objects with m:n relation for
> postprocessing and then populate the Indirection Table by using
> PBImpl#linkMtoN(Object obj, CollectionDescriptor cod, boolean insert).
> Note: I never tried this ;-)
>
> regards,
> Armin
>
>
> > jakob
> >
> > Jakob Braeuchi schrieb:
> >
> >> hi gerhard,
> >>
> >> thanks for your contribution. it looks really impressive !
> >> i integrated your class into to current 1.0.x branch an ran all odmg
> >> testcases without skipping known issues.
> >> with the old reorder i get:
> >>
> >> Tests run: 207, Failures: 2, Errors: 8
> >>
> >> with your ordering i still have 6 errors:
> >>
> >> Tests run: 207, Failures: 2, Errors: 6
> >>
> >> ie this one:
> >>
> >> 3)
> >>
>
testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
> >>
> >> at
> >>
>
org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
> >>
> >> at
> >>
>
org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
> >>
> >> at
> >> org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
> >> at
> >> org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
> >> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
> >> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
> >> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
> >> at
> >>
>
sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
> >>
> >> at
> >>
>
sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
> >>
> >> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
> >> Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
> >> collection of type class
> >> org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be
> >> managed by OJB. Use Array, Collection or ManageableCollection instead!
> >> at
> >>
>
org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
> >>
> >> at
> >>
>
org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
> >>
> >> at
> >>
>
org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
> >>
> >> at
> >>
>
org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
> >>
> >> at
> >>
>
org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
> >>
> >>
> >> 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-user-unsubscribe@db.apache.org
> >>> For additional commands, e-mail: ojb-user-help@db.apache.org
> >>>
> >>>
> >>
> >> ---------------------------------------------------------------------
> >> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
> >> For additional commands, e-mail: ojb-user-help@db.apache.org
> >>
> >>
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
> > For additional commands, e-mail: ojb-user-help@db.apache.org
> >
> >
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-user-help@db.apache.org
>
--
Geschenkt: 3 Monate GMX ProMail + 3 Top-Spielfilme auf DVD
++ Jetzt kostenlos testen http://www.gmx.net/de/go/mail ++
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Armin Waibel <ar...@apache.org>.
Jakob Braeuchi wrote:
> hi gerhard,
>
> the failing testcases in org.apache.ojb.odmg.M2NTest can not at all be
> fixed by reordering.
>
> the problem is the bidirectional m:n relationship with auto-update =
> LINK on both sides. no matter what side is inserted first pb tries to
> insert into the indirection-table as well. this will always fail.
> setting auto-update to OBJECT does also not help in this case because
> objects are inserted more than once which leads to a unique key violation.
>
> the only solution i see is to _defer_ the insertion of the
> indirection-table until all main objects are saved. unfortunately i have
> no idea how to do this :(
>
hmm, if we change auto-update to NONE (instead false) for m:n relations,
insert/update both sides, "mark" these objects with m:n relation for
postprocessing and then populate the Indirection Table by using
PBImpl#linkMtoN(Object obj, CollectionDescriptor cod, boolean insert).
Note: I never tried this ;-)
regards,
Armin
> jakob
>
> Jakob Braeuchi schrieb:
>
>> hi gerhard,
>>
>> thanks for your contribution. it looks really impressive !
>> i integrated your class into to current 1.0.x branch an ran all odmg
>> testcases without skipping known issues.
>> with the old reorder i get:
>>
>> Tests run: 207, Failures: 2, Errors: 8
>>
>> with your ordering i still have 6 errors:
>>
>> Tests run: 207, Failures: 2, Errors: 6
>>
>> ie this one:
>>
>> 3)
>> testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
>>
>> at
>> org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
>>
>> at
>> org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
>> at
>> org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
>> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
>> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
>> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
>> at
>> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>>
>> at
>> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>>
>> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
>> Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
>> collection of type class
>> org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be
>> managed by OJB. Use Array, Collection or ManageableCollection instead!
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
>>
>>
>> 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-user-unsubscribe@db.apache.org
>>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>>
>>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-user-help@db.apache.org
>
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-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,
the failing testcases in org.apache.ojb.odmg.M2NTest can not at all be fixed by
reordering.
the problem is the bidirectional m:n relationship with auto-update = LINK on
both sides. no matter what side is inserted first pb tries to insert into the
indirection-table as well. this will always fail.
setting auto-update to OBJECT does also not help in this case because objects
are inserted more than once which leads to a unique key violation.
the only solution i see is to _defer_ the insertion of the indirection-table
until all main objects are saved. unfortunately i have no idea how to do this :(
jakob
Jakob Braeuchi schrieb:
> hi gerhard,
>
> thanks for your contribution. it looks really impressive !
> i integrated your class into to current 1.0.x branch an ran all odmg
> testcases without skipping known issues.
> with the old reorder i get:
>
> Tests run: 207, Failures: 2, Errors: 8
>
> with your ordering i still have 6 errors:
>
> Tests run: 207, Failures: 2, Errors: 6
>
> ie this one:
>
> 3)
> testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
>
> at
> org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
>
> at
> org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
> at org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
> at
> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>
> at
> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>
> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
> Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
> collection of type class
> org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be managed
> by OJB. Use Array, Collection or ManageableCollection instead!
> at
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
>
>
> 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-user-unsubscribe@db.apache.org
>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-user-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-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>.
Hi Jakob
On Thu, 18 Nov 2004 21:17:04 +0100, Jakob Braeuchi <jb...@gmx.ch> wrote:
>hi gerhard,
>
>i applied a small fix in addCollectionEdges()
>
>...
> else
> {
> if (col instanceof ManageableCollection)
> {
> Collection newCol = new ArrayList();
> CollectionUtils.addAll(newCol, ((ManageableCollection)
>col).ojbIterator());
>
> refObjects = newCol.toArray();
> }
> else if (col instanceof Collection)
> {
> refObjects = ((Collection) col).toArray();
>
> }
> else if (col instanceof Object[])
>...
>
>two of the reported problems were caused by the fact that ManageableCollection
>does not extend Collection.
>
Oops... Yep, that's something I overlooked. I should have got suspicious when I
copied that error message from BrokerHelp.getCollectionIterator ... :-)
Gerhard
>but i still have problems in org.apache.ojb.odmg.M2NTest.
>
>Tests run: 207, Failures: 2, Errors: 6
>
>jakob
>
>Jakob Braeuchi schrieb:
>
>> hi gerhard,
>>
>> thanks for your contribution. it looks really impressive !
>> i integrated your class into to current 1.0.x branch an ran all odmg
>> testcases without skipping known issues.
>> with the old reorder i get:
>>
>> Tests run: 207, Failures: 2, Errors: 8
>>
>> with your ordering i still have 6 errors:
>>
>> Tests run: 207, Failures: 2, Errors: 6
>>
>> ie this one:
>>
>> 3)
>> testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
>>
>> at
>> org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
>>
>> at
>> org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
>> at org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
>> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
>> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
>> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
>> at
>> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>>
>> at
>> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>>
>> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
>> Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
>> collection of type class
>> org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be managed
>> by OJB. Use Array, Collection or ManageableCollection instead!
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
>>
>> at
>> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
>>
>>
>> jakob
>>
>>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-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 applied a small fix in addCollectionEdges()
...
else
{
if (col instanceof ManageableCollection)
{
Collection newCol = new ArrayList();
CollectionUtils.addAll(newCol, ((ManageableCollection)
col).ojbIterator());
refObjects = newCol.toArray();
}
else if (col instanceof Collection)
{
refObjects = ((Collection) col).toArray();
}
else if (col instanceof Object[])
...
two of the reported problems were caused by the fact that ManageableCollection
does not extend Collection.
but i still have problems in org.apache.ojb.odmg.M2NTest.
Tests run: 207, Failures: 2, Errors: 6
jakob
Jakob Braeuchi schrieb:
> hi gerhard,
>
> thanks for your contribution. it looks really impressive !
> i integrated your class into to current 1.0.x branch an ran all odmg
> testcases without skipping known issues.
> with the old reorder i get:
>
> Tests run: 207, Failures: 2, Errors: 8
>
> with your ordering i still have 6 errors:
>
> Tests run: 207, Failures: 2, Errors: 6
>
> ie this one:
>
> 3)
> testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
>
> at
> org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
>
> at
> org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
> at org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
> at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
> at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
> at
> sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
>
> at
> sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
>
> at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
> Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object
> collection of type class
> org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be managed
> by OJB. Use Array, Collection or ManageableCollection instead!
> at
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
>
> at
> org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
>
>
> 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-user-unsubscribe@db.apache.org
>> For additional commands, e-mail: ojb-user-help@db.apache.org
>>
>>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-user-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-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,
thanks for your contribution. it looks really impressive !
i integrated your class into to current 1.0.x branch an ran all odmg testcases
without skipping known issues.
with the old reorder i get:
Tests run: 207, Failures: 2, Errors: 8
with your ordering i still have 6 errors:
Tests run: 207, Failures: 2, Errors: 6
ie this one:
3)
testStoreComplex(org.apache.ojb.odmg.M2NTest)org.apache.ojb.odmg.TransactionAbortedExceptionOJB
at org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:174)
at org.apache.ojb.odmg.TransactionImpl.doWriteObjects(TransactionImpl.java:324)
at org.apache.ojb.odmg.TransactionImpl.prepare(TransactionImpl.java:624)
at org.apache.ojb.odmg.TransactionImpl.commit(TransactionImpl.java:581)
at org.apache.ojb.odmg.M2NTest.doTestStoreComplex(M2NTest.java:157)
at org.apache.ojb.odmg.M2NTest.testStoreComplex(M2NTest.java:137)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
at
sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
at org.apache.ojb.odmg.AllTests.main(AllTests.java:18)
Caused by: org.apache.ojb.broker.OJBRuntimeException: Given object collection of
type class org.apache.ojb.odmg.M2NTest$MovieManageableCollection can not be
managed by OJB. Use Array, Collection or ManageableCollection instead!
at
org.apache.ojb.odmg.ObjectEnvelopeOrdering.addCollectionEdges(ObjectEnvelopeOrdering.java:312)
at
org.apache.ojb.odmg.ObjectEnvelopeOrdering.addEdgesForVertex(ObjectEnvelopeOrdering.java:241)
at
org.apache.ojb.odmg.ObjectEnvelopeOrdering.reorder(ObjectEnvelopeOrdering.java:133)
at org.apache.ojb.odmg.ObjectEnvelopeTable.reorder(ObjectEnvelopeTable.java:588)
at org.apache.ojb.odmg.ObjectEnvelopeTable.commit(ObjectEnvelopeTable.java:148)
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-user-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-user-help@db.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-help@db.apache.org
Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Posted by Łukasz Korzybski <na...@xtr.net.pl>.
Dnia czwartek, 18 listopada 2004 14:54, Gerhard Grosse napisał:
> Hi,
>
...
>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.
That sounds terrific! It woud be great to see it in OJB.
---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-user-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-user-help@db.apache.org