rqloptimizer.java

这是外国一个开源推理机

/*  Sesame - Storage and Querying architecture for RDF and RDF Schema
 *  Copyright (C) 2001-2005 Aduna
 *
 *  Contact: 
 *  	Aduna
 *  	Prinses Julianaplein 14 b
 *  	3817 CS Amersfoort
 *  	The Netherlands
 *  	tel. [phone]
 *  	fax. [phone]
 *
 *  	http://aduna.biz/
 *  	http://www.openrdf.org/
 *  
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package org.openrdf.sesame.query.rql;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.openrdf.util.log.ThreadLog;

import org.openrdf.model.Value;
import org.openrdf.model.impl.LiteralImpl;

import org.openrdf.sesame.query.rql.model.And;
import org.openrdf.sesame.query.rql.model.BooleanConstant;
import org.openrdf.sesame.query.rql.model.BooleanQuery;
import org.openrdf.sesame.query.rql.model.ClassSelector;
import org.openrdf.sesame.query.rql.model.CompareTo;
import org.openrdf.sesame.query.rql.model.DataPathSelector;
import org.openrdf.sesame.query.rql.model.DomainSelector;
import org.openrdf.sesame.query.rql.model.In;
import org.openrdf.sesame.query.rql.model.InstanceSelector;
import org.openrdf.sesame.query.rql.model.IntegerConstant;
import org.openrdf.sesame.query.rql.model.PropertySelector;
import org.openrdf.sesame.query.rql.model.Query;
import org.openrdf.sesame.query.rql.model.RangeSelector;
import org.openrdf.sesame.query.rql.model.RealConstant;
import org.openrdf.sesame.query.rql.model.ResourceQuery;
import org.openrdf.sesame.query.rql.model.Selector;
import org.openrdf.sesame.query.rql.model.SetQuery;
import org.openrdf.sesame.query.rql.model.SfwQuery;
import org.openrdf.sesame.query.rql.model.StringConstant;
import org.openrdf.sesame.query.rql.model.URI;
import org.openrdf.sesame.query.rql.model.UnknownSelector;
import org.openrdf.sesame.query.rql.model.Var;

public class RqlOptimizer {

	// Static class
	private RqlOptimizer() {
	}

	public static Query optimize(Query query) {
		if (query instanceof SfwQuery) {
			_optimizeSfwQuery((SfwQuery)query);
		}
		else if (query instanceof SetQuery) {
			// Both arguments of SetQuery's are SfwQuery's
			SetQuery setQuery = (SetQuery)query;

			_optimizeSfwQuery(setQuery.getArg1());
			_optimizeSfwQuery(setQuery.getArg2());
		}

		return query;
	}

	private static void _optimizeSfwQuery(SfwQuery sfwQuery) {
		BooleanQuery where = sfwQuery.getWherePart();
		if (where != null) {
			// Make all explicit joins implicit
			where = _handleExplicitJoins(where);

			// Find and remove values assigned explicitly to variables
			where = _findAndRemoveExplicitAssigns(where);

			where = _optimizeNestedSfwQueries(where);

			// Update the where-part
			sfwQuery.setWherePart(where);
		}

		// Reorder the selectors
		_reorderSelectors(sfwQuery);
	}

	private static BooleanQuery _handleExplicitJoins(BooleanQuery where) {
		HashMap varMap = new HashMap();
		BooleanQuery newWhere = _findAndRemoveExplicitJoins(where, varMap);

		// Get unique lists from varMap:
		HashSet varSet = new HashSet(varMap.values());
		Iterator listIter = varSet.iterator();
		while (listIter.hasNext()) {
			List varList = (List)listIter.next();

			// Make the first var the leader of the rest
			Iterator varIter = varList.iterator();
			Var leader = (Var)varIter.next();
			while (varIter.hasNext()) {
				Var v = (Var)varIter.next();
				v.setLeader(leader);
			}
		}

		return newWhere;
	}

	private static BooleanQuery _findAndRemoveExplicitJoins(
		BooleanQuery bQuery, Map varMap)
	{
		if (bQuery instanceof And) {
			And and = (And)bQuery;
			BooleanQuery newArg1 = _findAndRemoveExplicitJoins(and.getArg1(), varMap);
			BooleanQuery newArg2 = _findAndRemoveExplicitJoins(and.getArg2(), varMap);
			if (newArg1 == null && newArg2 == null) {
				// Both args are obsolete
				return null;
			}
			else if (newArg2 == null) {
				// newArg2 is obsolete
				return newArg1;
			}
			else if (newArg1 == null) {
				// newArg1 is obsolete
				return newArg2;
			}
			else {
				// Nothing was changed
				return and;
			}
		}
		else if (bQuery instanceof CompareTo) {
			CompareTo ct = (CompareTo)bQuery;
			if (ct.getOperator() == CompareTo.EQ) {
				ResourceQuery arg1 = ct.getArg1();
				ResourceQuery arg2 = ct.getArg2();

				if (arg1 instanceof Var && arg2 instanceof Var) {
					// Check whether the vars are already equal to other vars
					List varList1 = (List)varMap.get(arg1);
					List varList2 = (List)varMap.get(arg2);

					if (varList1 == null && varList2 == null) {
						// new comparison for both vars
						List varList = new ArrayList();
						varList.add(arg1);
						varList.add(arg2);
						varMap.put(arg1, varList);
						varMap.put(arg2, varList);
					}
					else if (varList2 == null) {
						// var1 already equal to some other var(s)
						varList1.add(arg2);
						varMap.put(arg2, varList1);
					}
					else if (varList1 == null) {
						// var2 already equal to some other var(s)
						varList2.add(arg1);
						varMap.put(arg1, varList2);
					}
					else if (varList1 != varList2) {
						// Both vars already equal to some other vars
						varList1.addAll(varList2);

						// Replace varList2 by varList1:
						Iterator iter = varList2.iterator();
						while (iter.hasNext()) {
							Object o = iter.next();
							varMap.put(o, varList1);
						}
					}
					// else { vars were already equal }

					return null;
				}
			}
		}

		return bQuery;
	}

	private static BooleanQuery _findAndRemoveExplicitAssigns(BooleanQuery bQuery) {
		if (bQuery instanceof And) {
			And and = (And)bQuery;
			BooleanQuery newArg1 = _findAndRemoveExplicitAssigns(and.getArg1());
			BooleanQuery newArg2 = _findAndRemoveExplicitAssigns(and.getArg2());
			if (newArg1 == null && newArg2 == null) {
				// Both args are obsolete
				return null;
			}
			else if (newArg2 == null) {
				// newArg2 is obsolete
				return newArg1;
			}
			else if (newArg1 == null) {
				// newArg1 is obsolete
				return newArg2;
			}
			else {
				// Nothing was changed
				return and;
			}
		}
		else if (bQuery instanceof CompareTo) {
			CompareTo ct = (CompareTo)bQuery;
			if (ct.getOperator() == CompareTo.EQ) {
				ResourceQuery arg1 = ct.getArg1();
				ResourceQuery arg2 = ct.getArg2();

				if (arg1 instanceof Var || arg2 instanceof Var) {
					Var varArg = null;
					ResourceQuery valueArg = null;
					Value value = null;

					// Check which argument is the variable
					if (arg1 instanceof Var) {
						varArg = (Var)arg1;
						valueArg = arg2;
					}
					else {
						varArg = (Var)arg2;
						valueArg = arg1;
					}

					if (valueArg instanceof URI) {
						value = ((URI)valueArg).getValue();
					}
					else if (valueArg instanceof StringConstant) {
						value = new LiteralImpl(
								((StringConstant)valueArg).getValue());
					}
					else if (valueArg instanceof IntegerConstant) {
						int i = ((IntegerConstant)valueArg).getValue();
						value = new LiteralImpl( String.valueOf(i) );
					}
					else if (valueArg instanceof RealConstant) {
						float f = ((RealConstant)valueArg).getValue();
						value = new LiteralImpl( String.valueOf(f) );
					}

					if (value != null) {
						// Value can be set on the variable, but first we need
						// to check if it doesn't have a value already.

						Value otherVal = varArg.getValue();
						if (otherVal != null) {
							// The two values should be equal, or the query
							// will never have any results.
							if (value.equals(otherVal)) {
								return null;
							}
							else {
								return new BooleanConstant(false);
							}
						}
						else {
							varArg.setValue(value);
							return null;
						}
					}
				}
			}
		}

		return bQuery;
	}

	// Optimizes any SfwQuery's that are used as right operand for in operators.
	private static BooleanQuery _optimizeNestedSfwQueries(BooleanQuery bQuery) {
		if (bQuery instanceof And) {
			And and = (And)bQuery;

			BooleanQuery newArg1 = _optimizeNestedSfwQueries(and.getArg1());
			BooleanQuery newArg2 = _optimizeNestedSfwQueries(and.getArg2());

			if (newArg1 == null && newArg2 == null) {
				// Both args are obsolete
				return null;
			}
			else if (newArg2 == null) {
				// newArg2 is obsolete
				return newArg1;
			}
			else if (newArg1 == null) {
				// newArg1 is obsolete
				return newArg2;
			}
			else {
				// Nothing was changed
				return and;
			}
		}
		else if (bQuery instanceof In) {
			In in = (In)bQuery;
			if (in.getArg2() instanceof SfwQuery) {
				_optimizeSfwQuery( (SfwQuery)in.getArg2() );
			}
		}

		return bQuery;
	}

	private static void _reorderSelectors(SfwQuery sfwQuery) {
		List selectorList = sfwQuery.getFromPart();

		// Crude reordering according to avg cost of selectors.
		// Selectors are ordered according to their type in the
		// following order:
		//     1: PropertySelector
		//     2: DomainSelector
		//     3: RangeSelector
		//     4: DataPathSelector
		//     5: UnknownSelector
		//     6: InstanceSelector
		//     7: ClassSelector

		List propertySelList = new ArrayList();
		List domainSelList = new ArrayList();
		List rangeSelList = new ArrayList();
		List dataPathSelList = new ArrayList();
		List unknownSelList = new ArrayList();
		List instanceSelList = new ArrayList();
		List classSelList = new ArrayList();
		List restSelList = new ArrayList(); // should be empty

		int selectorCount = selectorList.size();
		for (int i = 0; i < selectorCount; i++) {
			Selector selector = (Selector)selectorList.get(i);

			if (selector instanceof PropertySelector) {
				propertySelList.add(selector);
			}
			else if (selector instanceof DomainSelector) {
				domainSelList.add(selector);
			}
			else if (selector instanceof RangeSelector) {
				rangeSelList.add(selector);
			}
			else if (selector instanceof DataPathSelector) {
				dataPathSelList.add(selector);
			}
			else if (selector instanceof UnknownSelector) {
				unknownSelList.add(selector);
			}
			else if (selector instanceof InstanceSelector) {
				instanceSelList.add(selector);
			}
			else if (selector instanceof ClassSelector) {
				classSelList.add(selector);
			}
			else {
				restSelList.add(selector);
				ThreadLog.warning("Found an unknown selector: " +
					selector.getClass().getName());
			}
		}

		// Further reorder the DataPathSelectors
		dataPathSelList = _reorderDataPathSelectors(dataPathSelList);

		List newSelectorList = new ArrayList();
		newSelectorList.addAll(propertySelList);
		newSelectorList.addAll(domainSelList);
		newSelectorList.addAll(rangeSelList);
		newSelectorList.addAll(dataPathSelList);
		newSelectorList.addAll(unknownSelList);
		newSelectorList.addAll(instanceSelList);
		newSelectorList.addAll(classSelList);
		newSelectorList.addAll(restSelList);

		sfwQuery.setFromPart(newSelectorList);
	}

	private static List _reorderDataPathSelectors(List dataPathSelList) {
		// DataPathSelectors are ordered such that the selectors having
		// the most _fixed_ variables are evaluated first.

		List zeroVarsList = new ArrayList();
		List oneVarList = new ArrayList();
		List twoVarsList = new ArrayList();

		int selectorCount = dataPathSelList.size();
		for (int i = 0; i < selectorCount; i++) {
			DataPathSelector dps = (DataPathSelector)dataPathSelList.get(i);

			int varCount = 0;

			if (!dps.getSourceVar().hasValue()) {
				varCount++;
			}
			if (!dps.getTargetVar().hasValue()) {
				varCount++;
			}

			switch (varCount) {
				case 0: zeroVarsList.add(dps); break;
				case 1: oneVarList.add(dps); break;
				case 2: twoVarsList.add(dps); break;
			}
		}

		List result = new ArrayList();
		result.addAll(zeroVarsList);
		result.addAll(oneVarList);
		result.addAll(twoVarsList);

		return result;
	}
}