    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_testing/src/org/deegree/io/datastore/sql/transaction/delete/TableGraph.java $
    002    /*----------------------------------------------------------------------------
    003     This file is part of deegree, http://deegree.org/
    004     Copyright (C) 2001-2009 by:
    005       Department of Geography, University of Bonn
    006     and
    007       lat/lon GmbH
    008
    009     This library is free software; you can redistribute it and/or modify it under
    010     the terms of the GNU Lesser General Public License as published by the Free
    011     Software Foundation; either version 2.1 of the License, or (at your option)
    012     any later version.
    013     This library is distributed in the hope that it will be useful, but WITHOUT
    014     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    015     FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
    016     details.
    017     You should have received a copy of the GNU Lesser General Public License
    018     along with this library; if not, write to the Free Software Foundation, Inc.,
    019     59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
    020
    021     Contact information:
    022
    023     lat/lon GmbH
    024     Aennchenstr. 19, 53177 Bonn
    025     Germany
    026     http://lat-lon.de/
    027
    028     Department of Geography, University of Bonn
    029     Prof. Dr. Klaus Greve
    030     Postfach 1147, 53001 Bonn
    031     Germany
    032     http://www.geographie.uni-bonn.de/deegree/
    033
    034     e-mail: info@deegree.org
    035    ----------------------------------------------------------------------------*/
    036    package org.deegree.io.datastore.sql.transaction.delete;
    037
    038    import java.util.ArrayList;
    039    import java.util.HashMap;
    040    import java.util.HashSet;
    041    import java.util.List;
    042    import java.util.Map;
    043    import java.util.Set;
    044
    045    import org.deegree.framework.log.ILogger;
    046    import org.deegree.framework.log.LoggerFactory;
    047    import org.deegree.i18n.Messages;
    048    import org.deegree.io.datastore.DatastoreException;
    049    import org.deegree.io.datastore.FeatureId;
    050    import org.deegree.io.datastore.schema.MappedFeaturePropertyType;
    051    import org.deegree.io.datastore.schema.MappedFeatureType;
    052    import org.deegree.io.datastore.schema.MappedGeometryPropertyType;
    053    import org.deegree.io.datastore.schema.MappedPropertyType;
    054    import org.deegree.io.datastore.schema.MappedSimplePropertyType;
    055    import org.deegree.io.datastore.schema.TableRelation;
    056    import org.deegree.io.datastore.schema.TableRelation.FK_INFO;
    057    import org.deegree.model.feature.schema.PropertyType;
    058
    059    /**
    060     * Represents a delete operation on the relational (table) level. Contains explicit information on all table rows to be
    061     * removed from the database and their foreign key references.
    062     *
    063     * @see FeatureGraph
    064     *
    065     * @author <a href="mailto:schneider@lat-lon.de">Markus Schneider</a>
    066     * @author last edited by: $Author: mschneider $
    067     *
    068     * @version $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18. Jun 2009) $
    069     */
    070    class TableGraph {
    071
    072        private static final ILogger LOG = LoggerFactory.getLogger( TableGraph.class );
    073
    074        private DeleteHandler handler;
    075
    076        private List<TableNode> allNodes = new ArrayList<TableNode>();
    077
    078        private Map<FeatureId, TableNode> fidToNode = new HashMap<FeatureId, TableNode>();
    079
    080        private int rootFeatureCount = 0;
    081
    082        /**
    083         * Creates a new <code>DeleteGraph</code> instance from the given {@link FeatureGraph}.
    084         *
    085         * @param featureGraph
    086         * @param handler
    087         * @throws DatastoreException
    088         */
    089        TableGraph( FeatureGraph featureGraph, DeleteHandler handler ) throws DatastoreException {
    090
    091            this.handler = handler;
    092
    093            // add nodes for all deletable features
    094            for ( FeatureNode rootFeature : featureGraph.getRootNodes() ) {
    095                if ( rootFeature.isDeletable() ) {
    096                    add( rootFeature );
    097                    rootFeatureCount++;
    098                }
    099            }
    100
    101            // add connectivity information for all feature nodes
    102            for ( FeatureId fid : this.fidToNode.keySet() ) {
    103                addConnectivityInfo( fid, featureGraph );
    104            }
    105        }
    106
    107        /**
    108         * Returns the number of deletable root features.
    109         *
    110         * @return number of deletable root features.
    111         */
    112        int getDeletableRootFeatureCount() {
    113            return this.rootFeatureCount;
    114        }
    115
    116        /**
    117         * Adds a {@FeatureNode} and all it's descendant deletable subfeatures to the graph.
    118         *
    119         * @param featureNode
    120         */
    121        private boolean add( FeatureNode featureNode ) {
    122            if ( featureNode.isDeletable() ) {
    123                FeatureId fid = featureNode.getFid();
    124                if ( fidToNode.get( fid ) == null ) {
    125                    TableNode deleteNode = new TableNode( fid );
    126                    allNodes.add( deleteNode );
    127                    fidToNode.put( fid, deleteNode );
    128                    for ( FeatureNode subFeature : featureNode.getSubFeatures() ) {
    129                        add( subFeature );
    130                    }
    131                }
    132                return true;
    133            }
    134            return false;
    135        }
    136
    137        /**
    138         * Adds the connection information (sucessors / precedessors) for the given feature to the graph.
    139         *
    140         * @param fid
    141         * @param fGraph
    142         * @throws DatastoreException
    143         */
    144        private void addConnectivityInfo( FeatureId fid, FeatureGraph fGraph )
    145                                throws DatastoreException {
    146
    147            MappedFeatureType ft = fid.getFeatureType();
    148            PropertyType[] props = ft.getProperties();
    149            TableNode sourceNode = this.fidToNode.get( fid );
    150            for ( PropertyType pt : props ) {
    151                if ( pt instanceof MappedSimplePropertyType || pt instanceof MappedGeometryPropertyType ) {
    152                    TableRelation[] relations = ( (MappedPropertyType) pt ).getTableRelations();
    153                    if ( relations.length == 1 ) {
    154                        LOG.logDebug( "Adding simple/ geometry property '" + pt.getName() + "'..." );
    155                        List<TableNode> propNodes = this.handler.determinePropNodes( fid, relations[0] );
    156                        for ( TableNode node : propNodes ) {
    157                            add( sourceNode, node, relations[0] );
    158                        }
    159                    } else if ( relations.length > 1 ) {
    160                        String msg = Messages.getMessage( "DATASTORE_SQL_DELETE_UNSUPPORTED_JOIN" );
    161                        throw new DatastoreException( msg );
    162                    }
    163                    // if (relations.length == 0) property is deleted automatically
    164                } else if ( pt instanceof MappedFeaturePropertyType ) {
    165                    FeatureNode fNode = fGraph.getNode( fid );
    166                    List<FeatureId> subFeatureIds = fNode.getSubFeatureIds( (MappedFeaturePropertyType) pt );
    167                    for ( FeatureId subFid : subFeatureIds ) {
    168                        connect( fid, sourceNode, (MappedFeaturePropertyType) pt, fGraph.getNode( subFid ) );
    169                    }
    170                }
    171            }
    172        }
    173
    174        private void add( TableNode featureNode, TableNode propNode, TableRelation relation ) {
    175            if ( findNode( propNode ) != null ) {
    176                propNode = findNode( propNode );
    177            } else {
    178                allNodes.add( propNode );
    179            }
    180            if ( relation.getFKInfo() == FK_INFO.fkIsFromField ) {
    181                featureNode.connect( propNode );
    182                propNode.setDeleteVetoPossible();
    183            } else {
    184                propNode.connect( featureNode );
    185            }
    186        }
    187
    188        private void connect( FeatureId fid, TableNode sourceNode, MappedFeaturePropertyType pt, FeatureNode subFeature )
    189                                throws DatastoreException {
    190
    191            FeatureId subFid = subFeature.getFid();
    192            TableRelation[] relations = pt.getTableRelations();
    193
    194            if ( subFeature.isDeletable() ) {
    195                TableNode subFeatureNode = this.fidToNode.get( subFid );
    196                switch ( relations.length ) {
    197                case 1: {
    198                    TableRelation relation = relations[0];
    199                    if ( relation.getFKInfo() == FK_INFO.fkIsFromField ) {
    200                        sourceNode.connect( subFeatureNode );
    201                    } else {
    202                        subFeatureNode.connect( sourceNode );
    203                    }
    204                    break;
    205                }
    206                case 2: {
    207                    TableNode jtEntry = handler.determineJTNode( fid, subFid, relations[0], relations[1] );
    208                    this.allNodes.add( jtEntry );
    209                    if ( relations[0].getFKInfo() == FK_INFO.fkIsFromField ) {
    210                        sourceNode.connect( jtEntry );
    211                    } else {
    212                        jtEntry.connect( sourceNode );
    213                    }
    214                    if ( relations[1].getFKInfo() == FK_INFO.fkIsFromField ) {
    215                        jtEntry.connect( subFeatureNode );
    216                    } else {
    217                        subFeatureNode.connect( jtEntry );
    218                    }
    219                    break;
    220                }
    221                default: {
    222                    assert false;
    223                }
    224                }
    225            } else {
    226                if ( relations.length == 2 ) {
    227                    TableNode jtEntry = handler.determineJTNode( fid, subFid, relations[0], relations[1] );
    228                    this.allNodes.add( jtEntry );
    229                    if ( relations[0].getFKInfo() == FK_INFO.fkIsFromField ) {
    230                        sourceNode.connect( jtEntry );
    231                    } else {
    232                        jtEntry.connect( sourceNode );
    233                    }
    234                }
    235            }
    236        }
    237
    238        /**
    239         * Returns the {@link TableNode} that represents the specified feature instance.
    240         *
    241         * @param fid
    242         *            FeatureId of the feature instance
    243         * @return TableNode for the feature instance if it exists in the graph, null otherwise
    244         */
    245        TableNode findNode( FeatureId fid ) {
    246            return this.fidToNode.get( fid );
    247        }
    248
    249        /**
    250         * Returns the {@link TableNode} that represents the specified feature instance (given as a {@link TableNode}).
    251         *
    252         * @param newNode
    253         *            feature to look up
    254         * @return TableNode for the feature instance if it exists in the graph, null otherwise
    255         */
    256        TableNode findNode( TableNode newNode ) {
    257            for ( TableNode node : allNodes ) {
    258                if ( node.equals( newNode ) ) {
    259                    return node;
    260                }
    261            }
    262            return null;
    263        }
    264
    265        /**
    266         * Returns the nodes of the graph in topological order, i.e. they may be deleted in that order without violating any
    267         * foreign key constraints.
    268         * <p>
    269         * NOTE: If the foreign key constraints constitute a cycle, no topological order is possible and the initial order
    270         * (arbitrary) is returned.
    271         *
    272         * @return the nodes of the graph in topological order if no cycle is present, else in arbitrary order
    273         */
    274        List<TableNode> getDeletionOrder() {
    275            List<TableNode> orderedList = new ArrayList<TableNode>( allNodes.size() );
    276
    277            // key: node (table entry), value: number of open fk constraints
    278            Map<TableNode, Integer> preMap = new HashMap<TableNode, Integer>();
    279            // contains only nodes that have no open fk constraints
    280            List<TableNode> noPreNodes = new ArrayList<TableNode>();
    281            for ( TableNode node : allNodes ) {
    282                int preCount = node.getPreNodes().size();
    283                preMap.put( node, preCount );
    284                if ( preCount == 0 ) {
    285                    noPreNodes.add( node );
    286                }
    287            }
    288
    289            while ( !noPreNodes.isEmpty() ) {
    290                TableNode currentNode = noPreNodes.remove( noPreNodes.size() - 1 );
    291                orderedList.add( currentNode );
    292                for ( TableNode post : currentNode.getPostNodes() ) {
    293                    int preCount = preMap.get( post ) - 1;
    294                    preMap.put( post, preCount );
    295                    if ( preCount == 0 ) {
    296                        noPreNodes.add( post );
    297                    }
    298                }
    299            }
    300
    301            if ( orderedList.size() != allNodes.size() ) {
    302                String msg = "Cannot determine topological order: cycle in fk constraints. Deleting rows in arbitrary order.";
    303                LOG.logWarning( msg );
    304                orderedList.clear();
    305                orderedList.addAll( allNodes );
    306            }
    307            return orderedList;
    308        }
    309
    310        @Override
    311        public String toString() {
    312            StringBuffer sb = new StringBuffer();
    313            Set<TableNode> printedNodes = new HashSet<TableNode>();
    314
    315            for ( TableNode node : allNodes ) {
    316                sb.append( node.toString( "", printedNodes ) );
    317                sb.append( '\n' );
    318            }
    319            return sb.toString();
    320        }
    321    }