db-ojb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jakob Braeuchi <jbraeu...@gmx.ch>
Subject Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Date Sat, 20 Nov 2004 09:56:48 GMT
hi gerhard,

i commited your patch to 1.1 trunk.

jakob


Gerhard Grosse schrieb:

> Hi,
> 
> for quite some time we were experiencing problems with FK constraint violations
> when committing ODMG transactions. We resolved these problems by inserting
> TransactionExt.flush() calls wherever necessary. However, this in turn produced
> deadlock problems under high server load. Therefore we decided to try and
> improve the ordering of the SQL sent to the database. These efforts resulted in
> a class org.ojb.odmg.ObjectEnvelopeOrdering which we hereby contribute to the
> OJB community, because other users seem to have similar problems.
> 
> To use this class, the private method reorder() in class
> org.ojb.odmg.ObjectEnvelopeTable must be replaced with:
> 
> private void reorder()
> {
>   if (needsCommit)
>   {
>     ObjectEnvelopeOrdering ordering = 
>       new ObjectEnvelopeOrdering(transaction,mvOrderOfIds,mhtObjectEnvelopes);
>     ordering.reorder();
>     Identity[] newOrder = ordering.getOrdering();
>     mvOrderOfIds.clear();
>     for (int i = 0; i < newOrder.length; i++)
>     {
>       mvOrderOfIds.add(newOrder[i]);
>     }
>   }
> }
> 
> The ObjectEnvelopeOrdering class addresses the following problems we observed
> with the original ordering algorithm:
> 
> (1) the ordering is based on the modified state of the objects only; therefore
> if a reference in object A is set to null, OJB does not see that before
> modification A referenced an object B to be deleted. 
> 
> (2) 1:n and m:n collections are treated in the same way, although the
> FK-location in the DB is quite different. 
> 
> (3) the ordering algorithm is 'greedy' in the sense that once an object
> modification has been put into the ordered list, it will stay at this position
> even if later constraints are found that would require to move it to a position
> further down.
> 
> (4) issue (3) is aggravated by the fact that the ordering does not take into
> account the modification state of a referenced object. Therefore objects are
> inserted into the ordered list even if there is no real need for ordering. Later
> a real constraint me be encountered, but now the object is already frozen at its
> new position.
> 
> The ObjectEnvelopeOrdering class uses a graph-theoretical approach to order the
> object envelopes (see the JavaDoc for details). Edges in this graph are inserted
> only if there really is a need for ordering two object envelopes with respect to
> each other - determining this need is based on the modification state of both
> objects and the type of relation the two have to each other (1:1, 1:n, or m:n).
> This addresses issues (2)-(4). 
> 
> Issue (1) is not addressed as as niftily: Since we did not want to change the
> ObjectEnvelope class, we opted for a heuristic solution, where 'potential'
> relations between two objects are taken into account based on the class type of
> a reference.
> 
> Test results:
> After using the ObjectEnvelopeOrdering class we were able to remove all flush
> statements from our application without any test case failing. The results of
> the JUnit tests of OJB did not change either (some fail before and after the
> change), with one exception:
> org.apache.ojb.broker.sequence.NativeIdentifierTest.testReferenceInsertUpdateODMG.
> Before our change, this test failed with a failed assertion, after our change it
> now causes an FK violation error. Looking at the test code, I cannot see how the
> FK error could be avoided, because there are two tables with FKs referencing
> each other and the test attempts to insert two objects with references to each
> other in a single transaction. As far as I can see, there is no order of INSERT
> statements that could avoid the FK error.
> 
> Performance:
> The ordering process implemented by the ObjectEnvelopeOrdering class is
> certainly slower than the original recursive ordering. This is mainly due to 
> the need of addressing issue (1). In our real application scenario, however, we
> do not notice any perfomance degradation.
> 
> AFAIK the OJB mailing list does not accept attachements, therefore I am posting
> the class code inline. If anyone knows a better way to submit the code without
> distortion due to line breaks, please let me know. 
> 
> We would be happy if the class would make it into the 'official' OJB. In any
> case feel free to use it if it suits you. Of course the usual disclaimer apply
> (no warranty of any kind...)
> 
> Gerhard
> 
> -------------------------------
> 
> package org.apache.ojb.odmg;
> 
> import java.util.ArrayList;
> import java.util.Collection;
> import java.util.HashMap;
> import java.util.Iterator;
> import java.util.List;
> import java.util.Map;
> 
> import org.apache.ojb.broker.Identity;
> import org.apache.ojb.broker.OJBRuntimeException;
> import org.apache.ojb.broker.PersistenceBroker;
> import org.apache.ojb.broker.core.proxy.ProxyHelper;
> import org.apache.ojb.broker.metadata.ClassDescriptor;
> import org.apache.ojb.broker.metadata.CollectionDescriptor;
> import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
> import org.apache.ojb.broker.util.logging.Logger;
> import org.apache.ojb.broker.util.logging.LoggerFactory;
> import org.apache.ojb.odmg.states.ModificationState;
> 
> /**
>  * <p>Implements an algorithm for reordering the object envelopes of a pending
>  * transaction to minimized the probability of foreign key constraint
>  * violations.</p>
>  * 
>  * <p>The algorithm is based on a graph theoretical approach: Each object
>  * envelope is represented by a vertex in a graph. Each possible constraint
>  * on the order of database operations is represented by a directed edge
>  * in this graph, in which the initial vertex represents the object envelope
>  * to be sent to the database first and the terminal index represents the
>  * object envelope that might cause a FK violation if the initial vertex
>  * has not been sent to the database before.</p> 
>  * 
>  * <p>Additionally the edges in this graph are weighted. This is necessary
>  * because the object envelopes provide only information on the relation
>  * between objects <strong>after</strong> the transaction. FK violations,

>  * however, can also occur due to relations that existed <strong>before</strong>
>  * the transaction. Therefore the algorithm also considers potential relations
>  * between objects due to the fact that an object is of a class that is
>  * the item class of a object or collection reference of another object.
>  * Graph edges representing such potential relationships receive a lower
>  * weight than edges representing concrete relationships that exist in the
>  * current state of the object model.</p>
>  * 
>  * <p>Once all graph edges have been established, the algorithm proceeds as
>  * follows:</p>
>  * <ol>
>  *  <li>Iterate through all vertices and sum up the weight of all incoming
>  *      edges (i.e. those edges whose terminal vertex is the current
> vertex).</li>
>  *  <li>Find the minimum value of this weight sums (ideally this minimum is
> zero,
>  *      meaning that there are object envelopes that can be sent to the 
>  *      database without risking FK violations)<il>
>  *  <li>Add all vertices with a weight sum that is equal to this minimum to the
>  *      reordered sequence of object envelopes and remove the vertices
>  *      and all connected edges from the graph.</li>
>  *  <li>If there are vertices left, repeat steps (1) through (3), otherwise
>  *      we are done.
>  * </ol>
>  *
>  * @author  Gerhard Grosse
>  * @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2004/11/18 12:25:28 grosse
> Exp $
>  * @since   Nov 15, 2004
>  */
> public class ObjectEnvelopeOrdering
> {
>     private static final int CONCRETE_EDGE_WEIGHT = 2;
>     private static final int POTENTIAL_EDGE_WEIGHT = 1;
> 
>     private static Logger log =
>         LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
> 
>     private List originalOrder;
>     private Map envelopes;
>     private TransactionImpl transaction;
> 
>     private Vertex[] vertices;
>     private Map edgeMap;
> 
>     private int newOrderIndex;
>     private Identity[] newOrder;
> 
>     /**
>      * Creates an object envelope ordering based on an original ordering
>      * of Identity objects and an Identity-&gt;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)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(1:1)-&gt; (2)+</td><td>(2)-&gt;(1)
edge</td></tr>
>      *  <tr><td>(1)* -(1:1)-&gt; (2)-</td><td>no edge (cannot
occur)</td></tr>
>      *  <tr><td>(1)+ -(1:1)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(1:1)-&gt; (2)+</td><td>(2)-&gt;(1)
edge</td></tr>
>      *  <tr><td>(1)+ -(1:1)-&gt; (2)-</td><td>no edge (cannot
occur)</td></tr>
>      *  <tr><td>(1)- -(1:1)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:1)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:1)-&gt; (2)-</td><td>(1)-&gt;(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)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(1:1)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(1:1)-&gt; (2)-</td><td>(1)-&gt;(2)
edge</td></tr>
>      *  <tr><td>(1)+ -(1:1)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(1:1)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(1:1)-&gt; (2)-</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:1)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:1)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:1)-&gt; (2)-</td><td>(1)-&gt;(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)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(1:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(1:n)-&gt; (2)-</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(1:n)-&gt; (2)*</td><td>(1)-&gt;(2)
edge</td></tr>
>      *  <tr><td>(1)+ -(1:n)-&gt; (2)+</td><td>(1)-&gt;(2)
edge</td></tr>
>      *  <tr><td>(1)+ -(1:n)-&gt; (2)-</td><td>no edge (cannot
occur)</td></tr>
>      *  <tr><td>(1)- -(1:n)-&gt; (2)*</td><td>(2)-&gt;(1)
edge</td></tr>
>      *  <tr><td>(1)- -(1:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:n)-&gt; (2)-</td><td>(2)-&gt;(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)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(1:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(1:n)-&gt; (2)-</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(1:n)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(1:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(1:n)-&gt; (2)-</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:n)-&gt; (2)*</td><td>(2)-&gt;(1)
edge</td></tr>
>      *  <tr><td>(1)- -(1:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(1:n)-&gt; (2)-</td><td>(2)-&gt;(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)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(m:n)-&gt; (2)+</td><td>(2)-&gt;(1)
edge</td></tr>
>      *  <tr><td>(1)* -(m:n)-&gt; (2)-</td><td>no edge (cannot
occur)</td></tr>
>      *  <tr><td>(1)+ -(m:n)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(m:n)-&gt; (2)+</td><td>(2)-&gt;(1)
edge</td></tr>
>      *  <tr><td>(1)+ -(m:n)-&gt; (2)-</td><td>no edge (cannot
occur)</td></tr>
>      *  <tr><td>(1)- -(m:n)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(m:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(m:n)-&gt; (2)-</td><td>(1)-&gt;(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)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(m:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)* -(m:n)-&gt; (2)-</td><td>(1)-&gt;(2)
edge</td></tr>
>      *  <tr><td>(1)+ -(m:n)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(m:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)+ -(m:n)-&gt; (2)-</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(m:n)-&gt; (2)*</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(m:n)-&gt; (2)+</td><td>no edge</td></tr>
>      *  <tr><td>(1)- -(m:n)-&gt; (2)-</td><td>(1)-&gt;(2)
edge</td></tr>
>      * <table>
>      * @param vertex1 object envelope vertex of the object holding the 
>      *      collection
>      * @param vertex2 object envelope vertex of the object that might have
>      *      been contained in the collection
>      * @return an Edge object or null if the two database operations can
>      *      be performed in any order
>      */
>     protected Edge buildPotentialMNEdge(Vertex vertex1, Vertex vertex2)
>     {
>         ModificationState state1 = vertex1.getEnvelope().getModificationState();
>         ModificationState state2 = vertex2.getEnvelope().getModificationState();
>         if (state1.needsUpdate() || state1.needsDelete())
>         {
>             if (state2.needsDelete())
>             {
>                 // old version of (1) might comprise a link to (2)
>                 return new Edge(vertex1, vertex2, POTENTIAL_EDGE_WEIGHT);
>             }
>         }
>         return null;
>     }
> 
>     /**
>      * Represents an edge in the object envelope graph
>      */
>     private static class Edge
>     {
>         private Vertex initial;
>         private Vertex terminal;
>         private Identity initialIdentity;
>         private Identity terminalIdentity;
>         private int weight;
>         private boolean knownToBeProcessed;
>         private int hashCode;
> 
>         public Edge(Vertex initial, Vertex terminal, int weight)
>         {
>             this.initial = initial;
>             this.terminal = terminal;
>             this.initialIdentity = initial.getEnvelope().getIdentity();
>             this.terminalIdentity = terminal.getEnvelope().getIdentity();
>             this.weight = weight;
>             this.knownToBeProcessed = false;
>             this.hashCode =
>                 initialIdentity.hashCode() + 13 * terminalIdentity.hashCode();
>         }
>         public Vertex getInitialVertex()
>         {
>             return initial;
>         }
>         public Vertex getTerminalVertex()
>         {
>             return terminal;
>         }
>         public boolean connects(Vertex vertex)
>         {
>             return initial == vertex || terminal == vertex;
>         }
>         public void increaseWeightTo(int minWeight)
>         {
>             if (weight < minWeight)
>             {
>                 weight = minWeight;
>             }
>         }
>         public int getWeight()
>         {
>             return weight;
>         }
>         public boolean isProcessed()
>         {
>             if (knownToBeProcessed)
>             {
>                 return true;
>             }
>             else
>             {
>                 boolean processed =
>                     initial.isProcessed() || terminal.isProcessed();
>                 if (processed)
>                 {
>                     knownToBeProcessed = true;
>                 }
>                 return processed;
>             }
>         }
>         public boolean equals(Object obj)
>         {
>             if (obj instanceof Edge)
>             {
>                 Edge other = (Edge) obj;
>                 return this.initialIdentity.equals(other.initialIdentity)
>                     && this.terminalIdentity.equals(other.terminalIdentity);
>             }
>             else
>             {
>                 return false;
>             }
>         }
>         public int hashCode()
>         {
>             return hashCode;
>         }
>     }
> 
>     /**
>      * Represents a vertex in the object envelope graph
>      */
>     private static class Vertex
>     {
>         private ObjectEnvelope envelope;
>         private boolean processed;
>         private int incomingEdgeWeight;
> 
>         public Vertex(ObjectEnvelope envelope)
>         {
>             this.envelope = envelope;
>             this.incomingEdgeWeight = 0;
>             this.processed = false;
>         }
>         public ObjectEnvelope getEnvelope()
>         {
>             return envelope;
>         }
>         public void markProcessed()
>         {
>             processed = true;
>         }
>         public boolean isProcessed()
>         {
>             return processed;
>         }
>         public void resetIncomingEdgeWeight()
>         {
>             incomingEdgeWeight = 0;
>         }
>         public void incrementIncomingEdgeWeight(int weight)
>         {
>             incomingEdgeWeight += weight;
>         }
>         public int getIncomingEdgeWeight()
>         {
>             return incomingEdgeWeight;
>         }
>     }
> 
> }
> 
> 
> 
> 
> 
> 
> 
> 
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
> For additional commands, e-mail: ojb-dev-help@db.apache.org
> 
> 

---------------------------------------------------------------------
To unsubscribe, e-mail: ojb-dev-unsubscribe@db.apache.org
For additional commands, e-mail: ojb-dev-help@db.apache.org


Mime
View raw message