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