001 //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.3_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 }