BasicViewGenerator.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / BasicViewGenerator.cs / 1305376 / 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(MemberProjectionIndex projectedSlotMap, List usedCells, FragmentQuery activeDomain,
                                    ViewgenContext context, MemberDomainMap domainMap, ErrorLog errorLog, ConfigViewGenerator config) 
        {
            Debug.Assert(usedCells.Count > 0, "No used cells");
            m_projectedSlotMap = projectedSlotMap;
            m_usedCells = usedCells; 
            m_viewgenContext = context;
            m_activeDomain = activeDomain; 
            m_errorLog = errorLog; 
            m_config = config;
            m_domainMap = domainMap; 
        }
        #endregion

        #region Fields 
        private MemberProjectionIndex 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 ViewgenContext m_viewgenContext;
        private ErrorLog m_errorLog;
        private ConfigViewGenerator m_config;
        private MemberDomainMap m_domainMap; 
        #endregion
 
        #region Properties 
        private FragmentQueryProcessor LeftQP
        { 
            get { return m_viewgenContext.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_viewgenContext, 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_viewgenContext, 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.LeftCellWrapper.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_viewgenContext, CellTreeOpType.FOJ); 

            foreach (EntitySetBase extent in extentMap.Keys) 
            {
                OpCellTreeNode extentFojNode = new OpCellTreeNode(m_viewgenContext, 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_viewgenContext, 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_viewgenContext, 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_viewgenContext, 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_viewgenContext, 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_viewgenContext.ViewTarget == ViewTarget.QueryView);
 
            bool isDisjointLeft = LeftQP.IsDisjointFrom(n1.LeftFragmentQuery, n2.LeftFragmentQuery); 

            if (isDisjointLeft && m_viewgenContext.ViewTarget == ViewTarget.QueryView) 
            {
                return true;
            }
 
            CellTreeNode n = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.IJ, n1, n2);
            bool isDisjointRight = n.IsEmptyRightFragmentQuery; 
 
            if (m_viewgenContext.ViewTarget == ViewTarget.UpdateView &&
                isDisjointLeft && !isDisjointRight) 
            {

                if (ErrorPatternMatcher.FindMappingErrors(m_viewgenContext, m_domainMap, m_errorLog))
                { 
                    return false;
                } 
 

                StringBuilder builder = new StringBuilder(Strings.Viewgen_RightSideNotDisjoint(m_viewgenContext.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_viewgenContext.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_viewgenContext, CellTreeOpType.LASJ, n1, n2);
            bool isContainedRight = n.IsEmptyRightFragmentQuery; 

            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(MemberProjectionIndex projectedSlotMap, List usedCells, FragmentQuery activeDomain,
                                    ViewgenContext context, MemberDomainMap domainMap, ErrorLog errorLog, ConfigViewGenerator config) 
        {
            Debug.Assert(usedCells.Count > 0, "No used cells");
            m_projectedSlotMap = projectedSlotMap;
            m_usedCells = usedCells; 
            m_viewgenContext = context;
            m_activeDomain = activeDomain; 
            m_errorLog = errorLog; 
            m_config = config;
            m_domainMap = domainMap; 
        }
        #endregion

        #region Fields 
        private MemberProjectionIndex 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 ViewgenContext m_viewgenContext;
        private ErrorLog m_errorLog;
        private ConfigViewGenerator m_config;
        private MemberDomainMap m_domainMap; 
        #endregion
 
        #region Properties 
        private FragmentQueryProcessor LeftQP
        { 
            get { return m_viewgenContext.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_viewgenContext, 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_viewgenContext, 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.LeftCellWrapper.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_viewgenContext, CellTreeOpType.FOJ); 

            foreach (EntitySetBase extent in extentMap.Keys) 
            {
                OpCellTreeNode extentFojNode = new OpCellTreeNode(m_viewgenContext, 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_viewgenContext, 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_viewgenContext, 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_viewgenContext, 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_viewgenContext, 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_viewgenContext.ViewTarget == ViewTarget.QueryView);
 
            bool isDisjointLeft = LeftQP.IsDisjointFrom(n1.LeftFragmentQuery, n2.LeftFragmentQuery); 

            if (isDisjointLeft && m_viewgenContext.ViewTarget == ViewTarget.QueryView) 
            {
                return true;
            }
 
            CellTreeNode n = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.IJ, n1, n2);
            bool isDisjointRight = n.IsEmptyRightFragmentQuery; 
 
            if (m_viewgenContext.ViewTarget == ViewTarget.UpdateView &&
                isDisjointLeft && !isDisjointRight) 
            {

                if (ErrorPatternMatcher.FindMappingErrors(m_viewgenContext, m_domainMap, m_errorLog))
                { 
                    return false;
                } 
 

                StringBuilder builder = new StringBuilder(Strings.Viewgen_RightSideNotDisjoint(m_viewgenContext.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_viewgenContext.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_viewgenContext, CellTreeOpType.LASJ, n1, n2);
            bool isContainedRight = n.IsEmptyRightFragmentQuery; 

            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

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK