JoinTreeNode.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Map / ViewGeneration / Structures / JoinTreeNode.cs / 2 / JoinTreeNode.cs

                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System.Data.Common.Utils; 
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Globalization; 
using System.Data.Metadata.Edm;
 
namespace System.Data.Mapping.ViewGeneration.Structures { 

    // JoinTreeNode represents a node in the tree that represents the FROM 
    // part of a cell query. It stores information such as whether the node
    // is optional, whether the node joined, etc
    internal abstract class JoinTreeNode : InternalBase {
 
        #region Enums
 
        ///  
        /// How many times does a particular attribute node occur
        /// E.g., for compositions, it can be Zero .. Many 
        /// 
        internal enum Occurrences {
            Zero,
            Once, 
            Many
        } 
        #endregion 

        #region Constructors/Factories 
        // effects: A private constructor where all the fields are initalized
        protected JoinTreeNode(bool isOptional, IEnumerable children, MetadataWorkspace workspace) {

            Debug.Assert(children != null, "Cannot have a null children list"); 
            Debug.Assert(workspace != null, "MetadataWorkspace should never be null");
            // m_memberPath is left as null. It will be cached when MemberPath is first called 
            m_isOptional  = isOptional; 
            m_children    = new List(children);
            m_workspace = workspace; 

            // Set the parent field in each child
            foreach (JoinTreeNode child in m_children) {
                Debug.Assert(child.m_parent == null, "Child already has parent"); 
                child.m_parent = this;
            } 
        } 
        #endregion
 
        #region Fields
        // A cached path for optimization
        private MemberPath m_memberPath;
        // The nodes emanating from this node, e.g., if p is this node, a 
        // child could be p.pid or p.addrs
        // All the children are members - so strongly type that 
        private List m_children; 
        // Reference to parent for easy navigation up and member path determination -- root has this as null
        private JoinTreeNode m_parent; 
        // Whether the node restricts the number of tuples of its parent
        // (isOptional is false iff restriction)
        private bool m_isOptional;
        private MetadataWorkspace m_workspace; 
        #endregion
 
        #region Properties 
        // effects: Returns the full metadata path from the root extent to
        // this node, e.g., Person.Adrs.zip 
        internal MemberPath MemberPath {
            get {
                MemberPath result = m_memberPath;
                EntitySetBase extent = null; 
                if (m_memberPath == null) {
                    List path = new List(); 
                    JoinTreeNode node = this; 
                    // Go up the parent chain and then reverse the result
                    while (node != null) { 
                        MemberJoinTreeNode memberNode = node as MemberJoinTreeNode;
                        if (memberNode != null) {
                            path.Add(memberNode.Member);
                        } else { 
                            // We are at the root and node better correspond to an extent!
                            ExtentJoinTreeNode extentNode = (ExtentJoinTreeNode) node; 
                            extent = extentNode.Extent; 
                            Debug.Assert(extent != null && node.m_parent == null,
                                         "Non-member node better be extent and its parent needs to be null"); 
                        }
                        node = node.m_parent;
                    }
                    path.Reverse(); 
                    Debug.Assert(extent != null, "Tree must contain extent at root");
                    result = new MemberPath(extent, path, this.MetadataWorkspace); 
                } 
                Debug.Assert(m_memberPath == null || MemberPath.EqualityComparer.Equals(result, m_memberPath),
                             "Cached memberPath not the same as the current position of the node in the tree?"); 
                m_memberPath = result;
                return m_memberPath;
            }
        } 

        // effects: Returns the minimum number of times that this node occurs 
        // in its parent 
        internal static Occurrences MinOccurs {
            // CHANGE_[....]_FEATURE_COMPOSITION: Fix for composition and nested collections 
            get {return Occurrences.Once;}
        }

        // effects: Returns the edm type of this node 
        internal abstract EdmType NodeType { get;}
 
        // effects: Returns the name of the context, i.e., member name or extentname 
        protected abstract string ContextName { get;}
 
        internal MetadataWorkspace MetadataWorkspace { get { return m_workspace; } }
        #endregion

        #region Methods 
        // effects: Returns true if the second reporesent the same
        // extent/member as this 
        protected abstract bool IsSameContext(JoinTreeNode second); 

        // effects: Creates an empty JoinTreeNode from this's Context and nodeIsOptional 
        protected abstract JoinTreeNode CreateNodeFromContext(bool nodeIsOptional, List children);

        // effects: Determines all the identifiers used in this and adds them to identifiers
        internal abstract void GetIdentifiers(CqlIdentifiers identifiers); 

        // requires: member is a child of "this.MemberPath" 
        // effects: Creates a join tree node corresponding to member as a child 
        // node of this and returns the child  -- if it is already present,
        // returns the existing node 
        internal JoinTreeNode CreateAttributeNode(EdmMember member) {
            Debug.Assert(member != null, "Bad member object");
            // Check whether this child is already in the tree
            foreach (MemberJoinTreeNode child in m_children) { 
                if (member.Equals(child.Member)) {
                    return child; // already present 
                } 
            }
 
            MemberJoinTreeNode result = new MemberJoinTreeNode(member, false /* not optional */, new MemberJoinTreeNode[] { }, m_workspace);
            Add(result); // The parent pointer is automatically set
            return result;
        } 

        // effects: Collects all the slots in the tree rooted at this and adds them to slots 
        internal void GatherDescendantSlots(List slots) { 
            slots.Add(new JoinTreeSlot(this));
            foreach (JoinTreeNode child in m_children) { 
                child.GatherDescendantSlots(slots);
            }
        }
 
        // requires: node1 and node2
        // effects: Given that node1 and node2 are currently connected using 
        // operator "opType", merges them into a single node and returns the 
        // merged node. Modifies remap to hold information about remapping
        // different slots in the node. 
        // Modifies g1 (g2) such that it evaluates to true if a tuple
        // originates from node1 (node2).
        // If node1 and node2 do not have the same Value, no merge
        // occurs and null is returned 
        internal JoinTreeNode TryMergeNode(JoinTreeNode node2, CellTreeOpType opType,
                                           ref BoolExpression g1, ref BoolExpression g2, 
                                           Dictionary remap, MemberDomainMap memberDomainMap) { 

            JoinTreeNode node1 = this; 
            Debug.Assert(node1.m_parent == null && node2.m_parent == null ||
                         MemberPath.EqualityComparer.Equals(node1.m_parent.MemberPath, node2.m_parent.MemberPath),
                         "MergeNode on nodes that do not match till parent");
            if (node1.IsSameContext(node2) == false) { 
                return null; // cannot merge
            } 
 
            Debug.Assert(opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ ||
                         opType == CellTreeOpType.IJ || opType == CellTreeOpType.Union || 
                         opType == CellTreeOpType.LASJ,

                         "Unexpected operator type");
 
            // IsOptional appearing in the join tree distinguishes between inner
            // and left outer join (n is the node for S): 
            // R loj S:            n.IsOptional = true 
            // R join S:           n.IsOptional = false
            // 
            // We have the following algebraic equivalences:
            // (R loj T) JOIN (S loj T)   =         (R join S) Loj T
            // (R loj T) JOIN (S join T)  =         (R join S) Join T
            // (R join T) JOIN (S loj T)  =         (R join S) Join T 
            // (R join T) JOIN (S join T) =         (R join S) Join T
 
            // (R loj T) LOJ (S loj T)    =         (R loj S) Loj T 
            // (R loj T) LOJ (S join T)   =         (R loj S) Loj T
            // (R join T) LOJ (S loj T)   =         (R loj S) Join T 
            // (R join T) LOJ (S join T)  =         (R loj S) Join T

            // (R loj T) FOJ (S loj T)    =         (R foj S) Loj S
            // (R loj T) FOJ (S join T)   =         (R foj S) Loj T 
            // (R join T) FOJ (S loj T)   =         (R foj S) Loj T
            // (R join T) FOJ (S join T)  =         (R foj S) Join T 
            // CHANGE_[....]_IMPROVE: Convert to actual declarative calls 
            bool nodeIsOptional = false;
            // The following values are obtained from the above table. 
            // opType is the operator in upper case in the above table
            // We are currently at the node for "T" (i.e., node1 and node2
            // correspond to T) in both join trees. We are trying to merge
            // them to get the right side, i.e., get the capitalized operator on 
            // the right for T
 
            switch (opType) { 
                case CellTreeOpType.IJ: // If both are optional
                    nodeIsOptional = node1.m_isOptional && node2.m_isOptional; 
                    break;
                case CellTreeOpType.LOJ: // The right side's optionality is ignored
                case CellTreeOpType.LASJ:
                    nodeIsOptional = node1.m_isOptional; 
                    break;
                case CellTreeOpType.FOJ:   // Optional if either one is optional 
                case CellTreeOpType.Union: 
                    nodeIsOptional = node1.m_isOptional || node2.m_isOptional;
                    break; 
            }

            JoinTreeNode node = node1.CreateNodeFromContext(nodeIsOptional, new List());
 
            // Essentially, evey boolean in the cell query needs to be true
            // when a tuple comes from its corresponding cell. Since we are 
            // merging two cells, we need to change the booleans accordingly. 
            // g1 and g2 help us in doing that
 
            // Note: We choose node1.VarIfThisJoined in g1 and g2 -- we could
            // have chosen node2.VarIfThisJoined. The reason we do not choose
            // node.VarIfThisJoined is that we need to remap later -- so all
            // expressions must use the old nodes! 

            if (node.m_isOptional && !node2.m_isOptional) { 
                // If right side is non-optional, set g2 to keep track of 
                // this, i.e., when we produce an expression, we will place a
                // value in the right side's SELECT so that we can identify 
                // where this tuple came from
                IfJoinedCondition node2IfJoined = new IfJoinedCondition(node2);
                g2 = BoolExpression.CreateAnd(g2, BoolExpression.CreateLiteral(node2IfJoined, memberDomainMap));
            } 

            if (node.m_isOptional && !node1.m_isOptional) { 
                // This will only happen in FOJ for us 
                IfJoinedCondition node1IfJoined = new IfJoinedCondition(node1);
                g1 = BoolExpression.CreateAnd(g1, BoolExpression.CreateLiteral(node1IfJoined, memberDomainMap)); 
            }

            // Bitmaps to keep track of which children in node1 and node2
            // were found 
            bool[] matched1 = new bool[node1.m_children.Count];
            bool[] matched2 = new bool[node2.m_children.Count]; 
 
            // Process children that match and merge them
            for (int i = 0; i < node1.m_children.Count; i++) { 
                MemberJoinTreeNode child1 = node1.m_children[i];
                // Find the matching child for child1 in node2 if any

                for (int j = 0; j < node2.m_children.Count; j++) { 
                    MemberJoinTreeNode child2 = node2.m_children[j];
                    if (child1.Member.Equals(child2.Member)) { 
                        // Matching child found -- merge the two children -- we will always get back a member node 
                        MemberJoinTreeNode newChild = (MemberJoinTreeNode) child1.TryMergeNode(child2, opType,
                                                                                               ref g1, ref g2, remap, memberDomainMap); 
                        Debug.Assert(newChild != null, "Merge node cannot fail for same values");
                        node.Add(newChild);
                        Debug.Assert(false == matched1[i] && false == matched2[j],
                                     "Nodes match multiple time?"); 
                        matched1[i] = true;
                        matched2[j] = true; 
                    } 
                }
            } 

            // Process unmatched children of node1 and node2
            // Note: For node1 (node2), we pass g2 (g1) since an unmatched
            // child can produce extra children that requires g2(g1) to be modified 
            g2 = ProcessUnmergedChildren(node, node1, g2, remap, matched1, opType, memberDomainMap);
            g1 = ProcessUnmergedChildren(node, node2, g1, remap, matched2, opType, memberDomainMap); 
 
            remap[node1] = node;
            remap[node2] = node; 
            return node;
        }

        ///  
        /// effects: Processes the unmatched children of node (given by
        /// matched) by adding them as children of mergedNode. opType 
        /// indicates the operation that is being used to connect the two join trees 
        /// Modifies remap with the old to new mapping. Returns a boolean
        /// expression (that augments g) such that it evaluates to true if 
        /// node adds extra tuples to the output
        /// 
        private static BoolExpression
        ProcessUnmergedChildren(JoinTreeNode mergedNode, JoinTreeNode node, 
                                BoolExpression g, Dictionary remap,
                                bool[] matched, CellTreeOpType opType, MemberDomainMap memberDomainMap) { 
            for (int j = 0; j < node.m_children.Count; j++) { 
                if (matched[j]) {
                    continue; 
                }

                // Recall: optional = true means LOJ; else it means JOIN
                // The table below says: make unmatched child non-optional if 
                // op=join and the child is non-optional. Otherwise, it's
                // optional 
                // g2 needs to be adjusted in two cases marked below (where 
                // join becomes loj). Similarly, for g1
 
                //  (R) JOIN (R loj S)   =         (R loj S)
                //  (R) JOIN (R join S)  =         (R join S)
                //  (R) LOJ (R loj S)    =         (R loj S)
                //  (R) LOJ (R join S)   =         (R loj S)       // adjust g2 
                //  (R) FOJ (R loj S)    =         (R loj S)
                //  (R) FOJ (R join S)   =         (R loj S)       // adjust g2 
 
                // childCopy refers to S. Essentially, S is only present on
                // one join tree and not the other. S's optionality is 
                // determined from the table above (opType is capitalized
                // operator above)

                // Make a copy of this unmatched child and it merged node 
                JoinTreeNode child = node.m_children[j];
                // Set IsOptional to true according to table AND only if 
                // child can occur zero times 
                bool newIsOptional = !(opType == CellTreeOpType.IJ && false == child.m_isOptional)
                    && JoinTreeNode.MinOccurs == Occurrences.Zero; 
                MemberJoinTreeNode childCopy = (MemberJoinTreeNode) child.DeepClone(newIsOptional, remap);
                mergedNode.Add(childCopy);

                // Adjust g only for the cases where the optionality changed 
                // (as shown in the table above)
                bool ifAdjustG = childCopy.m_isOptional != child.m_isOptional; 
 
                if (ifAdjustG) {
                    // For node1:  T1 (left side) possibly adds extra tuples to the 
                    // result of T (node); update g2 so we can identify T2
                    // (node2) tuples. Similarly for node2.
                    // Note: We choose child.VarIfThisJoined in g -- we do not choose
                    // the new node since we need to remap later -- so all 
                    // expressions must use the old nodes!
                    IfJoinedCondition childIfJoined = new IfJoinedCondition(child); 
                    g = BoolExpression.CreateAnd(g, BoolExpression.CreateLiteral(childIfJoined, memberDomainMap)); 
                }
            } 
            return g;
        }

        // effects: Adds node as a child of this node (sets parent field as well) 
        private void Add(MemberJoinTreeNode node) {
            Debug.Assert(node.m_parent == null, "Attempt to add node that already belongs to some parent"); 
            m_children.Add(node); 
            node.m_parent = this;
        } 

        // effects: Asserts if this node or its children are malformed (for
        // debugging only)
        [Conditional("DEBUG")] 
        internal void Validate() {
            EdmType nodeType = NodeType; 
            foreach (MemberJoinTreeNode child in m_children) { 
                Debug.Assert(child != null, "Null child");
                EdmMember member = child.Member; 
                Debug.Assert(member is EdmProperty || member is RelationshipEndMember,
                             "Malformed join tree: MemberMetadata in a non-root JoinTreeNode must be either property or relation end");
                child.Validate();
            } 
        }
 
        // effects: Performs a deep clone of JoinTreeNode while modifying 
        // remap to store a mapping from the old nodes to the new nodes
        private JoinTreeNode DeepClone(bool isOptionalForNode, Dictionary remap) { 

            List children = new List();
            // Clone the children first
            foreach (MemberJoinTreeNode child in m_children) { 
                children.Add((MemberJoinTreeNode)child.DeepClone(child.m_isOptional, remap));
            } 
 
            // Now create a copy of the node and update remap
            JoinTreeNode newNode = CreateNodeFromContext(isOptionalForNode, children); 
            remap[this] = newNode;
            return newNode;
        }
 
        #endregion
 
        #region String methods 
        // effects: Converts the tree rooted at this into string form
        // (modifies stringBuilder) 
        internal override void ToFullString(StringBuilder builder) {
            builder.Append(ContextName);
            if (m_isOptional) {
                builder.Append('?'); 
            }
            bool first = true; 
            foreach (MemberJoinTreeNode child in m_children) { 
                if (first) {
                    builder.Append('<'); 
                    first = false;
                } else {
                    builder.Append(", ");
                } 
                child.ToFullString(builder);
            } 
            if (!first) { 
                builder.Append('>');
            } 
        }

        internal override void ToCompactString(StringBuilder builder) {
            MemberPath.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.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Globalization; 
using System.Data.Metadata.Edm;
 
namespace System.Data.Mapping.ViewGeneration.Structures { 

    // JoinTreeNode represents a node in the tree that represents the FROM 
    // part of a cell query. It stores information such as whether the node
    // is optional, whether the node joined, etc
    internal abstract class JoinTreeNode : InternalBase {
 
        #region Enums
 
        ///  
        /// How many times does a particular attribute node occur
        /// E.g., for compositions, it can be Zero .. Many 
        /// 
        internal enum Occurrences {
            Zero,
            Once, 
            Many
        } 
        #endregion 

        #region Constructors/Factories 
        // effects: A private constructor where all the fields are initalized
        protected JoinTreeNode(bool isOptional, IEnumerable children, MetadataWorkspace workspace) {

            Debug.Assert(children != null, "Cannot have a null children list"); 
            Debug.Assert(workspace != null, "MetadataWorkspace should never be null");
            // m_memberPath is left as null. It will be cached when MemberPath is first called 
            m_isOptional  = isOptional; 
            m_children    = new List(children);
            m_workspace = workspace; 

            // Set the parent field in each child
            foreach (JoinTreeNode child in m_children) {
                Debug.Assert(child.m_parent == null, "Child already has parent"); 
                child.m_parent = this;
            } 
        } 
        #endregion
 
        #region Fields
        // A cached path for optimization
        private MemberPath m_memberPath;
        // The nodes emanating from this node, e.g., if p is this node, a 
        // child could be p.pid or p.addrs
        // All the children are members - so strongly type that 
        private List m_children; 
        // Reference to parent for easy navigation up and member path determination -- root has this as null
        private JoinTreeNode m_parent; 
        // Whether the node restricts the number of tuples of its parent
        // (isOptional is false iff restriction)
        private bool m_isOptional;
        private MetadataWorkspace m_workspace; 
        #endregion
 
        #region Properties 
        // effects: Returns the full metadata path from the root extent to
        // this node, e.g., Person.Adrs.zip 
        internal MemberPath MemberPath {
            get {
                MemberPath result = m_memberPath;
                EntitySetBase extent = null; 
                if (m_memberPath == null) {
                    List path = new List(); 
                    JoinTreeNode node = this; 
                    // Go up the parent chain and then reverse the result
                    while (node != null) { 
                        MemberJoinTreeNode memberNode = node as MemberJoinTreeNode;
                        if (memberNode != null) {
                            path.Add(memberNode.Member);
                        } else { 
                            // We are at the root and node better correspond to an extent!
                            ExtentJoinTreeNode extentNode = (ExtentJoinTreeNode) node; 
                            extent = extentNode.Extent; 
                            Debug.Assert(extent != null && node.m_parent == null,
                                         "Non-member node better be extent and its parent needs to be null"); 
                        }
                        node = node.m_parent;
                    }
                    path.Reverse(); 
                    Debug.Assert(extent != null, "Tree must contain extent at root");
                    result = new MemberPath(extent, path, this.MetadataWorkspace); 
                } 
                Debug.Assert(m_memberPath == null || MemberPath.EqualityComparer.Equals(result, m_memberPath),
                             "Cached memberPath not the same as the current position of the node in the tree?"); 
                m_memberPath = result;
                return m_memberPath;
            }
        } 

        // effects: Returns the minimum number of times that this node occurs 
        // in its parent 
        internal static Occurrences MinOccurs {
            // CHANGE_[....]_FEATURE_COMPOSITION: Fix for composition and nested collections 
            get {return Occurrences.Once;}
        }

        // effects: Returns the edm type of this node 
        internal abstract EdmType NodeType { get;}
 
        // effects: Returns the name of the context, i.e., member name or extentname 
        protected abstract string ContextName { get;}
 
        internal MetadataWorkspace MetadataWorkspace { get { return m_workspace; } }
        #endregion

        #region Methods 
        // effects: Returns true if the second reporesent the same
        // extent/member as this 
        protected abstract bool IsSameContext(JoinTreeNode second); 

        // effects: Creates an empty JoinTreeNode from this's Context and nodeIsOptional 
        protected abstract JoinTreeNode CreateNodeFromContext(bool nodeIsOptional, List children);

        // effects: Determines all the identifiers used in this and adds them to identifiers
        internal abstract void GetIdentifiers(CqlIdentifiers identifiers); 

        // requires: member is a child of "this.MemberPath" 
        // effects: Creates a join tree node corresponding to member as a child 
        // node of this and returns the child  -- if it is already present,
        // returns the existing node 
        internal JoinTreeNode CreateAttributeNode(EdmMember member) {
            Debug.Assert(member != null, "Bad member object");
            // Check whether this child is already in the tree
            foreach (MemberJoinTreeNode child in m_children) { 
                if (member.Equals(child.Member)) {
                    return child; // already present 
                } 
            }
 
            MemberJoinTreeNode result = new MemberJoinTreeNode(member, false /* not optional */, new MemberJoinTreeNode[] { }, m_workspace);
            Add(result); // The parent pointer is automatically set
            return result;
        } 

        // effects: Collects all the slots in the tree rooted at this and adds them to slots 
        internal void GatherDescendantSlots(List slots) { 
            slots.Add(new JoinTreeSlot(this));
            foreach (JoinTreeNode child in m_children) { 
                child.GatherDescendantSlots(slots);
            }
        }
 
        // requires: node1 and node2
        // effects: Given that node1 and node2 are currently connected using 
        // operator "opType", merges them into a single node and returns the 
        // merged node. Modifies remap to hold information about remapping
        // different slots in the node. 
        // Modifies g1 (g2) such that it evaluates to true if a tuple
        // originates from node1 (node2).
        // If node1 and node2 do not have the same Value, no merge
        // occurs and null is returned 
        internal JoinTreeNode TryMergeNode(JoinTreeNode node2, CellTreeOpType opType,
                                           ref BoolExpression g1, ref BoolExpression g2, 
                                           Dictionary remap, MemberDomainMap memberDomainMap) { 

            JoinTreeNode node1 = this; 
            Debug.Assert(node1.m_parent == null && node2.m_parent == null ||
                         MemberPath.EqualityComparer.Equals(node1.m_parent.MemberPath, node2.m_parent.MemberPath),
                         "MergeNode on nodes that do not match till parent");
            if (node1.IsSameContext(node2) == false) { 
                return null; // cannot merge
            } 
 
            Debug.Assert(opType == CellTreeOpType.FOJ || opType == CellTreeOpType.LOJ ||
                         opType == CellTreeOpType.IJ || opType == CellTreeOpType.Union || 
                         opType == CellTreeOpType.LASJ,

                         "Unexpected operator type");
 
            // IsOptional appearing in the join tree distinguishes between inner
            // and left outer join (n is the node for S): 
            // R loj S:            n.IsOptional = true 
            // R join S:           n.IsOptional = false
            // 
            // We have the following algebraic equivalences:
            // (R loj T) JOIN (S loj T)   =         (R join S) Loj T
            // (R loj T) JOIN (S join T)  =         (R join S) Join T
            // (R join T) JOIN (S loj T)  =         (R join S) Join T 
            // (R join T) JOIN (S join T) =         (R join S) Join T
 
            // (R loj T) LOJ (S loj T)    =         (R loj S) Loj T 
            // (R loj T) LOJ (S join T)   =         (R loj S) Loj T
            // (R join T) LOJ (S loj T)   =         (R loj S) Join T 
            // (R join T) LOJ (S join T)  =         (R loj S) Join T

            // (R loj T) FOJ (S loj T)    =         (R foj S) Loj S
            // (R loj T) FOJ (S join T)   =         (R foj S) Loj T 
            // (R join T) FOJ (S loj T)   =         (R foj S) Loj T
            // (R join T) FOJ (S join T)  =         (R foj S) Join T 
            // CHANGE_[....]_IMPROVE: Convert to actual declarative calls 
            bool nodeIsOptional = false;
            // The following values are obtained from the above table. 
            // opType is the operator in upper case in the above table
            // We are currently at the node for "T" (i.e., node1 and node2
            // correspond to T) in both join trees. We are trying to merge
            // them to get the right side, i.e., get the capitalized operator on 
            // the right for T
 
            switch (opType) { 
                case CellTreeOpType.IJ: // If both are optional
                    nodeIsOptional = node1.m_isOptional && node2.m_isOptional; 
                    break;
                case CellTreeOpType.LOJ: // The right side's optionality is ignored
                case CellTreeOpType.LASJ:
                    nodeIsOptional = node1.m_isOptional; 
                    break;
                case CellTreeOpType.FOJ:   // Optional if either one is optional 
                case CellTreeOpType.Union: 
                    nodeIsOptional = node1.m_isOptional || node2.m_isOptional;
                    break; 
            }

            JoinTreeNode node = node1.CreateNodeFromContext(nodeIsOptional, new List());
 
            // Essentially, evey boolean in the cell query needs to be true
            // when a tuple comes from its corresponding cell. Since we are 
            // merging two cells, we need to change the booleans accordingly. 
            // g1 and g2 help us in doing that
 
            // Note: We choose node1.VarIfThisJoined in g1 and g2 -- we could
            // have chosen node2.VarIfThisJoined. The reason we do not choose
            // node.VarIfThisJoined is that we need to remap later -- so all
            // expressions must use the old nodes! 

            if (node.m_isOptional && !node2.m_isOptional) { 
                // If right side is non-optional, set g2 to keep track of 
                // this, i.e., when we produce an expression, we will place a
                // value in the right side's SELECT so that we can identify 
                // where this tuple came from
                IfJoinedCondition node2IfJoined = new IfJoinedCondition(node2);
                g2 = BoolExpression.CreateAnd(g2, BoolExpression.CreateLiteral(node2IfJoined, memberDomainMap));
            } 

            if (node.m_isOptional && !node1.m_isOptional) { 
                // This will only happen in FOJ for us 
                IfJoinedCondition node1IfJoined = new IfJoinedCondition(node1);
                g1 = BoolExpression.CreateAnd(g1, BoolExpression.CreateLiteral(node1IfJoined, memberDomainMap)); 
            }

            // Bitmaps to keep track of which children in node1 and node2
            // were found 
            bool[] matched1 = new bool[node1.m_children.Count];
            bool[] matched2 = new bool[node2.m_children.Count]; 
 
            // Process children that match and merge them
            for (int i = 0; i < node1.m_children.Count; i++) { 
                MemberJoinTreeNode child1 = node1.m_children[i];
                // Find the matching child for child1 in node2 if any

                for (int j = 0; j < node2.m_children.Count; j++) { 
                    MemberJoinTreeNode child2 = node2.m_children[j];
                    if (child1.Member.Equals(child2.Member)) { 
                        // Matching child found -- merge the two children -- we will always get back a member node 
                        MemberJoinTreeNode newChild = (MemberJoinTreeNode) child1.TryMergeNode(child2, opType,
                                                                                               ref g1, ref g2, remap, memberDomainMap); 
                        Debug.Assert(newChild != null, "Merge node cannot fail for same values");
                        node.Add(newChild);
                        Debug.Assert(false == matched1[i] && false == matched2[j],
                                     "Nodes match multiple time?"); 
                        matched1[i] = true;
                        matched2[j] = true; 
                    } 
                }
            } 

            // Process unmatched children of node1 and node2
            // Note: For node1 (node2), we pass g2 (g1) since an unmatched
            // child can produce extra children that requires g2(g1) to be modified 
            g2 = ProcessUnmergedChildren(node, node1, g2, remap, matched1, opType, memberDomainMap);
            g1 = ProcessUnmergedChildren(node, node2, g1, remap, matched2, opType, memberDomainMap); 
 
            remap[node1] = node;
            remap[node2] = node; 
            return node;
        }

        ///  
        /// effects: Processes the unmatched children of node (given by
        /// matched) by adding them as children of mergedNode. opType 
        /// indicates the operation that is being used to connect the two join trees 
        /// Modifies remap with the old to new mapping. Returns a boolean
        /// expression (that augments g) such that it evaluates to true if 
        /// node adds extra tuples to the output
        /// 
        private static BoolExpression
        ProcessUnmergedChildren(JoinTreeNode mergedNode, JoinTreeNode node, 
                                BoolExpression g, Dictionary remap,
                                bool[] matched, CellTreeOpType opType, MemberDomainMap memberDomainMap) { 
            for (int j = 0; j < node.m_children.Count; j++) { 
                if (matched[j]) {
                    continue; 
                }

                // Recall: optional = true means LOJ; else it means JOIN
                // The table below says: make unmatched child non-optional if 
                // op=join and the child is non-optional. Otherwise, it's
                // optional 
                // g2 needs to be adjusted in two cases marked below (where 
                // join becomes loj). Similarly, for g1
 
                //  (R) JOIN (R loj S)   =         (R loj S)
                //  (R) JOIN (R join S)  =         (R join S)
                //  (R) LOJ (R loj S)    =         (R loj S)
                //  (R) LOJ (R join S)   =         (R loj S)       // adjust g2 
                //  (R) FOJ (R loj S)    =         (R loj S)
                //  (R) FOJ (R join S)   =         (R loj S)       // adjust g2 
 
                // childCopy refers to S. Essentially, S is only present on
                // one join tree and not the other. S's optionality is 
                // determined from the table above (opType is capitalized
                // operator above)

                // Make a copy of this unmatched child and it merged node 
                JoinTreeNode child = node.m_children[j];
                // Set IsOptional to true according to table AND only if 
                // child can occur zero times 
                bool newIsOptional = !(opType == CellTreeOpType.IJ && false == child.m_isOptional)
                    && JoinTreeNode.MinOccurs == Occurrences.Zero; 
                MemberJoinTreeNode childCopy = (MemberJoinTreeNode) child.DeepClone(newIsOptional, remap);
                mergedNode.Add(childCopy);

                // Adjust g only for the cases where the optionality changed 
                // (as shown in the table above)
                bool ifAdjustG = childCopy.m_isOptional != child.m_isOptional; 
 
                if (ifAdjustG) {
                    // For node1:  T1 (left side) possibly adds extra tuples to the 
                    // result of T (node); update g2 so we can identify T2
                    // (node2) tuples. Similarly for node2.
                    // Note: We choose child.VarIfThisJoined in g -- we do not choose
                    // the new node since we need to remap later -- so all 
                    // expressions must use the old nodes!
                    IfJoinedCondition childIfJoined = new IfJoinedCondition(child); 
                    g = BoolExpression.CreateAnd(g, BoolExpression.CreateLiteral(childIfJoined, memberDomainMap)); 
                }
            } 
            return g;
        }

        // effects: Adds node as a child of this node (sets parent field as well) 
        private void Add(MemberJoinTreeNode node) {
            Debug.Assert(node.m_parent == null, "Attempt to add node that already belongs to some parent"); 
            m_children.Add(node); 
            node.m_parent = this;
        } 

        // effects: Asserts if this node or its children are malformed (for
        // debugging only)
        [Conditional("DEBUG")] 
        internal void Validate() {
            EdmType nodeType = NodeType; 
            foreach (MemberJoinTreeNode child in m_children) { 
                Debug.Assert(child != null, "Null child");
                EdmMember member = child.Member; 
                Debug.Assert(member is EdmProperty || member is RelationshipEndMember,
                             "Malformed join tree: MemberMetadata in a non-root JoinTreeNode must be either property or relation end");
                child.Validate();
            } 
        }
 
        // effects: Performs a deep clone of JoinTreeNode while modifying 
        // remap to store a mapping from the old nodes to the new nodes
        private JoinTreeNode DeepClone(bool isOptionalForNode, Dictionary remap) { 

            List children = new List();
            // Clone the children first
            foreach (MemberJoinTreeNode child in m_children) { 
                children.Add((MemberJoinTreeNode)child.DeepClone(child.m_isOptional, remap));
            } 
 
            // Now create a copy of the node and update remap
            JoinTreeNode newNode = CreateNodeFromContext(isOptionalForNode, children); 
            remap[this] = newNode;
            return newNode;
        }
 
        #endregion
 
        #region String methods 
        // effects: Converts the tree rooted at this into string form
        // (modifies stringBuilder) 
        internal override void ToFullString(StringBuilder builder) {
            builder.Append(ContextName);
            if (m_isOptional) {
                builder.Append('?'); 
            }
            bool first = true; 
            foreach (MemberJoinTreeNode child in m_children) { 
                if (first) {
                    builder.Append('<'); 
                    first = false;
                } else {
                    builder.Append(", ");
                } 
                child.ToFullString(builder);
            } 
            if (!first) { 
                builder.Append('>');
            } 
        }

        internal override void ToCompactString(StringBuilder builder) {
            MemberPath.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