Predicate.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Query / PlanCompiler / Predicate.cs / 1305376 / Predicate.cs

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

using System; 
using System.Collections.Generic;
//using System.Diagnostics; // Please use PlanCompiler.Assert instead of Debug.Assert in this class...
using System.Globalization;
 
using System.Data.Query.InternalTrees;
 
namespace System.Data.Query.PlanCompiler 
{
    ///  
    /// The Predicate class represents a condition (predicate) in CNF.
    /// A predicate consists of a number of "simple" parts, and the parts are considered to be
    /// ANDed together
    /// 
    /// This class provides a number of useful functions related to
    ///   - Single Table predicates 
    ///   - Join predicates 
    ///   - Key preservation
    ///   - Null preservation 
    /// etc.
    ///
    /// Note: This class doesn't really convert node trees into CNF form. It looks for
    /// basic CNF patterns, and reasons about them. For example, 
    ///    (a AND b) OR c
    /// can technically be translated into (a OR c) AND (b OR c), 
    /// but we don't bother. 
    /// At some future point of time, it might be appropriate to consider this
    /// 
    /// 
    internal class Predicate
    {
        #region private state 
        private Command m_command;
        private List m_parts; 
        #endregion 

        #region constructors 
        /// 
        /// Create an empty predicate
        /// 
        ///  
        internal Predicate(Command command)
        { 
            m_command = command; 
            m_parts = new List();
        } 

        /// 
        /// Create a predicate from a node tree
        ///  
        /// current iqt command
        /// the node tree 
        internal Predicate(Command command, Node andTree) 
            : this(command)
        { 
            PlanCompiler.Assert(andTree != null, "null node passed to Predicate() constructor");
            InitFromAndTree(andTree);
        }
        #endregion 

        #region public surface 
 
        #region construction APIs
        ///  
        /// Add a new "part" (simple predicate) to the current list of predicate parts
        /// 
        /// simple predicate
        internal void AddPart(Node n) 
        {
            m_parts.Add(n); 
        } 
        #endregion
 
        #region Reconstruction (of node tree)
        /// 
        /// Build up an AND tree based on the current parts.
        /// Specifically, if I have parts (p1, p2, ..., pn), we build up a tree that looks like 
        ///    p1 AND p2 AND ... AND pn
        /// 
        /// If we have no parts, we return a null reference 
        /// If we have only one part, then we return just that part
        ///  
        /// the and subtree
        internal Node BuildAndTree()
        {
            Node andNode = null; 
            foreach (Node n in m_parts)
            { 
                if (andNode == null) 
                {
                    andNode = n; 
                }
                else
                {
                    andNode = m_command.CreateNode(m_command.CreateConditionalOp(OpType.And), 
                        andNode, n);
                } 
            } 
            return andNode;
        } 
        #endregion

        #region SingleTable (Filter) Predicates
 
        /// 
        /// Partition the current predicate into predicates that only apply 
        /// to the specified table (single-table-predicates), and others 
        /// 
        /// current columns defined by the table 
        /// non-single-table predicates
        /// single-table-predicates
        internal Predicate GetSingleTablePredicates(VarVec tableDefinitions,
            out Predicate otherPredicates) 
        {
            List tableDefinitionList = new List(); 
            tableDefinitionList.Add(tableDefinitions); 
            List singleTablePredicateList;
            GetSingleTablePredicates(tableDefinitionList, out singleTablePredicateList, out otherPredicates); 
            return singleTablePredicateList[0];
        }
        #endregion
 
        #region EquiJoins
        ///  
        /// Get the set of equi-join columns from this predicate 
        /// 
        ///  
        /// 
        /// 
        /// 
        ///  
        internal void GetEquiJoinPredicates(VarVec leftTableDefinitions, VarVec rightTableDefinitions,
            out List leftTableEquiJoinColumns, out List rightTableEquiJoinColumns, 
            out Predicate otherPredicates) 
        {
            otherPredicates = new Predicate(m_command); 
            leftTableEquiJoinColumns = new List();
            rightTableEquiJoinColumns = new List();
            foreach (Node part in m_parts)
            { 
                Var leftTableVar;
                Var rightTableVar; 
 
                if (IsEquiJoinPredicate(part, leftTableDefinitions, rightTableDefinitions, out leftTableVar, out rightTableVar))
                { 
                    leftTableEquiJoinColumns.Add(leftTableVar);
                    rightTableEquiJoinColumns.Add(rightTableVar);
                }
                else 
                {
                    otherPredicates.AddPart(part); 
                } 
            }
        } 

        internal Predicate GetJoinPredicates(VarVec leftTableDefinitions, VarVec rightTableDefinitions,
            out Predicate otherPredicates)
        { 
            Predicate joinPredicate = new Predicate(m_command);
            otherPredicates = new Predicate(m_command); 
 
            foreach (Node part in m_parts)
            { 
                Var leftTableVar;
                Var rightTableVar;

                if (Predicate.IsEquiJoinPredicate(part, leftTableDefinitions, rightTableDefinitions, out leftTableVar, out rightTableVar)) 
                {
                    joinPredicate.AddPart(part); 
                } 
                else
                { 
                    otherPredicates.AddPart(part);
                }
            }
            return joinPredicate; 
        }
        #endregion 
 
        #region Keys
        ///  
        /// Is the current predicate a "key-satisfying" predicate?
        /// 
        /// list of keyVars
        /// current table definitions 
        /// true, if this predicate satisfies the keys
        internal bool SatisfiesKey(VarVec keyVars, VarVec definitions) 
        { 
            if (keyVars.Count > 0)
            { 
                VarVec missingKeys = keyVars.Clone();
                foreach (Node part in m_parts)
                {
                    if (part.Op.OpType != OpType.EQ) 
                    {
                        continue; 
                    } 
                    Var keyVar;
                    if (IsKeyPredicate(part.Child0, part.Child1, keyVars, definitions, out keyVar)) 
                    {
                        missingKeys.Clear(keyVar);
                    }
                    else if (IsKeyPredicate(part.Child1, part.Child0, keyVars, definitions, out keyVar)) 
                    {
                        missingKeys.Clear(keyVar); 
                    } 
                }
 
                return missingKeys.IsEmpty;
            }
            return false;
        } 
        #endregion
 
        #region Nulls 
        /// 
        /// Does this predicate preserve nulls for the table columns? 
        ///
        /// If the ansiNullSemantics parameter is set, then we simply return true
        /// always - this shuts off most optimizations
        /// 
        /// 
        /// list of columns to consider 
        /// use ansi null semantics 
        /// true, if the predicate preserves nulls
        internal bool PreservesNulls(VarVec tableColumns, bool ansiNullSemantics) 
        {
            // Don't mess with non-ansi semantics
            if (!ansiNullSemantics)
            { 
                return true;
            } 
 
            // If at least one part does not preserve nulls, then we simply return false
            foreach (Node part in m_parts) 
            {
                if (!PreservesNulls(part, tableColumns))
                {
                    return false; 
                }
            } 
            return true; 
        }
        #endregion 

        #endregion

        #region private methods 
        #region construction
        private void InitFromAndTree(Node andTree) 
        { 
            if (andTree.Op.OpType == OpType.And)
            { 
                InitFromAndTree(andTree.Child0);
                InitFromAndTree(andTree.Child1);
            }
            else 
            {
                m_parts.Add(andTree); 
            } 
        }
        #endregion 

        #region Single Table Predicates

        private void GetSingleTablePredicates(List tableDefinitions, 
            out List singleTablePredicates, out Predicate otherPredicates)
        { 
            singleTablePredicates = new List(); 
            foreach (VarVec vec in tableDefinitions)
            { 
                singleTablePredicates.Add(new Predicate(m_command));
            }
            otherPredicates = new Predicate(m_command);
            VarVec externalRefs = m_command.CreateVarVec(); 

            foreach (Node part in m_parts) 
            { 
                NodeInfo nodeInfo = m_command.GetNodeInfo(part);
 
                bool singleTablePart = false;
                for (int i = 0; i < tableDefinitions.Count; i++)
                {
                    VarVec tableColumns = tableDefinitions[i]; 
                    if (tableColumns != null)
                    { 
                        externalRefs.InitFrom(nodeInfo.ExternalReferences); 
                        externalRefs.Minus(tableColumns);
                        if (externalRefs.IsEmpty) 
                        {
                            singleTablePart = true;
                            singleTablePredicates[i].AddPart(part);
                            break; 
                        }
                    } 
                } 
                if (!singleTablePart)
                { 
                    otherPredicates.AddPart(part);
                }
            }
        } 

        #endregion 
 
        #region EquiJoins
        ///  
        /// Is this "simple" predicate an equi-join predicate?
        ///   (ie) is it of the form "var1 = var2"
        /// Return "var1" and "var2"
        ///  
        /// the simple predicate
        /// var on the left-side 
        /// var on the right 
        /// true, if this is an equijoin predicate
        private static bool IsEquiJoinPredicate(Node simplePredicateNode, out Var leftVar, out Var rightVar) 
        {
            leftVar = null;
            rightVar = null;
            if (simplePredicateNode.Op.OpType != OpType.EQ) 
            {
                return false; 
            } 

            VarRefOp leftVarOp = simplePredicateNode.Child0.Op as VarRefOp; 
            if (leftVarOp == null)
            {
                return false;
            } 
            VarRefOp rightVarOp = simplePredicateNode.Child1.Op as VarRefOp;
            if (rightVarOp == null) 
            { 
                return false;
            } 

            leftVar = leftVarOp.Var;
            rightVar = rightVarOp.Var;
            return true; 
        }
 
        ///  
        /// Is this an equi-join predicate involving columns from the specified tables?
        /// On output, if this was indeed an equijoin predicate, "leftVar" is the 
        /// column of the left table, while "rightVar" is the column of the right table
        /// and the predicate itself is of the form "leftVar = rightVar"
        /// 
        /// the simple predicate node 
        /// interesting columns of the left table
        /// interesting columns of the right table 
        /// join column of the left table 
        /// join column of the right table
        /// true, if this is an equijoin predicate involving columns from the 2 tables 
        private static bool IsEquiJoinPredicate(Node simplePredicateNode,
            VarVec leftTableDefinitions, VarVec rightTableDefinitions,
            out Var leftVar, out Var rightVar)
        { 
            Var tempLeftVar;
            Var tempRightVar; 
 
            leftVar = null;
            rightVar = null; 
            if (!Predicate.IsEquiJoinPredicate(simplePredicateNode, out tempLeftVar, out tempRightVar))
            {
                return false;
            } 

            if (leftTableDefinitions.IsSet(tempLeftVar) && 
                rightTableDefinitions.IsSet(tempRightVar)) 
            {
                leftVar = tempLeftVar; 
                rightVar = tempRightVar;
            }
            else if (leftTableDefinitions.IsSet(tempRightVar) &&
                     rightTableDefinitions.IsSet(tempLeftVar)) 
            {
                leftVar = tempRightVar; 
                rightVar = tempLeftVar; 
            }
            else 
            {
                return false;
            }
 
            return true;
        } 
        #endregion 

        #region Nulls 
        /// 
        /// Does this predicate preserve nulls on the specified columns of the table?
        /// If any of the columns participates in a comparison predicate, or in a
        /// not-null predicate, then, nulls are not preserved 
        /// 
        /// the "simple" predicate node 
        /// list of table columns 
        /// true, if nulls are preserved
        private static bool PreservesNulls(Node simplePredNode, VarVec tableColumns) 
        {
            VarRefOp varRefOp;

            switch (simplePredNode.Op.OpType) 
            {
                case OpType.EQ: 
                case OpType.NE: 
                case OpType.GT:
                case OpType.GE: 
                case OpType.LT:
                case OpType.LE:
                    varRefOp = simplePredNode.Child0.Op as VarRefOp;
                    if (varRefOp != null && tableColumns.IsSet(varRefOp.Var)) 
                    {
                        return false; 
                    } 
                    varRefOp = simplePredNode.Child1.Op as VarRefOp;
                    if (varRefOp != null && tableColumns.IsSet(varRefOp.Var)) 
                    {
                        return false;
                    }
                    return true; 

                case OpType.Not: 
                    if (simplePredNode.Child0.Op.OpType != OpType.IsNull) 
                    {
                        return true; 
                    }
                    varRefOp = simplePredNode.Child0.Child0.Op as VarRefOp;
                    return (varRefOp == null || !tableColumns.IsSet(varRefOp.Var));
 
                case OpType.Like:
                    // If the predicate is "column LIKE constant ...", then the 
                    // predicate does not preserve nulls 
                    ConstantBaseOp constantOp = simplePredNode.Child1.Op as ConstantBaseOp;
                    if (constantOp == null || (constantOp.OpType == OpType.Null)) 
                    {
                        return true;
                    }
                    varRefOp = simplePredNode.Child0.Op as VarRefOp; 
                    if (varRefOp != null && tableColumns.IsSet(varRefOp.Var))
                    { 
                        return false; 
                    }
                    return true; 

                default:
                    return true;
            } 
        }
        #endregion 
 
        #region Keys
        private bool IsKeyPredicate(Node left, Node right, VarVec keyVars, VarVec definitions, out Var keyVar) 
        {
            keyVar = null;

            // If the left-side is not a Var, then return false 
            if (left.Op.OpType != OpType.VarRef)
            { 
                return false; 
            }
            VarRefOp varRefOp = (VarRefOp)left.Op; 
            keyVar = varRefOp.Var;

            // Not a key of this table?
            if (!keyVars.IsSet(keyVar)) 
            {
                return false; 
            } 

            // Make sure that the other side is either a constant, or has no 
            // references at all to us
            NodeInfo otherNodeInfo = m_command.GetNodeInfo(right);
            VarVec otherVarExternalReferences = otherNodeInfo.ExternalReferences.Clone();
            otherVarExternalReferences.And(definitions); 
            return otherVarExternalReferences.IsEmpty;
        } 
        #endregion 

        #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