db-ojb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian McCallister <bmccallis...@gmail.com>
Subject Re: Java class for ordering SQL statements in ODMG to avoid FK violations
Date Sun, 21 Nov 2004 15:06:48 GMT
I had an implementation based on commons-graph from
jakarta-commons-sandbox. I ripped it out as I am very uncomfortable
being dependent on a sandbox component for which none of us are a
contributor.

Right now the Dirty* stuff does a very bad sort (INSERT -> UPDATE ->
DELETE) which works as long as no inserts depend on each other, and
you don't use serializable transactions at the DB level (prone to
deadlocks). Not a good option.

-Brian

On Sun, 21 Nov 2004 10:26:35 +0100, Jakob Braeuchi <jbraeuchi@gmx.ch> wrote:
> hi brian,
> 
> it imports org.apache.ojb.odmg.states.ModificationState.
> do you already have an implementation of the sort ?
> 
> jakob
> 
> Brian McCallister schrieb:
> 
> 
> > Fantastic!
> >
> > I haven't looked closely at the code yet, but is it dependent (for
> > operation, not compile ;-) on ODMG classes? I need the exact same
> > topological sort for the object space transaction stuff (against PB)
> > in 1.1 =)
> >
> > Thank you!
> >
> > -Brian
> >
> > On Thu, 18 Nov 2004 14:06:48 +0100, Gerhard Grosse
> > <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
> 
>

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