Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / QueryRewriting / RewritingProcessor.cs / 1 / RewritingProcessor.cs
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. 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.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- NativeMethodsOther.cs
- FixUpCollection.cs
- NeutralResourcesLanguageAttribute.cs
- SessionEndedEventArgs.cs
- SqlGenerator.cs
- input.cs
- AmbientProperties.cs
- DataGridPageChangedEventArgs.cs
- TiffBitmapEncoder.cs
- TableLayoutColumnStyleCollection.cs
- Path.cs
- NativeMethods.cs
- SchemaImporterExtensionsSection.cs
- LocationSectionRecord.cs
- SuppressMessageAttribute.cs
- FixUp.cs
- PointCollectionValueSerializer.cs
- SizeLimitedCache.cs
- UnmanagedMemoryStreamWrapper.cs
- WindowProviderWrapper.cs
- ConfigurationProperty.cs
- Positioning.cs
- BlurBitmapEffect.cs
- AssemblyCollection.cs
- SqlResolver.cs
- OleDbConnection.cs
- UdpDiscoveryEndpointProvider.cs
- Imaging.cs
- ThreadAbortException.cs
- ProfileSettingsCollection.cs
- TypedLocationWrapper.cs
- IntPtr.cs
- ExpressionPrefixAttribute.cs
- DataGridColumn.cs
- PasswordRecovery.cs
- XmlDesigner.cs
- HtmlObjectListAdapter.cs
- BidOverLoads.cs
- RoleBoolean.cs
- InkCanvasInnerCanvas.cs
- SimpleTypeResolver.cs
- DataGridViewDataConnection.cs
- TextSearch.cs
- ProbeDuplexCD1AsyncResult.cs
- InvokeMethod.cs
- Hex.cs
- ExpandButtonVisibilityConverter.cs
- TraceHandler.cs
- TreeNodeSelectionProcessor.cs
- DataContractSerializerSection.cs
- HtmlTextArea.cs
- CapiNative.cs
- DataViewSettingCollection.cs
- WeakKeyDictionary.cs
- BaseValidator.cs
- VectorAnimationBase.cs
- SpellerStatusTable.cs
- ListViewItem.cs
- DataServiceExpressionVisitor.cs
- Subtree.cs
- FirstMatchCodeGroup.cs
- AssertSection.cs
- SchemaInfo.cs
- EventMetadata.cs
- FixUpCollection.cs
- SystemColors.cs
- Point4D.cs
- DataGridItemEventArgs.cs
- InstanceDescriptor.cs
- DataGridViewToolTip.cs
- DataTableCollection.cs
- PowerStatus.cs
- GridViewEditEventArgs.cs
- SoapHelper.cs
- EntityReference.cs
- HandlerFactoryWrapper.cs
- RectValueSerializer.cs
- MessageSmuggler.cs
- DeflateInput.cs
- UserPreferenceChangedEventArgs.cs
- PriorityBindingExpression.cs
- PrintPageEvent.cs
- FilterableAttribute.cs
- ColorContextHelper.cs
- EndpointInfoCollection.cs
- LinkArea.cs
- XmlDomTextWriter.cs
- CodeValidator.cs
- BuildProvidersCompiler.cs
- GroupBoxAutomationPeer.cs
- DesignerActionService.cs
- LayoutInformation.cs
- StaticFileHandler.cs
- ConfigurationValidatorBase.cs
- ModuleElement.cs
- SqlDataSourceSelectingEventArgs.cs
- Convert.cs
- SqlUserDefinedTypeAttribute.cs
- WebExceptionStatus.cs
- XmlQueryContext.cs