db-ojb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gerhard Grosse <gerhard.gro...@lex-com.net>
Subject Java class for ordering SQL statements in ODMG to avoid FK violations
Date Thu, 18 Nov 2004 13:06:48 GMT
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


Mime
View raw message