Code:
/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / BasicViewGenerator.cs / 3 / BasicViewGenerator.cs
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....]
// @backupOwner [....]
//---------------------------------------------------------------------
using System.Data.Common.Utils;
using System.Data.Mapping.ViewGeneration.Structures;
using System.Data.Mapping.ViewGeneration.QueryRewriting;
using System.Data.Mapping.ViewGeneration.Validation;
using System.Data.Mapping.ViewGeneration.Utils;
using System.Data.Common.Utils.Boolean;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Data.Metadata.Edm;
using System.Linq;
using System.Data.Entity;
namespace System.Data.Mapping.ViewGeneration
{
// This class generates a view for an extent that may contain self-joins
// and self-unions -- this can be later simplified or optimized
// Output: A cell tree with LeftCellWrappers as nodes connected by Union, IJ,
// LOJ, FOJs
internal class BasicViewGenerator : InternalBase
{
#region Constructor
// effects: Creates a view generator object that can be used to generate views
// based on usedCells (projectedSlotMap are useful for deciphering the fields)
internal BasicViewGenerator(MemberPathMapBase projectedSlotMap, List usedCells, FragmentQuery activeDomain,
CellNormalizer normalizer, MemberDomainMap domainMap, ErrorLog errorLog, ConfigViewGenerator config)
{
Debug.Assert(usedCells.Count > 0, "No used cells");
m_projectedSlotMap = projectedSlotMap;
m_usedCells = usedCells;
m_normalizer = normalizer;
m_activeDomain = activeDomain;
m_errorLog = errorLog;
m_config = config;
m_domainMap = domainMap;
}
#endregion
#region Fields
private MemberPathMapBase m_projectedSlotMap;
private List m_usedCells;
// Active domain comprises all multiconstants that need to be reconstructed
private FragmentQuery m_activeDomain;
// these two are temporarily needed for checking containment
private CellNormalizer m_normalizer;
private ErrorLog m_errorLog;
private ConfigViewGenerator m_config;
private MemberDomainMap m_domainMap;
#endregion
#region Properties
private FragmentQueryProcessor LeftQP
{
get { return m_normalizer.LeftFragmentQP; }
}
#endregion
#region Exposed Methods
// effects: Given the set of used cells for an extent, returns a
// view to generate that extent
internal CellTreeNode CreateViewExpression()
{
// Create an initial FOJ group with all the used cells as children
OpCellTreeNode fojNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
// Add all the used cells as children to fojNode. This is a valid
// view for the extent. We later try to optimize it
foreach (LeftCellWrapper cell in m_usedCells)
{
LeafCellTreeNode cellNode = new LeafCellTreeNode(m_normalizer, cell);
fojNode.Add(cellNode);
}
//rootNode = GroupByNesting(rootNode);
// Group cells by the "right" extent (recall that we are
// generating the view for the left extent) so that cells of the
// same extent are in the same subtree
CellTreeNode rootNode = GroupByRightExtent(fojNode);
// Change some of the FOJs to Unions, IJs and LOJs
rootNode = IsolateUnions(rootNode);
// The isolation with Union is different from IsolateUnions --
// the above isolation can finds collections of chidren in a
// node and connects them by union. The below one only considers
// two children at a time
// CHANGE_[....]_DESIGN Check whether the optimization for OpType.Union is a net win in terms
// of query performance
rootNode = IsolateByOperator(rootNode, CellTreeOpType.Union);
rootNode = IsolateByOperator(rootNode, CellTreeOpType.IJ);
rootNode = IsolateByOperator(rootNode, CellTreeOpType.LOJ);
return rootNode;
}
#endregion
#region Private Methods
// requires: The tree rooted at cellTreeNode is an FOJ tree of
// LeafCellTreeNodes only, i.e., there is an FOJ node with the
// children being LeafCellTreeNodes
//
// effects: Given a tree rooted at rootNode, ensures that cells
// of the same right extent are placed in their own subtree below
// cellTreeNode. That is, if there are 3 cells of extent A and 2 of
// extent B (i.e., 5 cells with an FOJ on it), the resulting tree has
// an FOJ node with two children -- FOJ nodes. These FOJ nodes have 2
// and 3 children
internal CellTreeNode GroupByRightExtent(CellTreeNode rootNode)
{
// A dictionary that maps an extent to the nodes are from that extent
// We want a ref comparer here
KeyToListMap extentMap =
new KeyToListMap(EqualityComparer.Default);
// CR_Meek_Low: method can be simplified (Map, populate as you go)
// (becomes self-documenting)
// For each leaf child, find the extent of the child and place it
// in extentMap
foreach (LeafCellTreeNode childNode in rootNode.Children)
{
// A cell may contain P, P.PA -- we return P
// CHANGE_[....]_FEATURE_COMPOSITION Need to fix for composition!!
EntitySetBase extent = childNode.RightCellQuery.Extent; // relation or extent to group by
Debug.Assert(extent != null, "Each cell must have a right extent");
// Add the childNode as a child of the FOJ tree for "extent"
extentMap.Add(extent, childNode);
}
// Now go through the extent map and create FOJ nodes for each extent
// Place the nodes for that extent in the newly-created FOJ subtree
// Also add the op node for every node as a child of the final result
OpCellTreeNode result = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
foreach (EntitySetBase extent in extentMap.Keys)
{
OpCellTreeNode extentFojNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
foreach (LeafCellTreeNode childNode in extentMap.ListForKey(extent))
{
extentFojNode.Add(childNode);
}
result.Add(extentFojNode);
}
// We call Flatten to remove any unnecessary nestings
// where an OpNode has only 1 child.
return result.Flatten();
}
// requires: cellTreeNode has a tree such that all its intermediate nodes
// are FOJ nodes only
// effects: Converts the tree rooted at rootNode (recursively) in
// following way and returns a new rootNode -- it partitions
// rootNode's children such that no two different partitions have
// any overlapping constants. These partitions are connected by Union
// nodes (since there is no overlapping).
// Note: Method may modify rootNode's contents and children
private CellTreeNode IsolateUnions(CellTreeNode rootNode)
{
if (rootNode.Children.Count <= 1)
{
// No partitioning of children needs to be done
return rootNode;
}
Debug.Assert(rootNode.OpType == CellTreeOpType.FOJ, "So far, we have FOJs only");
// Recursively, transform the subtrees rooted at cellTreeNode's children
for (int i = 0; i < rootNode.Children.Count; i++)
{
// Method modifies input as well
rootNode.Children[i] = IsolateUnions(rootNode.Children[i]);
}
// Different children groups are connected by a Union
// node -- the secltion domain of one group is disjoint from
// another group's selection domain, i.e., group A1 contributes
// tuples to the extent which are disjoint from the tuples by
// A2. So we can connect these groups by union alls.
// Inside each group, we continue to connect children of the same
// group using FOJ
OpCellTreeNode unionNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.Union);
// childrenSet keeps track of the children that need to be procesed/partitioned
ModifiableIteratorCollection childrenSet = new ModifiableIteratorCollection(rootNode.Children);
while (false == childrenSet.IsEmpty)
{
// Start a new group
// Make an FOJ node to connect children of the same group
OpCellTreeNode fojNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
// Add one of the root's children as a child to the foj node
CellTreeNode someChild = childrenSet.RemoveOneElement();
fojNode.Add(someChild);
// We now want a transitive closure of the overlap between the
// the children node. We keep checking each child with the
// fojNode and add it as a child of fojNode if there is an
// overlap. Note that when a node is added to the fojNode,
// its constants are propagated to the fojNode -- so we do
// get transitive closure in terms of intersection
foreach (CellTreeNode child in childrenSet.Elements())
{
if (!IsDisjoint(fojNode, child))
{
fojNode.Add(child);
childrenSet.RemoveCurrentOfIterator();
// To ensure that we get all overlapping node, we
// need to restart checking all the children
childrenSet.ResetIterator();
}
}
// Now we have a group of children nodes rooted at
// fojNode. Add this fojNode to the union
unionNode.Add(fojNode);
}
// The union node as the root of the view
CellTreeNode result = unionNode.Flatten();
return result;
}
// requires: opTypeToIsolate must be LOJ, IJ, or Union
// effects: Given a tree rooted at rootNode, determines if there
// are any FOJs that can be replaced by opTypeToIsolate. If so,
// does that and a returns a new tree with the replaced operators
// Note: Method may modify rootNode's contents and children
internal CellTreeNode IsolateByOperator(CellTreeNode rootNode, CellTreeOpType opTypeToIsolate)
{
Debug.Assert(opTypeToIsolate == CellTreeOpType.IJ || opTypeToIsolate == CellTreeOpType.LOJ
|| opTypeToIsolate == CellTreeOpType.Union,
"IsolateJoins can only be called for IJs, LOJs, and Unions");
List children = rootNode.Children;
if (children.Count <= 1)
{
// No child or one child - do nothing
return rootNode;
}
// Replace the FOJs with IJs/LOJs/Unions in the children's subtrees first
for (int i = 0; i < children.Count; i++)
{
// Method modifies input as well
children[i] = IsolateByOperator(children[i], opTypeToIsolate);
}
// Only FOJs and LOJs can be coverted (to IJs, Unions, LOJs) --
// so if the node is not that, we can ignore it (or if the node is already of
// the same type that we want)
if (rootNode.OpType != CellTreeOpType.FOJ && rootNode.OpType != CellTreeOpType.LOJ ||
rootNode.OpType == opTypeToIsolate)
{
return rootNode;
}
// Create a new node with the same type as the input cell node type
OpCellTreeNode newRootNode = new OpCellTreeNode(m_normalizer, rootNode.OpType);
// We start a new "group" with one of the children X - we create
// a newChildNode with type "opTypeToIsolate". Then we
// determine if any of the remaining children should be in the
// same group as X.
// childrenSet keeps track of the children that need to be procesed/partitioned
ModifiableIteratorCollection childrenSet = new ModifiableIteratorCollection(children);
// Find groups with same or subsumed constants and create a join
// or union node for them. We do this so that some of the FOJs
// can be replaced by union and join nodes
//
while (false == childrenSet.IsEmpty)
{
// Start a new "group" with some child node (for the opTypeToIsolate node type)
OpCellTreeNode groupNode = new OpCellTreeNode(m_normalizer, opTypeToIsolate);
CellTreeNode someChild = childrenSet.RemoveOneElement();
groupNode.Add(someChild);
// Go through the remaining children and determine if their
// constants are subsets/equal/disjoint w.r.t the joinNode
// constants.
foreach (CellTreeNode child in childrenSet.Elements())
{
// Check if we can add the child as part of this
// groupNode (with opTypeToIsolate being LOJ, IJ, or Union)
if (TryAddChildToGroup(opTypeToIsolate, child, groupNode))
{
childrenSet.RemoveCurrentOfIterator();
// For LOJ, suppose that child A did not subsume B or
// vice-versa. But child C subsumes both. To ensure
// that we can get A, B, C in the same group, we
// reset the iterator so that when C is added in B's
// loop, we can reconsider A.
// CHANGE_[....]_DESIGN: the iterator should only be reset if we're isolating LOJ
// (even then I'm not entirely convinced, since in LOJ you only add elements
// that subsume, not that elements that are subsumed)
childrenSet.ResetIterator();
}
}
// The new Union/LOJ/IJ node needs to be connected to the root
newRootNode.Add(groupNode);
}
return newRootNode.Flatten();
}
// effects: Determines if the childNode can be added as a child of the
// groupNode using te operation "opTypeToIsolate". E.g., if
// opTypeToIsolate is inner join, we can add child to group node if
// childNode and groupNode have the same multiconstantsets, i.e., they have
// the same selection condition
// Modifies groupNode to contain groupNode at the appropriate
// position (for LOJs, the child could be added to the beginning)
private bool TryAddChildToGroup(CellTreeOpType opTypeToIsolate, CellTreeNode childNode,
OpCellTreeNode groupNode)
{
switch (opTypeToIsolate)
{
case CellTreeOpType.IJ:
// For Inner join, the constants of the node and
// the child must be the same, i.e., if the cells
// are producing exactly same tuples (same selection)
if (IsEquivalentTo(childNode, groupNode))
{
groupNode.Add(childNode);
return true;
}
break;
case CellTreeOpType.LOJ:
// If one cell's selection condition subsumes
// another, we can use LOJ. We need to check for
// "subsumes" on both sides
if (IsContainedIn(childNode, groupNode))
{
groupNode.Add(childNode);
return true;
}
else if (IsContainedIn(groupNode, childNode))
{
// child subsumes the whole group -- add it first
groupNode.AddFirst(childNode);
return true;
}
break;
case CellTreeOpType.Union:
// If the selection conditions are disjoint, we can use UNION ALL
// We cannot use active domain here; disjointness is guaranteed only
// if we check the entire selection domain
if (IsDisjoint(childNode, groupNode))
{
groupNode.Add(childNode);
return true;
}
break;
}
return false;
}
private bool IsDisjoint(CellTreeNode n1, CellTreeNode n2)
{
bool isQueryView = (m_normalizer.SchemaContext.ViewTarget == ViewTarget.QueryView);
bool isDisjointLeft = LeftQP.IsDisjointFrom(n1.LeftFragmentQuery, n2.LeftFragmentQuery);
if (isDisjointLeft && m_normalizer.SchemaContext.ViewTarget == ViewTarget.QueryView)
{
return true;
}
CellTreeNode n = new OpCellTreeNode(m_normalizer, CellTreeOpType.IJ, n1, n2);
bool isDisjointRight = m_normalizer.IsEmpty(n);
if (m_normalizer.SchemaContext.ViewTarget == ViewTarget.UpdateView &&
isDisjointLeft && !isDisjointRight)
{
if (ErrorPatternMatcher.FindMappingErrors(m_normalizer, m_domainMap, m_errorLog))
{
return false;
}
StringBuilder builder = new StringBuilder(Strings.Viewgen_RightSideNotDisjoint(m_normalizer.Extent.ToString()));
builder.AppendLine();
//Retrieve the offending state
FragmentQuery intersection = LeftQP.Intersect(n1.RightFragmentQuery, n2.RightFragmentQuery);
if (LeftQP.IsSatisfiable(intersection))
{
intersection.Condition.ExpensiveSimplify();
RewritingValidator.EntityConfigurationToUserString(intersection.Condition, builder);
}
//Add Error
m_errorLog.AddEntry(new ErrorLog.Record(true, ViewGenErrorCode.DisjointConstraintViolation,
builder.ToString(), m_normalizer.AllWrappersForExtent, String.Empty));
ExceptionHelpers.ThrowMappingException(m_errorLog, m_config);
return false;
}
return (isDisjointLeft || isDisjointRight);
}
private bool IsContainedIn(CellTreeNode n1, CellTreeNode n2)
{
// Decide whether to IJ or LOJ using the domains that are filtered by the active domain
// The net effect is that some unneeded multiconstants will be pruned away in IJ/LOJ
// It is desirable to do so since we are only interested in the active domain
FragmentQuery n1Active = LeftQP.Intersect(n1.LeftFragmentQuery, m_activeDomain);
FragmentQuery n2Active = LeftQP.Intersect(n2.LeftFragmentQuery, m_activeDomain);
bool isContainedLeft = LeftQP.IsContainedIn(n1Active, n2Active);
if (isContainedLeft)
{
return true;
}
CellTreeNode n = new OpCellTreeNode(m_normalizer, CellTreeOpType.LASJ, n1, n2);
bool isContainedRight = m_normalizer.IsEmpty(n);
return isContainedRight;
}
private bool IsEquivalentTo(CellTreeNode n1, CellTreeNode n2)
{
return IsContainedIn(n1, n2) && IsContainedIn(n2, n1);
}
#endregion
#region String methods
internal override void ToCompactString(StringBuilder builder)
{
// We just print the slotmap for now
m_projectedSlotMap.ToCompactString(builder);
}
#endregion
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//----------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
//
// @owner [....]
// @backupOwner [....]
//---------------------------------------------------------------------
using System.Data.Common.Utils;
using System.Data.Mapping.ViewGeneration.Structures;
using System.Data.Mapping.ViewGeneration.QueryRewriting;
using System.Data.Mapping.ViewGeneration.Validation;
using System.Data.Mapping.ViewGeneration.Utils;
using System.Data.Common.Utils.Boolean;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Data.Metadata.Edm;
using System.Linq;
using System.Data.Entity;
namespace System.Data.Mapping.ViewGeneration
{
// This class generates a view for an extent that may contain self-joins
// and self-unions -- this can be later simplified or optimized
// Output: A cell tree with LeftCellWrappers as nodes connected by Union, IJ,
// LOJ, FOJs
internal class BasicViewGenerator : InternalBase
{
#region Constructor
// effects: Creates a view generator object that can be used to generate views
// based on usedCells (projectedSlotMap are useful for deciphering the fields)
internal BasicViewGenerator(MemberPathMapBase projectedSlotMap, List usedCells, FragmentQuery activeDomain,
CellNormalizer normalizer, MemberDomainMap domainMap, ErrorLog errorLog, ConfigViewGenerator config)
{
Debug.Assert(usedCells.Count > 0, "No used cells");
m_projectedSlotMap = projectedSlotMap;
m_usedCells = usedCells;
m_normalizer = normalizer;
m_activeDomain = activeDomain;
m_errorLog = errorLog;
m_config = config;
m_domainMap = domainMap;
}
#endregion
#region Fields
private MemberPathMapBase m_projectedSlotMap;
private List m_usedCells;
// Active domain comprises all multiconstants that need to be reconstructed
private FragmentQuery m_activeDomain;
// these two are temporarily needed for checking containment
private CellNormalizer m_normalizer;
private ErrorLog m_errorLog;
private ConfigViewGenerator m_config;
private MemberDomainMap m_domainMap;
#endregion
#region Properties
private FragmentQueryProcessor LeftQP
{
get { return m_normalizer.LeftFragmentQP; }
}
#endregion
#region Exposed Methods
// effects: Given the set of used cells for an extent, returns a
// view to generate that extent
internal CellTreeNode CreateViewExpression()
{
// Create an initial FOJ group with all the used cells as children
OpCellTreeNode fojNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
// Add all the used cells as children to fojNode. This is a valid
// view for the extent. We later try to optimize it
foreach (LeftCellWrapper cell in m_usedCells)
{
LeafCellTreeNode cellNode = new LeafCellTreeNode(m_normalizer, cell);
fojNode.Add(cellNode);
}
//rootNode = GroupByNesting(rootNode);
// Group cells by the "right" extent (recall that we are
// generating the view for the left extent) so that cells of the
// same extent are in the same subtree
CellTreeNode rootNode = GroupByRightExtent(fojNode);
// Change some of the FOJs to Unions, IJs and LOJs
rootNode = IsolateUnions(rootNode);
// The isolation with Union is different from IsolateUnions --
// the above isolation can finds collections of chidren in a
// node and connects them by union. The below one only considers
// two children at a time
// CHANGE_[....]_DESIGN Check whether the optimization for OpType.Union is a net win in terms
// of query performance
rootNode = IsolateByOperator(rootNode, CellTreeOpType.Union);
rootNode = IsolateByOperator(rootNode, CellTreeOpType.IJ);
rootNode = IsolateByOperator(rootNode, CellTreeOpType.LOJ);
return rootNode;
}
#endregion
#region Private Methods
// requires: The tree rooted at cellTreeNode is an FOJ tree of
// LeafCellTreeNodes only, i.e., there is an FOJ node with the
// children being LeafCellTreeNodes
//
// effects: Given a tree rooted at rootNode, ensures that cells
// of the same right extent are placed in their own subtree below
// cellTreeNode. That is, if there are 3 cells of extent A and 2 of
// extent B (i.e., 5 cells with an FOJ on it), the resulting tree has
// an FOJ node with two children -- FOJ nodes. These FOJ nodes have 2
// and 3 children
internal CellTreeNode GroupByRightExtent(CellTreeNode rootNode)
{
// A dictionary that maps an extent to the nodes are from that extent
// We want a ref comparer here
KeyToListMap extentMap =
new KeyToListMap(EqualityComparer.Default);
// CR_Meek_Low: method can be simplified (Map, populate as you go)
// (becomes self-documenting)
// For each leaf child, find the extent of the child and place it
// in extentMap
foreach (LeafCellTreeNode childNode in rootNode.Children)
{
// A cell may contain P, P.PA -- we return P
// CHANGE_[....]_FEATURE_COMPOSITION Need to fix for composition!!
EntitySetBase extent = childNode.RightCellQuery.Extent; // relation or extent to group by
Debug.Assert(extent != null, "Each cell must have a right extent");
// Add the childNode as a child of the FOJ tree for "extent"
extentMap.Add(extent, childNode);
}
// Now go through the extent map and create FOJ nodes for each extent
// Place the nodes for that extent in the newly-created FOJ subtree
// Also add the op node for every node as a child of the final result
OpCellTreeNode result = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
foreach (EntitySetBase extent in extentMap.Keys)
{
OpCellTreeNode extentFojNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
foreach (LeafCellTreeNode childNode in extentMap.ListForKey(extent))
{
extentFojNode.Add(childNode);
}
result.Add(extentFojNode);
}
// We call Flatten to remove any unnecessary nestings
// where an OpNode has only 1 child.
return result.Flatten();
}
// requires: cellTreeNode has a tree such that all its intermediate nodes
// are FOJ nodes only
// effects: Converts the tree rooted at rootNode (recursively) in
// following way and returns a new rootNode -- it partitions
// rootNode's children such that no two different partitions have
// any overlapping constants. These partitions are connected by Union
// nodes (since there is no overlapping).
// Note: Method may modify rootNode's contents and children
private CellTreeNode IsolateUnions(CellTreeNode rootNode)
{
if (rootNode.Children.Count <= 1)
{
// No partitioning of children needs to be done
return rootNode;
}
Debug.Assert(rootNode.OpType == CellTreeOpType.FOJ, "So far, we have FOJs only");
// Recursively, transform the subtrees rooted at cellTreeNode's children
for (int i = 0; i < rootNode.Children.Count; i++)
{
// Method modifies input as well
rootNode.Children[i] = IsolateUnions(rootNode.Children[i]);
}
// Different children groups are connected by a Union
// node -- the secltion domain of one group is disjoint from
// another group's selection domain, i.e., group A1 contributes
// tuples to the extent which are disjoint from the tuples by
// A2. So we can connect these groups by union alls.
// Inside each group, we continue to connect children of the same
// group using FOJ
OpCellTreeNode unionNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.Union);
// childrenSet keeps track of the children that need to be procesed/partitioned
ModifiableIteratorCollection childrenSet = new ModifiableIteratorCollection(rootNode.Children);
while (false == childrenSet.IsEmpty)
{
// Start a new group
// Make an FOJ node to connect children of the same group
OpCellTreeNode fojNode = new OpCellTreeNode(m_normalizer, CellTreeOpType.FOJ);
// Add one of the root's children as a child to the foj node
CellTreeNode someChild = childrenSet.RemoveOneElement();
fojNode.Add(someChild);
// We now want a transitive closure of the overlap between the
// the children node. We keep checking each child with the
// fojNode and add it as a child of fojNode if there is an
// overlap. Note that when a node is added to the fojNode,
// its constants are propagated to the fojNode -- so we do
// get transitive closure in terms of intersection
foreach (CellTreeNode child in childrenSet.Elements())
{
if (!IsDisjoint(fojNode, child))
{
fojNode.Add(child);
childrenSet.RemoveCurrentOfIterator();
// To ensure that we get all overlapping node, we
// need to restart checking all the children
childrenSet.ResetIterator();
}
}
// Now we have a group of children nodes rooted at
// fojNode. Add this fojNode to the union
unionNode.Add(fojNode);
}
// The union node as the root of the view
CellTreeNode result = unionNode.Flatten();
return result;
}
// requires: opTypeToIsolate must be LOJ, IJ, or Union
// effects: Given a tree rooted at rootNode, determines if there
// are any FOJs that can be replaced by opTypeToIsolate. If so,
// does that and a returns a new tree with the replaced operators
// Note: Method may modify rootNode's contents and children
internal CellTreeNode IsolateByOperator(CellTreeNode rootNode, CellTreeOpType opTypeToIsolate)
{
Debug.Assert(opTypeToIsolate == CellTreeOpType.IJ || opTypeToIsolate == CellTreeOpType.LOJ
|| opTypeToIsolate == CellTreeOpType.Union,
"IsolateJoins can only be called for IJs, LOJs, and Unions");
List children = rootNode.Children;
if (children.Count <= 1)
{
// No child or one child - do nothing
return rootNode;
}
// Replace the FOJs with IJs/LOJs/Unions in the children's subtrees first
for (int i = 0; i < children.Count; i++)
{
// Method modifies input as well
children[i] = IsolateByOperator(children[i], opTypeToIsolate);
}
// Only FOJs and LOJs can be coverted (to IJs, Unions, LOJs) --
// so if the node is not that, we can ignore it (or if the node is already of
// the same type that we want)
if (rootNode.OpType != CellTreeOpType.FOJ && rootNode.OpType != CellTreeOpType.LOJ ||
rootNode.OpType == opTypeToIsolate)
{
return rootNode;
}
// Create a new node with the same type as the input cell node type
OpCellTreeNode newRootNode = new OpCellTreeNode(m_normalizer, rootNode.OpType);
// We start a new "group" with one of the children X - we create
// a newChildNode with type "opTypeToIsolate". Then we
// determine if any of the remaining children should be in the
// same group as X.
// childrenSet keeps track of the children that need to be procesed/partitioned
ModifiableIteratorCollection childrenSet = new ModifiableIteratorCollection(children);
// Find groups with same or subsumed constants and create a join
// or union node for them. We do this so that some of the FOJs
// can be replaced by union and join nodes
//
while (false == childrenSet.IsEmpty)
{
// Start a new "group" with some child node (for the opTypeToIsolate node type)
OpCellTreeNode groupNode = new OpCellTreeNode(m_normalizer, opTypeToIsolate);
CellTreeNode someChild = childrenSet.RemoveOneElement();
groupNode.Add(someChild);
// Go through the remaining children and determine if their
// constants are subsets/equal/disjoint w.r.t the joinNode
// constants.
foreach (CellTreeNode child in childrenSet.Elements())
{
// Check if we can add the child as part of this
// groupNode (with opTypeToIsolate being LOJ, IJ, or Union)
if (TryAddChildToGroup(opTypeToIsolate, child, groupNode))
{
childrenSet.RemoveCurrentOfIterator();
// For LOJ, suppose that child A did not subsume B or
// vice-versa. But child C subsumes both. To ensure
// that we can get A, B, C in the same group, we
// reset the iterator so that when C is added in B's
// loop, we can reconsider A.
// CHANGE_[....]_DESIGN: the iterator should only be reset if we're isolating LOJ
// (even then I'm not entirely convinced, since in LOJ you only add elements
// that subsume, not that elements that are subsumed)
childrenSet.ResetIterator();
}
}
// The new Union/LOJ/IJ node needs to be connected to the root
newRootNode.Add(groupNode);
}
return newRootNode.Flatten();
}
// effects: Determines if the childNode can be added as a child of the
// groupNode using te operation "opTypeToIsolate". E.g., if
// opTypeToIsolate is inner join, we can add child to group node if
// childNode and groupNode have the same multiconstantsets, i.e., they have
// the same selection condition
// Modifies groupNode to contain groupNode at the appropriate
// position (for LOJs, the child could be added to the beginning)
private bool TryAddChildToGroup(CellTreeOpType opTypeToIsolate, CellTreeNode childNode,
OpCellTreeNode groupNode)
{
switch (opTypeToIsolate)
{
case CellTreeOpType.IJ:
// For Inner join, the constants of the node and
// the child must be the same, i.e., if the cells
// are producing exactly same tuples (same selection)
if (IsEquivalentTo(childNode, groupNode))
{
groupNode.Add(childNode);
return true;
}
break;
case CellTreeOpType.LOJ:
// If one cell's selection condition subsumes
// another, we can use LOJ. We need to check for
// "subsumes" on both sides
if (IsContainedIn(childNode, groupNode))
{
groupNode.Add(childNode);
return true;
}
else if (IsContainedIn(groupNode, childNode))
{
// child subsumes the whole group -- add it first
groupNode.AddFirst(childNode);
return true;
}
break;
case CellTreeOpType.Union:
// If the selection conditions are disjoint, we can use UNION ALL
// We cannot use active domain here; disjointness is guaranteed only
// if we check the entire selection domain
if (IsDisjoint(childNode, groupNode))
{
groupNode.Add(childNode);
return true;
}
break;
}
return false;
}
private bool IsDisjoint(CellTreeNode n1, CellTreeNode n2)
{
bool isQueryView = (m_normalizer.SchemaContext.ViewTarget == ViewTarget.QueryView);
bool isDisjointLeft = LeftQP.IsDisjointFrom(n1.LeftFragmentQuery, n2.LeftFragmentQuery);
if (isDisjointLeft && m_normalizer.SchemaContext.ViewTarget == ViewTarget.QueryView)
{
return true;
}
CellTreeNode n = new OpCellTreeNode(m_normalizer, CellTreeOpType.IJ, n1, n2);
bool isDisjointRight = m_normalizer.IsEmpty(n);
if (m_normalizer.SchemaContext.ViewTarget == ViewTarget.UpdateView &&
isDisjointLeft && !isDisjointRight)
{
if (ErrorPatternMatcher.FindMappingErrors(m_normalizer, m_domainMap, m_errorLog))
{
return false;
}
StringBuilder builder = new StringBuilder(Strings.Viewgen_RightSideNotDisjoint(m_normalizer.Extent.ToString()));
builder.AppendLine();
//Retrieve the offending state
FragmentQuery intersection = LeftQP.Intersect(n1.RightFragmentQuery, n2.RightFragmentQuery);
if (LeftQP.IsSatisfiable(intersection))
{
intersection.Condition.ExpensiveSimplify();
RewritingValidator.EntityConfigurationToUserString(intersection.Condition, builder);
}
//Add Error
m_errorLog.AddEntry(new ErrorLog.Record(true, ViewGenErrorCode.DisjointConstraintViolation,
builder.ToString(), m_normalizer.AllWrappersForExtent, String.Empty));
ExceptionHelpers.ThrowMappingException(m_errorLog, m_config);
return false;
}
return (isDisjointLeft || isDisjointRight);
}
private bool IsContainedIn(CellTreeNode n1, CellTreeNode n2)
{
// Decide whether to IJ or LOJ using the domains that are filtered by the active domain
// The net effect is that some unneeded multiconstants will be pruned away in IJ/LOJ
// It is desirable to do so since we are only interested in the active domain
FragmentQuery n1Active = LeftQP.Intersect(n1.LeftFragmentQuery, m_activeDomain);
FragmentQuery n2Active = LeftQP.Intersect(n2.LeftFragmentQuery, m_activeDomain);
bool isContainedLeft = LeftQP.IsContainedIn(n1Active, n2Active);
if (isContainedLeft)
{
return true;
}
CellTreeNode n = new OpCellTreeNode(m_normalizer, CellTreeOpType.LASJ, n1, n2);
bool isContainedRight = m_normalizer.IsEmpty(n);
return isContainedRight;
}
private bool IsEquivalentTo(CellTreeNode n1, CellTreeNode n2)
{
return IsContainedIn(n1, n2) && IsContainedIn(n2, n1);
}
#endregion
#region String methods
internal override void ToCompactString(StringBuilder builder)
{
// We just print the slotmap for now
m_projectedSlotMap.ToCompactString(builder);
}
#endregion
}
}
// 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
- OdbcCommand.cs
- PcmConverter.cs
- ConfigurationPermission.cs
- TrackingServices.cs
- DbException.cs
- NameValueSectionHandler.cs
- TableRowCollection.cs
- SQLRoleProvider.cs
- GlyphInfoList.cs
- ExpressionNode.cs
- TerminatingOperationBehavior.cs
- PropertyRef.cs
- FamilyTypeface.cs
- ThemeableAttribute.cs
- DeferredReference.cs
- DataObject.cs
- GridViewSortEventArgs.cs
- ActivityStatusChangeEventArgs.cs
- ResourcePermissionBaseEntry.cs
- TextFormatterContext.cs
- ProxyHwnd.cs
- OptimalTextSource.cs
- ScriptingScriptResourceHandlerSection.cs
- SourceFileBuildProvider.cs
- CodeObject.cs
- EntityStoreSchemaGenerator.cs
- SerializationFieldInfo.cs
- ComponentDispatcherThread.cs
- Range.cs
- SoapReflector.cs
- WpfMemberInvoker.cs
- WebException.cs
- ColumnPropertiesGroup.cs
- StorageComplexTypeMapping.cs
- SqlDelegatedTransaction.cs
- ResolveCriteria11.cs
- ComEventsMethod.cs
- KnownTypesHelper.cs
- RuleSettingsCollection.cs
- XmlEncoding.cs
- SHA384.cs
- ConnectionString.cs
- FrameworkRichTextComposition.cs
- TripleDESCryptoServiceProvider.cs
- OdbcConnectionHandle.cs
- NetStream.cs
- Identifier.cs
- SqlMethodAttribute.cs
- TextEditorTables.cs
- KeyValueInternalCollection.cs
- InputReportEventArgs.cs
- AttachmentService.cs
- SourceFileInfo.cs
- DecoderBestFitFallback.cs
- InvalidDataContractException.cs
- ProcessThreadCollection.cs
- DataGridCheckBoxColumn.cs
- MarginsConverter.cs
- EnumerableCollectionView.cs
- SoapObjectWriter.cs
- LeafCellTreeNode.cs
- TabControl.cs
- ViewBase.cs
- MDIClient.cs
- ToolboxItem.cs
- Light.cs
- PersonalizationProviderCollection.cs
- COM2ColorConverter.cs
- SqlBulkCopyColumnMappingCollection.cs
- CollectionAdapters.cs
- TaskScheduler.cs
- WriteableBitmap.cs
- DirectoryObjectSecurity.cs
- StorageScalarPropertyMapping.cs
- Expressions.cs
- Policy.cs
- InternalsVisibleToAttribute.cs
- SiteMap.cs
- BaseServiceProvider.cs
- CodeGeneratorAttribute.cs
- IndentedWriter.cs
- NetworkInformationException.cs
- KeysConverter.cs
- XmlCodeExporter.cs
- ContextStack.cs
- XmlSchemaCompilationSettings.cs
- ContentType.cs
- ToolStripDropDownClosingEventArgs.cs
- FilteredDataSetHelper.cs
- DecimalConstantAttribute.cs
- DriveNotFoundException.cs
- TimelineGroup.cs
- ProviderBase.cs
- IDataContractSurrogate.cs
- DefaultValueTypeConverter.cs
- StatusCommandUI.cs
- GenericAuthenticationEventArgs.cs
- SubclassTypeValidator.cs
- InputManager.cs
- DataGridTablesFactory.cs