Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / QueryRewriting / RewritingPass.cs / 1305376 / RewritingPass.cs
//---------------------------------------------------------------------- //// Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System; using System.Diagnostics; using System.Collections.Generic; using System.Text; using System.Linq; namespace System.Data.Mapping.ViewGeneration.QueryRewriting { // Goal: use the next view to get rewritingSoFar to be closer to the goal internal class RewritingPasswhere T_Tile : class { // region that rewriting needs to cover private readonly T_Tile m_toFill; // region that rewriting needs to be disjoint with private readonly T_Tile m_toAvoid; private readonly List m_views; private readonly RewritingProcessor m_qp; private readonly Dictionary m_usedViews = new Dictionary (); public RewritingPass(T_Tile toFill, T_Tile toAvoid, List views, RewritingProcessor qp) { m_toFill = toFill; m_toAvoid = toAvoid; m_views = views; m_qp = qp; } public static bool RewriteQuery(T_Tile toFill, T_Tile toAvoid, out T_Tile rewriting, List views, RewritingProcessor qp) { RewritingPass rewritingPass = new RewritingPass (toFill, toAvoid, views, qp); if (rewritingPass.RewriteQuery(out rewriting)) { RewritingSimplifier .TrySimplifyUnionRewriting(ref rewriting, toFill, toAvoid, qp); return true; } return false; } private static bool RewriteQueryInternal(T_Tile toFill, T_Tile toAvoid, out T_Tile rewriting, List views, HashSet recentlyUsedViews, RewritingProcessor qp) { if (qp.REORDER_VIEWS && recentlyUsedViews.Count > 0) { // move recently used views toward the end List reorderedViews = new List (); foreach (T_Tile view in views) { if (false == recentlyUsedViews.Contains(view)) { reorderedViews.Add(view); } } reorderedViews.AddRange(recentlyUsedViews); views = reorderedViews; } RewritingPass rewritingPass = new RewritingPass (toFill, toAvoid, views, qp); return rewritingPass.RewriteQuery(out rewriting); } private bool RewriteQuery(out T_Tile rewriting) { rewriting = m_toFill; T_Tile rewritingSoFar; if (false == FindRewritingByIncludedAndDisjoint(out rewritingSoFar)) { if (false == FindContributingView(out rewritingSoFar)) { return false; } } bool hasExtraTuples = !m_qp.IsDisjointFrom(rewritingSoFar, m_toAvoid); // try to cut off extra tuples using joins if (hasExtraTuples) { foreach (T_Tile view in AvailableViews) { if (TryJoin(view, ref rewritingSoFar)) { hasExtraTuples = false; break; } } } // try to cut off extra tuples using anti-semijoins if (hasExtraTuples) { foreach (T_Tile view in AvailableViews) { if (TryAntiSemiJoin(view, ref rewritingSoFar)) { hasExtraTuples = false; break; } } } if (hasExtraTuples) { return false; // won't be able to cut off extra tuples } // remove redundant joins and anti-semijoins RewritingSimplifier .TrySimplifyJoinRewriting(ref rewritingSoFar, m_toAvoid, m_usedViews, m_qp); // find rewriting for missing tuples, if any T_Tile missingTuples = m_qp.AntiSemiJoin(m_toFill, rewritingSoFar); if (!m_qp.IsEmpty(missingTuples)) { T_Tile rewritingForMissingTuples; if (false == RewritingPass .RewriteQueryInternal(missingTuples, m_toAvoid, out rewritingForMissingTuples, m_views, new HashSet (m_usedViews.Keys), m_qp)) { rewriting = rewritingForMissingTuples; return false; // failure } else { // Although a more general optimization for UNIONs will handle this case, // adding this check reduces the overall number of containment tests if (m_qp.IsContainedIn(rewritingSoFar, rewritingForMissingTuples)) { rewritingSoFar = rewritingForMissingTuples; } else { rewritingSoFar = m_qp.Union(rewritingSoFar, rewritingForMissingTuples); } } } // if we reached this point, we have a successful rewriting rewriting = rewritingSoFar; return true; } // returns true if no more extra tuples are left private bool TryJoin(T_Tile view, ref T_Tile rewriting) { T_Tile newRewriting = m_qp.Join(rewriting, view); if (!m_qp.IsEmpty(newRewriting)) { m_usedViews[view] = TileOpKind.Join; rewriting = newRewriting; return m_qp.IsDisjointFrom(rewriting, m_toAvoid); } return false; } // returns true if no more extra tuples are left private bool TryAntiSemiJoin(T_Tile view, ref T_Tile rewriting) { T_Tile newRewriting = m_qp.AntiSemiJoin(rewriting, view); if (!m_qp.IsEmpty(newRewriting)) { m_usedViews[view] = TileOpKind.AntiSemiJoin; rewriting = newRewriting; return m_qp.IsDisjointFrom(rewriting, m_toAvoid); } return false; } // Try to find a rewriting by intersecting all views which contain the query // and subtracting all views that are disjoint from the query private bool FindRewritingByIncludedAndDisjoint(out T_Tile rewritingSoFar) { // intersect all views in which m_toFill is contained rewritingSoFar = null; foreach (T_Tile view in AvailableViews) { if (m_qp.IsContainedIn(m_toFill, view)) // query <= view { if (rewritingSoFar == null) { rewritingSoFar = view; m_usedViews[view] = TileOpKind.Join; } else { T_Tile newRewriting = m_qp.Join(rewritingSoFar, view); if (!m_qp.IsContainedIn(rewritingSoFar, newRewriting)) { rewritingSoFar = newRewriting; m_usedViews[view] = TileOpKind.Join; // it is a useful join } else { continue; // useless join } } if (m_qp.IsContainedIn(rewritingSoFar, m_toFill)) { return true; } } } // subtract all views that are disjoint from m_toFill if (rewritingSoFar != null) { foreach (T_Tile view in AvailableViews) { if (m_qp.IsDisjointFrom(m_toFill, view)) // query ^ view = {} { if (!m_qp.IsDisjointFrom(rewritingSoFar, view)) { rewritingSoFar = m_qp.AntiSemiJoin(rewritingSoFar, view); m_usedViews[view] = TileOpKind.AntiSemiJoin; if (m_qp.IsContainedIn(rewritingSoFar, m_toFill)) { return true; } } } } } return rewritingSoFar != null; } private bool FindContributingView(out T_Tile rewriting) { // find some view that helps reduce toFill foreach (T_Tile view in AvailableViews) { if (false == m_qp.IsDisjointFrom(view, m_toFill)) { rewriting = view; m_usedViews[view] = TileOpKind.Join; // positive, intersected return true; } } rewriting = null; return false; } private IEnumerable AvailableViews { get { return m_views.Where(view => !m_usedViews.ContainsKey(view)); } } } } // 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; using System.Linq; namespace System.Data.Mapping.ViewGeneration.QueryRewriting { // Goal: use the next view to get rewritingSoFar to be closer to the goal internal class RewritingPasswhere T_Tile : class { // region that rewriting needs to cover private readonly T_Tile m_toFill; // region that rewriting needs to be disjoint with private readonly T_Tile m_toAvoid; private readonly List m_views; private readonly RewritingProcessor m_qp; private readonly Dictionary m_usedViews = new Dictionary (); public RewritingPass(T_Tile toFill, T_Tile toAvoid, List views, RewritingProcessor qp) { m_toFill = toFill; m_toAvoid = toAvoid; m_views = views; m_qp = qp; } public static bool RewriteQuery(T_Tile toFill, T_Tile toAvoid, out T_Tile rewriting, List views, RewritingProcessor qp) { RewritingPass rewritingPass = new RewritingPass (toFill, toAvoid, views, qp); if (rewritingPass.RewriteQuery(out rewriting)) { RewritingSimplifier .TrySimplifyUnionRewriting(ref rewriting, toFill, toAvoid, qp); return true; } return false; } private static bool RewriteQueryInternal(T_Tile toFill, T_Tile toAvoid, out T_Tile rewriting, List views, HashSet recentlyUsedViews, RewritingProcessor qp) { if (qp.REORDER_VIEWS && recentlyUsedViews.Count > 0) { // move recently used views toward the end List reorderedViews = new List (); foreach (T_Tile view in views) { if (false == recentlyUsedViews.Contains(view)) { reorderedViews.Add(view); } } reorderedViews.AddRange(recentlyUsedViews); views = reorderedViews; } RewritingPass rewritingPass = new RewritingPass (toFill, toAvoid, views, qp); return rewritingPass.RewriteQuery(out rewriting); } private bool RewriteQuery(out T_Tile rewriting) { rewriting = m_toFill; T_Tile rewritingSoFar; if (false == FindRewritingByIncludedAndDisjoint(out rewritingSoFar)) { if (false == FindContributingView(out rewritingSoFar)) { return false; } } bool hasExtraTuples = !m_qp.IsDisjointFrom(rewritingSoFar, m_toAvoid); // try to cut off extra tuples using joins if (hasExtraTuples) { foreach (T_Tile view in AvailableViews) { if (TryJoin(view, ref rewritingSoFar)) { hasExtraTuples = false; break; } } } // try to cut off extra tuples using anti-semijoins if (hasExtraTuples) { foreach (T_Tile view in AvailableViews) { if (TryAntiSemiJoin(view, ref rewritingSoFar)) { hasExtraTuples = false; break; } } } if (hasExtraTuples) { return false; // won't be able to cut off extra tuples } // remove redundant joins and anti-semijoins RewritingSimplifier .TrySimplifyJoinRewriting(ref rewritingSoFar, m_toAvoid, m_usedViews, m_qp); // find rewriting for missing tuples, if any T_Tile missingTuples = m_qp.AntiSemiJoin(m_toFill, rewritingSoFar); if (!m_qp.IsEmpty(missingTuples)) { T_Tile rewritingForMissingTuples; if (false == RewritingPass .RewriteQueryInternal(missingTuples, m_toAvoid, out rewritingForMissingTuples, m_views, new HashSet (m_usedViews.Keys), m_qp)) { rewriting = rewritingForMissingTuples; return false; // failure } else { // Although a more general optimization for UNIONs will handle this case, // adding this check reduces the overall number of containment tests if (m_qp.IsContainedIn(rewritingSoFar, rewritingForMissingTuples)) { rewritingSoFar = rewritingForMissingTuples; } else { rewritingSoFar = m_qp.Union(rewritingSoFar, rewritingForMissingTuples); } } } // if we reached this point, we have a successful rewriting rewriting = rewritingSoFar; return true; } // returns true if no more extra tuples are left private bool TryJoin(T_Tile view, ref T_Tile rewriting) { T_Tile newRewriting = m_qp.Join(rewriting, view); if (!m_qp.IsEmpty(newRewriting)) { m_usedViews[view] = TileOpKind.Join; rewriting = newRewriting; return m_qp.IsDisjointFrom(rewriting, m_toAvoid); } return false; } // returns true if no more extra tuples are left private bool TryAntiSemiJoin(T_Tile view, ref T_Tile rewriting) { T_Tile newRewriting = m_qp.AntiSemiJoin(rewriting, view); if (!m_qp.IsEmpty(newRewriting)) { m_usedViews[view] = TileOpKind.AntiSemiJoin; rewriting = newRewriting; return m_qp.IsDisjointFrom(rewriting, m_toAvoid); } return false; } // Try to find a rewriting by intersecting all views which contain the query // and subtracting all views that are disjoint from the query private bool FindRewritingByIncludedAndDisjoint(out T_Tile rewritingSoFar) { // intersect all views in which m_toFill is contained rewritingSoFar = null; foreach (T_Tile view in AvailableViews) { if (m_qp.IsContainedIn(m_toFill, view)) // query <= view { if (rewritingSoFar == null) { rewritingSoFar = view; m_usedViews[view] = TileOpKind.Join; } else { T_Tile newRewriting = m_qp.Join(rewritingSoFar, view); if (!m_qp.IsContainedIn(rewritingSoFar, newRewriting)) { rewritingSoFar = newRewriting; m_usedViews[view] = TileOpKind.Join; // it is a useful join } else { continue; // useless join } } if (m_qp.IsContainedIn(rewritingSoFar, m_toFill)) { return true; } } } // subtract all views that are disjoint from m_toFill if (rewritingSoFar != null) { foreach (T_Tile view in AvailableViews) { if (m_qp.IsDisjointFrom(m_toFill, view)) // query ^ view = {} { if (!m_qp.IsDisjointFrom(rewritingSoFar, view)) { rewritingSoFar = m_qp.AntiSemiJoin(rewritingSoFar, view); m_usedViews[view] = TileOpKind.AntiSemiJoin; if (m_qp.IsContainedIn(rewritingSoFar, m_toFill)) { return true; } } } } } return rewritingSoFar != null; } private bool FindContributingView(out T_Tile rewriting) { // find some view that helps reduce toFill foreach (T_Tile view in AvailableViews) { if (false == m_qp.IsDisjointFrom(view, m_toFill)) { rewriting = view; m_usedViews[view] = TileOpKind.Join; // positive, intersected return true; } } rewriting = null; return false; } private IEnumerable AvailableViews { get { return m_views.Where(view => !m_usedViews.ContainsKey(view)); } } } } // 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
- StrongNamePublicKeyBlob.cs
- ToolStripDropDownClosingEventArgs.cs
- DotExpr.cs
- RegexGroupCollection.cs
- PtsPage.cs
- GenericWebPart.cs
- InvalidComObjectException.cs
- LinqDataSourceUpdateEventArgs.cs
- ConnectionProviderAttribute.cs
- TemplatedAdorner.cs
- DataView.cs
- CodeRemoveEventStatement.cs
- DescendantBaseQuery.cs
- HtmlLink.cs
- NonParentingControl.cs
- ContextMenuStripGroupCollection.cs
- ResourceReader.cs
- Registry.cs
- HostedTransportConfigurationBase.cs
- HtmlHead.cs
- Point.cs
- AccessDataSourceView.cs
- VisualBasicReference.cs
- ValueSerializerAttribute.cs
- RowSpanVector.cs
- _ListenerRequestStream.cs
- StylusTip.cs
- ColorConvertedBitmapExtension.cs
- WebErrorHandler.cs
- ServicePointManager.cs
- LockedActivityGlyph.cs
- TextTreeInsertUndoUnit.cs
- ParentQuery.cs
- StructuredProperty.cs
- unitconverter.cs
- DoubleConverter.cs
- ImageKeyConverter.cs
- EventDescriptor.cs
- Rect.cs
- ComponentCommands.cs
- RegexRunner.cs
- QueryIntervalOp.cs
- CompleteWizardStep.cs
- SharedRuntimeState.cs
- RuntimeWrappedException.cs
- DataGridViewImageColumn.cs
- FaultContext.cs
- TrackPointCollection.cs
- FixedNode.cs
- WindowsImpersonationContext.cs
- ResourcesChangeInfo.cs
- SafeUserTokenHandle.cs
- TableRowGroupCollection.cs
- BroadcastEventHelper.cs
- TextTreeTextNode.cs
- DoubleLinkList.cs
- PropertyFilterAttribute.cs
- DesignerActionTextItem.cs
- BuildResultCache.cs
- BuildProvidersCompiler.cs
- VBIdentifierNameEditor.cs
- ButtonFieldBase.cs
- XPathAncestorIterator.cs
- StylusLogic.cs
- ToolStripPanelRow.cs
- ConstructorArgumentAttribute.cs
- XmlSchemaSet.cs
- MissingMethodException.cs
- HttpListenerRequestUriBuilder.cs
- Variant.cs
- PhysicalAddress.cs
- CaseInsensitiveHashCodeProvider.cs
- DurationConverter.cs
- BuildResult.cs
- PassportAuthenticationEventArgs.cs
- ApplicationServiceHelper.cs
- RootProjectionNode.cs
- PathNode.cs
- Positioning.cs
- DSASignatureFormatter.cs
- EdmSchemaAttribute.cs
- ToolStripPanelRow.cs
- XsdBuildProvider.cs
- ProviderMetadataCachedInformation.cs
- ObjectQueryState.cs
- AttachedPropertyBrowsableForTypeAttribute.cs
- DiscoveryClientDocuments.cs
- CodeTypeReferenceExpression.cs
- EventMappingSettings.cs
- DbgUtil.cs
- SymLanguageType.cs
- ServiceProviders.cs
- QueryOperatorEnumerator.cs
- DataServiceExpressionVisitor.cs
- WinInet.cs
- FileStream.cs
- ObjectStorage.cs
- XmlTextEncoder.cs
- IriParsingElement.cs
- BitmapEffectrendercontext.cs