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
- BitArray.cs
- HorizontalAlignConverter.cs
- DataGridViewColumnTypeEditor.cs
- WriteStateInfoBase.cs
- BindToObject.cs
- XPathExpr.cs
- Gdiplus.cs
- DataContractJsonSerializer.cs
- RemotingAttributes.cs
- SynchronizingStream.cs
- DefaultValueTypeConverter.cs
- XmlFormatWriterGenerator.cs
- DataGridViewColumnEventArgs.cs
- WindowShowOrOpenTracker.cs
- CommentAction.cs
- Setter.cs
- TextViewBase.cs
- ZipPackagePart.cs
- TriggerBase.cs
- NamespaceEmitter.cs
- ByeMessage11.cs
- ObjectDataSourceDisposingEventArgs.cs
- ModifiableIteratorCollection.cs
- HighlightComponent.cs
- SystemInformation.cs
- DescendantQuery.cs
- EnumMemberAttribute.cs
- TdsParserStateObject.cs
- EngineSite.cs
- ColorPalette.cs
- WindowsToolbar.cs
- ActivityMarkupSerializationProvider.cs
- Rotation3DAnimation.cs
- CaseInsensitiveComparer.cs
- CursorEditor.cs
- DataGridComboBoxColumn.cs
- StylusCollection.cs
- DynamicRendererThreadManager.cs
- UInt64Storage.cs
- TypePresenter.xaml.cs
- XmlParserContext.cs
- ConvertTextFrag.cs
- TextTreeNode.cs
- SpotLight.cs
- MenuScrollingVisibilityConverter.cs
- COSERVERINFO.cs
- SecurityHelper.cs
- SmtpFailedRecipientException.cs
- PrintPreviewDialog.cs
- ScalarType.cs
- GeometryValueSerializer.cs
- FixedSOMTableRow.cs
- RightsManagementEncryptionTransform.cs
- PointCollectionConverter.cs
- Documentation.cs
- FileAuthorizationModule.cs
- Missing.cs
- _Events.cs
- TargetControlTypeCache.cs
- EncodingInfo.cs
- FlatButtonAppearance.cs
- Composition.cs
- Helper.cs
- StateWorkerRequest.cs
- ListBoxItemWrapperAutomationPeer.cs
- WeakRefEnumerator.cs
- MeasureData.cs
- SettingsPropertyNotFoundException.cs
- ApplicationServiceManager.cs
- XmlReaderSettings.cs
- MessageBodyMemberAttribute.cs
- DeadCharTextComposition.cs
- Query.cs
- PageRequestManager.cs
- StringCollectionEditor.cs
- WindowsToolbarAsMenu.cs
- ISAPIWorkerRequest.cs
- HtmlInputSubmit.cs
- TripleDES.cs
- Size.cs
- TrackingDataItemValue.cs
- TransformPatternIdentifiers.cs
- ReadContentAsBinaryHelper.cs
- SchemaMapping.cs
- WeakEventManager.cs
- IgnoreFlushAndCloseStream.cs
- BooleanAnimationBase.cs
- TemplateField.cs
- ParagraphResult.cs
- ProgressBar.cs
- ComponentCollection.cs
- TextEditorDragDrop.cs
- HttpSessionStateWrapper.cs
- WS2007FederationHttpBindingElement.cs
- CalendarData.cs
- MouseActionValueSerializer.cs
- CorrelationKeyCalculator.cs
- WebPageTraceListener.cs
- ObjectParameter.cs
- DataError.cs