Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / QueryRewriting / RewritingProcessor.cs / 1305376 / RewritingProcessor.cs
//---------------------------------------------------------------------- //// Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System; using System.Diagnostics; using System.Collections.Generic; using System.Text; namespace System.Data.Mapping.ViewGeneration.QueryRewriting { internal abstract class TileProcessor{ internal abstract bool IsEmpty(T_Tile tile); internal abstract T_Tile Union(T_Tile a, T_Tile b); internal abstract T_Tile Join(T_Tile a, T_Tile b); internal abstract T_Tile AntiSemiJoin(T_Tile a, T_Tile b); internal abstract T_Tile GetArg1(T_Tile tile); internal abstract T_Tile GetArg2(T_Tile tile); internal abstract TileOpKind GetOpKind(T_Tile tile); } internal class RewritingProcessor : TileProcessor where T_Tile : class { public double PERMUTE_FRACTION = 0.0; public int MIN_PERMUTATIONS = 0; public int MAX_PERMUTATIONS = 0; public bool REORDER_VIEWS = false; private int m_numSATChecks; private int m_numIntersection; private int m_numDifference; private int m_numUnion; private int m_numErrors; private TileProcessor m_tileProcessor; public RewritingProcessor(TileProcessor tileProcessor) { m_tileProcessor = tileProcessor; } internal TileProcessor TileProcessor { get { return m_tileProcessor; } } public void GetStatistics(out int numSATChecks, out int numIntersection, out int numUnion, out int numDifference, out int numErrors) { numSATChecks = m_numSATChecks; numIntersection = m_numIntersection; numUnion = m_numUnion; numDifference = m_numDifference; numErrors = m_numErrors; } public void PrintStatistics() { Console.WriteLine("{0} containment checks, {4} set operations ({1} intersections + {2} unions + {3} differences)", m_numSATChecks, m_numIntersection, m_numUnion, m_numDifference, m_numIntersection + m_numUnion + m_numDifference); Console.WriteLine("{0} errors", m_numErrors); } internal override T_Tile GetArg1(T_Tile tile) { return m_tileProcessor.GetArg1(tile); } internal override T_Tile GetArg2(T_Tile tile) { return m_tileProcessor.GetArg2(tile); } internal override TileOpKind GetOpKind(T_Tile tile) { return m_tileProcessor.GetOpKind(tile); } internal override bool IsEmpty(T_Tile a) { m_numSATChecks++; return m_tileProcessor.IsEmpty(a); } public bool IsDisjointFrom(T_Tile a, T_Tile b) { return m_tileProcessor.IsEmpty(Join(a, b)); } internal bool IsContainedIn(T_Tile a, T_Tile b) { T_Tile difference = AntiSemiJoin(a, b); return IsEmpty(difference); } internal bool IsEquivalentTo(T_Tile a, T_Tile b) { bool aInB = IsContainedIn(a, b); bool bInA = IsContainedIn(b, a); return aInB && bInA; } internal override T_Tile Union(T_Tile a, T_Tile b) { m_numUnion++; return m_tileProcessor.Union(a, b); } internal override T_Tile Join(T_Tile a, T_Tile b) { if (a == null) { return b; } m_numIntersection++; return m_tileProcessor.Join(a, b); } internal override T_Tile AntiSemiJoin(T_Tile a, T_Tile b) { m_numDifference++; return m_tileProcessor.AntiSemiJoin(a, b); } public void AddError() { m_numErrors++; } public int CountOperators(T_Tile query) { int count = 0; if (query != null) { if (GetOpKind(query) != TileOpKind.Named) { count++; count += CountOperators(GetArg1(query)); count += CountOperators(GetArg2(query)); } } return count; } public int CountViews(T_Tile query) { HashSet views = new HashSet (); GatherViews(query, views); return views.Count; } public void GatherViews(T_Tile rewriting, HashSet views) { if (rewriting != null) { if (GetOpKind(rewriting) == TileOpKind.Named) { views.Add(rewriting); } else { GatherViews(GetArg1(rewriting), views); GatherViews(GetArg2(rewriting), views); } } } public static IEnumerable AllButOne (IEnumerable list, int toSkipPosition) { int valuePosition = 0; foreach (T value in list) { if (valuePosition++ != toSkipPosition) { yield return value; } } } public static IEnumerable Concat (T value, IEnumerable rest) { yield return value; foreach (T restValue in rest) { yield return restValue; } } public static IEnumerable > Permute (IEnumerable list) { IEnumerable rest = null; int valuePosition = 0; foreach (T value in list) { rest = AllButOne (list, valuePosition++); foreach (IEnumerable restPermutation in Permute (rest)) { yield return Concat (value, restPermutation); } } if (rest == null) { yield return list; // list is empty enumeration } } static Random rnd = new Random(1507); public static List RandomPermutation (IEnumerable input) { List output = new List (input); for (int i = 0; i < output.Count; i++) { int j = rnd.Next(output.Count); T tmp = output[i]; output[i] = output[j]; output[j] = tmp; } return output; } public static IEnumerable Reverse (IEnumerable input, HashSet filter) { List output = new List (input); output.Reverse(); foreach (T t in output) { if (filter.Contains(t)) { yield return t; } } } public bool RewriteQuery(T_Tile toFill, T_Tile toAvoid, IEnumerable views, out T_Tile rewriting) { if (RewriteQueryOnce(toFill, toAvoid, views, out rewriting)) { HashSet usedViews = new HashSet (); GatherViews(rewriting, usedViews); int opCount = CountOperators(rewriting); // try several permutations of views, pick one with fewer operators T_Tile newRewriting; int permuteTries = 0; int numPermutations = Math.Min(MAX_PERMUTATIONS, Math.Max(MIN_PERMUTATIONS, (int)(usedViews.Count * PERMUTE_FRACTION))); while (permuteTries++ < numPermutations) { IEnumerable permutedViews; if (permuteTries == 1) { permutedViews = Reverse(views, usedViews); } else { permutedViews = RandomPermutation(usedViews); // Tradeoff: views vs. usedViews! } bool succeeded = RewriteQueryOnce(toFill, toAvoid, permutedViews, out newRewriting); Debug.Assert(succeeded); int newOpCount = CountOperators(newRewriting); if (newOpCount < opCount) { opCount = newOpCount; rewriting = newRewriting; } HashSet newUsedViews = new HashSet (); GatherViews(newRewriting, newUsedViews); usedViews = newUsedViews; // can only be fewer! } return true; } return false; } public bool RewriteQueryOnce(T_Tile toFill, T_Tile toAvoid, IEnumerable views, out T_Tile rewriting) { List viewList = new List (views); return RewritingPass .RewriteQuery(toFill, toAvoid, out rewriting, viewList, this); } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. //---------------------------------------------------------------------- // // Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System; using System.Diagnostics; using System.Collections.Generic; using System.Text; namespace System.Data.Mapping.ViewGeneration.QueryRewriting { internal abstract class TileProcessor{ internal abstract bool IsEmpty(T_Tile tile); internal abstract T_Tile Union(T_Tile a, T_Tile b); internal abstract T_Tile Join(T_Tile a, T_Tile b); internal abstract T_Tile AntiSemiJoin(T_Tile a, T_Tile b); internal abstract T_Tile GetArg1(T_Tile tile); internal abstract T_Tile GetArg2(T_Tile tile); internal abstract TileOpKind GetOpKind(T_Tile tile); } internal class RewritingProcessor : TileProcessor where T_Tile : class { public double PERMUTE_FRACTION = 0.0; public int MIN_PERMUTATIONS = 0; public int MAX_PERMUTATIONS = 0; public bool REORDER_VIEWS = false; private int m_numSATChecks; private int m_numIntersection; private int m_numDifference; private int m_numUnion; private int m_numErrors; private TileProcessor m_tileProcessor; public RewritingProcessor(TileProcessor tileProcessor) { m_tileProcessor = tileProcessor; } internal TileProcessor TileProcessor { get { return m_tileProcessor; } } public void GetStatistics(out int numSATChecks, out int numIntersection, out int numUnion, out int numDifference, out int numErrors) { numSATChecks = m_numSATChecks; numIntersection = m_numIntersection; numUnion = m_numUnion; numDifference = m_numDifference; numErrors = m_numErrors; } public void PrintStatistics() { Console.WriteLine("{0} containment checks, {4} set operations ({1} intersections + {2} unions + {3} differences)", m_numSATChecks, m_numIntersection, m_numUnion, m_numDifference, m_numIntersection + m_numUnion + m_numDifference); Console.WriteLine("{0} errors", m_numErrors); } internal override T_Tile GetArg1(T_Tile tile) { return m_tileProcessor.GetArg1(tile); } internal override T_Tile GetArg2(T_Tile tile) { return m_tileProcessor.GetArg2(tile); } internal override TileOpKind GetOpKind(T_Tile tile) { return m_tileProcessor.GetOpKind(tile); } internal override bool IsEmpty(T_Tile a) { m_numSATChecks++; return m_tileProcessor.IsEmpty(a); } public bool IsDisjointFrom(T_Tile a, T_Tile b) { return m_tileProcessor.IsEmpty(Join(a, b)); } internal bool IsContainedIn(T_Tile a, T_Tile b) { T_Tile difference = AntiSemiJoin(a, b); return IsEmpty(difference); } internal bool IsEquivalentTo(T_Tile a, T_Tile b) { bool aInB = IsContainedIn(a, b); bool bInA = IsContainedIn(b, a); return aInB && bInA; } internal override T_Tile Union(T_Tile a, T_Tile b) { m_numUnion++; return m_tileProcessor.Union(a, b); } internal override T_Tile Join(T_Tile a, T_Tile b) { if (a == null) { return b; } m_numIntersection++; return m_tileProcessor.Join(a, b); } internal override T_Tile AntiSemiJoin(T_Tile a, T_Tile b) { m_numDifference++; return m_tileProcessor.AntiSemiJoin(a, b); } public void AddError() { m_numErrors++; } public int CountOperators(T_Tile query) { int count = 0; if (query != null) { if (GetOpKind(query) != TileOpKind.Named) { count++; count += CountOperators(GetArg1(query)); count += CountOperators(GetArg2(query)); } } return count; } public int CountViews(T_Tile query) { HashSet views = new HashSet (); GatherViews(query, views); return views.Count; } public void GatherViews(T_Tile rewriting, HashSet views) { if (rewriting != null) { if (GetOpKind(rewriting) == TileOpKind.Named) { views.Add(rewriting); } else { GatherViews(GetArg1(rewriting), views); GatherViews(GetArg2(rewriting), views); } } } public static IEnumerable AllButOne (IEnumerable list, int toSkipPosition) { int valuePosition = 0; foreach (T value in list) { if (valuePosition++ != toSkipPosition) { yield return value; } } } public static IEnumerable Concat (T value, IEnumerable rest) { yield return value; foreach (T restValue in rest) { yield return restValue; } } public static IEnumerable > Permute (IEnumerable list) { IEnumerable rest = null; int valuePosition = 0; foreach (T value in list) { rest = AllButOne (list, valuePosition++); foreach (IEnumerable restPermutation in Permute (rest)) { yield return Concat (value, restPermutation); } } if (rest == null) { yield return list; // list is empty enumeration } } static Random rnd = new Random(1507); public static List RandomPermutation (IEnumerable input) { List output = new List (input); for (int i = 0; i < output.Count; i++) { int j = rnd.Next(output.Count); T tmp = output[i]; output[i] = output[j]; output[j] = tmp; } return output; } public static IEnumerable Reverse (IEnumerable input, HashSet filter) { List output = new List (input); output.Reverse(); foreach (T t in output) { if (filter.Contains(t)) { yield return t; } } } public bool RewriteQuery(T_Tile toFill, T_Tile toAvoid, IEnumerable views, out T_Tile rewriting) { if (RewriteQueryOnce(toFill, toAvoid, views, out rewriting)) { HashSet usedViews = new HashSet (); GatherViews(rewriting, usedViews); int opCount = CountOperators(rewriting); // try several permutations of views, pick one with fewer operators T_Tile newRewriting; int permuteTries = 0; int numPermutations = Math.Min(MAX_PERMUTATIONS, Math.Max(MIN_PERMUTATIONS, (int)(usedViews.Count * PERMUTE_FRACTION))); while (permuteTries++ < numPermutations) { IEnumerable permutedViews; if (permuteTries == 1) { permutedViews = Reverse(views, usedViews); } else { permutedViews = RandomPermutation(usedViews); // Tradeoff: views vs. usedViews! } bool succeeded = RewriteQueryOnce(toFill, toAvoid, permutedViews, out newRewriting); Debug.Assert(succeeded); int newOpCount = CountOperators(newRewriting); if (newOpCount < opCount) { opCount = newOpCount; rewriting = newRewriting; } HashSet newUsedViews = new HashSet (); GatherViews(newRewriting, newUsedViews); usedViews = newUsedViews; // can only be fewer! } return true; } return false; } public bool RewriteQueryOnce(T_Tile toFill, T_Tile toAvoid, IEnumerable views, out T_Tile rewriting) { List viewList = new List (views); return RewritingPass .RewriteQuery(toFill, toAvoid, out rewriting, viewList, this); } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ConfigsHelper.cs
- WbmpConverter.cs
- Part.cs
- log.cs
- RecognizedAudio.cs
- DecoderBestFitFallback.cs
- __Filters.cs
- StringFreezingAttribute.cs
- MarkupCompiler.cs
- DbDataSourceEnumerator.cs
- SpecularMaterial.cs
- ValidationErrorEventArgs.cs
- ToolStripOverflow.cs
- SchemaManager.cs
- GatewayDefinition.cs
- TrackingDataItem.cs
- ObjectItemAssemblyLoader.cs
- InstanceKey.cs
- SessionState.cs
- AutoResetEvent.cs
- SchemaImporterExtensionElementCollection.cs
- SignatureTargetIdManager.cs
- QueryCreatedEventArgs.cs
- StorageEndPropertyMapping.cs
- TraceContext.cs
- StringStorage.cs
- XmlCharType.cs
- AddDataControlFieldDialog.cs
- EventSourceCreationData.cs
- TagMapCollection.cs
- ExpressionEditor.cs
- SystemColors.cs
- Update.cs
- OutputCacheProfile.cs
- DataGridColumn.cs
- BadImageFormatException.cs
- SafeHGlobalHandleCritical.cs
- Expander.cs
- HandleCollector.cs
- GraphicsPathIterator.cs
- DataGridViewCellConverter.cs
- DataGridViewComboBoxColumn.cs
- SafeRightsManagementHandle.cs
- SHA1.cs
- PackagingUtilities.cs
- BitStack.cs
- RbTree.cs
- ConsoleCancelEventArgs.cs
- SystemKeyConverter.cs
- CustomErrorCollection.cs
- NullReferenceException.cs
- CanonicalXml.cs
- DBConcurrencyException.cs
- ImpersonateTokenRef.cs
- AdCreatedEventArgs.cs
- FormViewDesigner.cs
- DetailsViewDesigner.cs
- RequestResponse.cs
- Normalization.cs
- Conditional.cs
- ForeignKeyConstraint.cs
- NavigationPropertyEmitter.cs
- ContextInformation.cs
- CharacterHit.cs
- ThousandthOfEmRealPoints.cs
- PipeStream.cs
- Inflater.cs
- HandlerFactoryCache.cs
- DesignerActionUI.cs
- SQLInt32Storage.cs
- Image.cs
- XmlIterators.cs
- RecipientInfo.cs
- UnauthorizedAccessException.cs
- ApplicationSecurityInfo.cs
- XmlWriterDelegator.cs
- XmlSerializerVersionAttribute.cs
- ExtensionFile.cs
- HwndSubclass.cs
- ComponentDispatcher.cs
- ImportCatalogPart.cs
- PeerResolverBindingElement.cs
- RuleConditionDialog.cs
- XmlnsDictionary.cs
- QueueSurrogate.cs
- _NegotiateClient.cs
- WebPartCloseVerb.cs
- XmlSchemaCompilationSettings.cs
- ButtonColumn.cs
- PropertyDescriptorComparer.cs
- SQLBinary.cs
- RemoveStoryboard.cs
- ClosureBinding.cs
- HtmlInputReset.cs
- CachingHintValidation.cs
- MessageHeaderInfoTraceRecord.cs
- AnnotationHelper.cs
- RecordBuilder.cs
- ValueUtilsSmi.cs
- UnsafeNativeMethods.cs