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 Sun, 21 Nov 2004 09:26:35 GMT
hi brian,

it imports org.apache.ojb.odmg.states.ModificationState.
do you already have an implementation of the sort ?

jakob

Brian McCallister schrieb:
> Fantastic!
> 
> I haven't looked closely at the code yet, but is it dependent (for
> operation, not compile ;-) on ODMG classes? I need the exact same
> topological sort for the object space transaction stuff (against PB)
> in 1.1 =)
> 
> Thank you!
> 
> -Brian
> 
> On Thu, 18 Nov 2004 14:06:48 +0100, Gerhard Grosse
> <gerhard.grosse@lex-com.net> wrote:
> 
>>Hi,
>>
>>for quite some time we were experiencing problems with FK constraint violations
>>when committing ODMG transactions. We resolved these problems by inserting
>>TransactionExt.flush() calls wherever necessary. However, this in turn produced
>>deadlock problems under high server load. Therefore we decided to try and
>>improve the ordering of the SQL sent to the database. These efforts resulted in
>>a class org.ojb.odmg.ObjectEnvelopeOrdering which we hereby contribute to the
>>OJB community, because other users seem to have similar problems.
>>
>>To use this class, the private method reorder() in class
>>org.ojb.odmg.ObjectEnvelopeTable must be replaced with:
>>
>>private void reorder()
>>{
>>  if (needsCommit)
>>  {
>>    ObjectEnvelopeOrdering ordering =
>>      new ObjectEnvelopeOrdering(transaction,mvOrderOfIds,mhtObjectEnvelopes);
>>    ordering.reorder();
>>    Identity[] newOrder = ordering.getOrdering();
>>    mvOrderOfIds.clear();
>>    for (int i = 0; i < newOrder.length; i++)
>>    {
>>      mvOrderOfIds.add(newOrder[i]);
>>    }
>>  }
>>}
>>
>>The ObjectEnvelopeOrdering class addresses the following problems we observed
>>with the original ordering algorithm:
>>
>>(1) the ordering is based on the modified state of the objects only; therefore
>>if a reference in object A is set to null, OJB does not see that before
>>modification A referenced an object B to be deleted.
>>
>>(2) 1:n and m:n collections are treated in the same way, although the
>>FK-location in the DB is quite different.
>>
>>(3) the ordering algorithm is 'greedy' in the sense that once an object
>>modification has been put into the ordered list, it will stay at this position
>>even if later constraints are found that would require to move it to a position
>>further down.
>>
>>(4) issue (3) is aggravated by the fact that the ordering does not take into
>>account the modification state of a referenced object. Therefore objects are
>>inserted into the ordered list even if there is no real need for ordering. Later
>>a real constraint me be encountered, but now the object is already frozen at its
>>new position.
>>
>>The ObjectEnvelopeOrdering class uses a graph-theoretical approach to order the
>>object envelopes (see the JavaDoc for details). Edges in this graph are inserted
>>only if there really is a need for ordering two object envelopes with respect to
>>each other - determining this need is based on the modification state of both
>>objects and the type of relation the two have to each other (1:1, 1:n, or m:n).
>>This addresses issues (2)-(4).
>>
>>Issue (1) is not addressed as as niftily: Since we did not want to change the
>>ObjectEnvelope class, we opted for a heuristic solution, where 'potential'
>>relations between two objects are taken into account based on the class type of
>>a reference.
>>
>>Test results:
>>After using the ObjectEnvelopeOrdering class we were able to remove all flush
>>statements from our application without any test case failing. The results of
>>the JUnit tests of OJB did not change either (some fail before and after the
>>change), with one exception:
>>org.apache.ojb.broker.sequence.NativeIdentifierTest.testReferenceInsertUpdateODMG.
>>Before our change, this test failed with a failed assertion, after our change it
>>now causes an FK violation error. Looking at the test code, I cannot see how the
>>FK error could be avoided, because there are two tables with FKs referencing
>>each other and the test attempts to insert two objects with references to each
>>other in a single transaction. As far as I can see, there is no order of INSERT
>>statements that could avoid the FK error.
>>
>>Performance:
>>The ordering process implemented by the ObjectEnvelopeOrdering class is
>>certainly slower than the original recursive ordering. This is mainly due to
>>the need of addressing issue (1). In our real application scenario, however, we
>>do not notice any perfomance degradation.
>>
>>AFAIK the OJB mailing list does not accept attachements, therefore I am posting
>>the class code inline. If anyone knows a better way to submit the code without
>>distortion due to line breaks, please let me know.
>>
>>We would be happy if the class would make it into the 'official' OJB. In any
>>case feel free to use it if it suits you. Of course the usual disclaimer apply
>>(no warranty of any kind...)
>>
>>Gerhard
>>
>>-------------------------------
>>
>>package org.apache.ojb.odmg;
>>
>>import java.util.ArrayList;
>>import java.util.Collection;
>>import java.util.HashMap;
>>import java.util.Iterator;
>>import java.util.List;
>>import java.util.Map;
>>
>>import org.apache.ojb.broker.Identity;
>>import org.apache.ojb.broker.OJBRuntimeException;
>>import org.apache.ojb.broker.PersistenceBroker;
>>import org.apache.ojb.broker.core.proxy.ProxyHelper;
>>import org.apache.ojb.broker.metadata.ClassDescriptor;
>>import org.apache.ojb.broker.metadata.CollectionDescriptor;
>>import org.apache.ojb.broker.metadata.ObjectReferenceDescriptor;
>>import org.apache.ojb.broker.util.logging.Logger;
>>import org.apache.ojb.broker.util.logging.LoggerFactory;
>>import org.apache.ojb.odmg.states.ModificationState;
>>
>>/**
>> * <p>Implements an algorithm for reordering the object envelopes of a pending
>> * transaction to minimized the probability of foreign key constraint
>> * violations.</p>
>> *
>> * <p>The algorithm is based on a graph theoretical approach: Each object
>> * envelope is represented by a vertex in a graph. Each possible constraint
>> * on the order of database operations is represented by a directed edge
>> * in this graph, in which the initial vertex represents the object envelope
>> * to be sent to the database first and the terminal index represents the
>> * object envelope that might cause a FK violation if the initial vertex
>> * has not been sent to the database before.</p>
>> *
>> * <p>Additionally the edges in this graph are weighted. This is necessary
>> * because the object envelopes provide only information on the relation
>> * between objects <strong>after</strong> the transaction. FK violations,
>> * however, can also occur due to relations that existed <strong>before</strong>
>> * the transaction. Therefore the algorithm also considers potential relations
>> * between objects due to the fact that an object is of a class that is
>> * the item class of a object or collection reference of another object.
>> * Graph edges representing such potential relationships receive a lower
>> * weight than edges representing concrete relationships that exist in the
>> * current state of the object model.</p>
>> *
>> * <p>Once all graph edges have been established, the algorithm proceeds as
>> * follows:</p>
>> * <ol>
>> *  <li>Iterate through all vertices and sum up the weight of all incoming
>> *      edges (i.e. those edges whose terminal vertex is the current
>>vertex).</li>
>> *  <li>Find the minimum value of this weight sums (ideally this minimum is
>>zero,
>> *      meaning that there are object envelopes that can be sent to the
>> *      database without risking FK violations)<il>
>> *  <li>Add all vertices with a weight sum that is equal to this minimum to
the
>> *      reordered sequence of object envelopes and remove the vertices
>> *      and all connected edges from the graph.</li>
>> *  <li>If there are vertices left, repeat steps (1) through (3), otherwise
>> *      we are done.
>> * </ol>
>> *
>> * @author  Gerhard Grosse
>> * @version $Id: ObjectEnvelopeOrdering.java,v 1.1 2004/11/18 12:25:28 grosse
>>Exp $
>> * @since   Nov 15, 2004
>> */
>>public class ObjectEnvelopeOrdering
>>{
>>    private static final int CONCRETE_EDGE_WEIGHT = 2;
>>    private static final int POTENTIAL_EDGE_WEIGHT = 1;
>>
>>    private static Logger log =
>>        LoggerFactory.getLogger(ObjectEnvelopeOrdering.class);
>>
>>    private List originalOrder;
>>    private Map envelopes;
>>    private TransactionImpl transaction;
>>
>>    private Vertex[] vertices;
>>    private Map edgeMap;
>>
>>    private int newOrderIndex;
>>    private Identity[] newOrder;
>>
>>    /**
>>     * Creates an object envelope ordering based on an original ordering
>>     * of Identity objects and an Identity-&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
> 
> 

---------------------------------------------------------------------
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