Main Page Namespace List Class Hierarchy Compound List File List Namespace Members Compound Members

LcgInfo::PredicateTree Class Reference

This class implements a binary tree of nodes that stores a logical predicate composed of boolean and comparison operators, and leaf elements. More...

#include <PredicateTree.h>

Inheritance diagram for LcgInfo::PredicateTree:

List of all members.

Public Types
enum	NodeType { BOOLEAN, COMPARISON, LEAF }
	The values that the member mType can hold. More...
Public Methods
	PredicateTree ()
	Default constructor of the class. More...
virtual	~PredicateTree ()
	Destructor of the class.
virtual PredicateTree *	create ()=0
	Creates a new node of the type of the node. More...
virtual PredicateTree *	clone ()=0
	Recursively copies this node and all the nodes below it. More...
bool const	PredicateTree::operator== (PredicateTree const &other)
	Overloads the equality comparison operator for PredicateTree objects. More...
void	clear ()
	Deletes of the subnodes children of this node and sets the value to "" and depth to 0 (type is not altered). More...
bool	empty ()
	Checks if the current node is empty; i.e. More...
NodeType	type () const
	Says the type of node that this is. More...
std::string	value () const
	Returns the contents of the information carried by this node. More...
void	translate (TableRowTranslator pTRowT, std::vector< std::string > pOrgTables, std::set< std::string > *pNewTables)
	Traslates the contents of this node (if it is a LEAF), or of its descendent LEAF nodes, by applying the mapping loaded in pTRowT. More...
void	print ()
	Returns a representation of the predicate tree structure for which this node is the root. More...
virtual void	insertPredicate (std::string const &pPred)=0
	Modifies this node, creates the necessary children and passes them the appropriate sub-predicates, to make the tree of which this node is the root represent the specified predicate. More...
virtual std::string	evaluate (std::vector< std::string > &pQueries)=0
	Returns the predicate (and possibly list of necessary subqueries) resulting of evaluating this node and all its descendants. More...
int	depth () const
	Returns the depth of this node in the tree. More...
PredicateTree *	left () const
	Returns a pointer to the left child node of this node. More...
PredicateTree *	right () const
	Returns a pointer to the right child node of this node. More...
void	setType (NodeType const &pType)
	Sets the type of this node. More...
void	setValue (std::string const &pValue)
	Sets the contents of the information carried by this node. More...
void	setDepth (int pDepth)
	Sets the depth of this node in the true. More...
void	setLeft (PredicateTree *pLeft=NULL)
	Sets the pointer to the left child node, and sets the child depth to be one more than that of the current node. More...
void	setRight (PredicateTree *pRight=NULL)
	Sets the pointer to the left child node, and sets the child depth to be one more than that of the current node. More...
void	incrementDepth (int pAmount)
	Sets the depth value of this node to the specified amount and that of its descendents to one more, recursively. More...
bool	relatesTables ()
	Check if this node is of type COMPARISON and if it relates two table keys. More...
bool	isIdentity () const
	Checks if the predicate is an identity; i.e. More...
bool	isRedundant (PredicateTree const &pPred)
	Checks if the specified predicate tree is redundant with the current tree. More...
void	addAndPredicate (std::string const &pPred, std::set< std::string > &pNewTables)
	Creates a new AND node and sets the current node tree as its left branch, and adds the specified predicate in its right branch. More...
bool	isBooleanOp (std::string pStr)
	Checks if the specified string is one of the boolean operators: "AND, "OR, "NOT".
Protected Methods
virtual std::string	getCHARS_TO_TOKENIZE_PREDICATES ()
	Returns the chars to be used as delimiters when tokenizing predicates to be added to a PredicateTree, in order to parse the table names to be added to the new list of tables for the resulting query. More...

Detailed Description

This class implements a binary tree of nodes that stores a logical predicate composed of boolean and comparison operators, and leaf elements.

It originates from a predicate clause of a query string (e.g.:the WHERE clause of an SQL query; where leaf nodes are table.row names, numbers or literals), and can be translated and evaluated to represent other types of predicates. Extending classes, by overloading virtual insertPredicate() and evaluate(), will define the input query language accepted to create the tree of nodes, and the output query language into which the tree is evaluated (implementing a syntactic translation of the predicate). For example, the class SQLtoLDAPPredicateTree would be built by providing a SQL WHERE clause and would be evaluated to a series of LDAP filters (representing the same predicate). The tree also allows the semantic translation of its content from an initial to a target schema, using a mapping between the schemas (and the TableRowTranslator class). In order to build a tree, ech object is a node linked to its two children nodes (left and right). In summary, the tree allows:

the recursive creation of nodes to store a whole predicate (e.g.: (a="pepe" AND c<3) OR (d.id=e.id))
the insertion of AND sub-predicates in a specified part of the tree (with checking of redundancy)
the semantic translation of the whole predicate using a specified mapping (and adding any sub-predicates indicated by the mapping)
the evaluation of the whole tree (returning a query string)

See also:: SQLPredicateTree , LDAPPredicateTree

Author:: LCG's EIS Group. CERN.

Version:: 1.0

Date:: 2004.

Definition at line 51 of file PredicateTree.h.

Member Enumeration Documentation

enum LcgInfo::PredicateTree::NodeType

The values that the member mType can hold.
Just to distinguish if the node is a logical (BOOLEAN node), a comparison operator (COMPARISON) or either a table.row name or a literal (LEAF node).
Definition at line 62 of file PredicateTree.h.
Referenced by setType, and type.

Constructor & Destructor Documentation

PredicateTree::PredicateTree ( )

Default constructor of the class.
It just gives NULL value to pointers and some default (to be changed) value to the rest.
Definition at line 18 of file PredicateTree.cpp.

Member Function Documentation

void PredicateTree::addAndPredicate ( std::string const & pPred,

std::set< std::string > & pNewTables

)

Creates a new AND node and sets the current node tree as its left branch, and adds the specified predicate in its right branch.
It is necessary for the translate() method. It also updates the list of table names of the resulting query (e.g. those of the FROM clause of the resulting query), based on the tables that appear in the predicate to add. It is used by the translate() method.
See also:
translate
Parameters:

pPred the predicate to add as right branch of the AND node

pNewTables pointer to the new list of tables for the resulting query

Definition at line 237 of file PredicateTree.cpp.
References create, LcgInfo::escapeLiterals, LcgInfo::extractTable, LcgInfo::isLiteral, LcgInfo::isNumber, isRedundant, left, right, setLeft, setRight, setType, setValue, LcgInfo::tokenizeStr, and LcgInfo::unescapeLiterals.
Referenced by translate.

void PredicateTree::clear ( )

Deletes of the subnodes children of this node and sets the value to "" and depth to 0 (type is not altered).
The node is afterwards ready to an insertPredicate() without any memory leak. Such a node will return true if the empty() method is called.
Definition at line 62 of file PredicateTree.cpp.
References left, right, setDepth, setLeft, setRight, and setValue.

virtual PredicateTree* LcgInfo::PredicateTree::clone ( ) [pure virtual]

Recursively copies this node and all the nodes below it.
The resulting object's dynamic type will be that of the extending class redefining this method It is a trick (similar to a virtual copy constructor) used to allow the recursive copy of the tree.
See also:
create
Returns:
a pointer to a new Predicate node with the same values as this node

Implemented in LcgInfo::SQLPredicateTree.

virtual PredicateTree* LcgInfo::PredicateTree::create ( ) [pure virtual]

Creates a new node of the type of the node.
It uses some default values (in order to use a template, use the clone() method). As said, the object's dynamic type will be that of the extending class redefining this method. It is a trick (virtual constructor) used to allow the recursive creation of the tree when inserting predicates.
See also:
clone
Returns:
a pointer to a new Predicate node with default values

Implemented in LcgInfo::SQLPredicateTree.
Referenced by addAndPredicate.

int LcgInfo::PredicateTree::depth ( ) const [inline]

Returns the depth of this node in the tree.

Returns:
the depth of the node in the tree

Definition at line 195 of file PredicateTree.h.
Referenced by LcgInfo::SQLtoSQLPredicateTree::clone, LcgInfo::SQLtoLDAPPredicateTree::clone, empty, LcgInfo::SQLtoSQLPredicateTree::evaluate, LcgInfo::SQLtoLDAPPredicateTree::evaluate, setLeft, and setRight.

bool PredicateTree::empty ( )

Checks if the current node is empty; i.e.
its two children are set to NULL, its value to "" and its depth to 0.

Returns:
true if empty, false otherwise

Definition at line 75 of file PredicateTree.cpp.
References depth, left, right, and value.

virtual std::string LcgInfo::PredicateTree::evaluate ( std::vector< std::string > & pQueries ) [pure virtual]

Returns the predicate (and possibly list of necessary subqueries) resulting of evaluating this node and all its descendants.
Extending classes implementing this method will specify the query language used in the output. It may throw a QueryTranslationException if the node (or one of its children) cannot be parsed properly.
Parameters:

pQueries to store the list of necessary subqueries (if any)

Returns:
resulting predicate

Implemented in LcgInfo::SQLPredicateTree.

string PredicateTree::getCHARS_TO_TOKENIZE_PREDICATES ( ) [protected, virtual]

Returns the chars to be used as delimiters when tokenizing predicates to be added to a PredicateTree, in order to parse the table names to be added to the new list of tables for the resulting query.
It is used by the addAndPredicate() method. This class method returns a default value (namely, the one that would be used SQL), but extending classes should redefine it depending on the query language they are using.
See also:
addAndPredicate

Reimplemented in LcgInfo::SQLPredicateTree.
Definition at line 281 of file PredicateTree.cpp.

void PredicateTree::incrementDepth ( int pAmount )

Sets the depth value of this node to the specified amount and that of its descendents to one more, recursively.
It is used by setLeft() and setRight() to set the correct depth for new children of a node.
Parameters:

pAmount the new depth value for this node and its descendents

Definition at line 203 of file PredicateTree.cpp.
References left, right, and setDepth.

virtual void LcgInfo::PredicateTree::insertPredicate ( std::string const & pPred ) [pure virtual]

Modifies this node, creates the necessary children and passes them the appropriate sub-predicates, to make the tree of which this node is the root represent the specified predicate.
It may throw an exception, if the predicate is not well-formed. Extending classes implementing this method will specify the accepted query language for the predicate.
Parameters:

pPredicate a string with the predicate to store in the tree

Implemented in LcgInfo::SQLPredicateTree.

bool PredicateTree::isIdentity ( ) const

Checks if the predicate is an identity; i.e.
it is a comparison operator for two values that are equal.
Definition at line 216 of file PredicateTree.cpp.
References left, right, and type.

bool PredicateTree::isRedundant ( PredicateTree const & pPred )

Checks if the specified predicate tree is redundant with the current tree.
This is true if the specified predicate is an identity (e.g.: a=a); or if it carries the same information that the current tree (e.g.: both are "b>3") or one of the subbranches of the current tree, as long as this subbranch is ANDed to the current root node (e.g.: the specifies tree is "b>3" and the current tree is "(a=1) AND (b>3)"). It is used by addAndPredicate() to avoid adding innecesary predicates to an existing tree.
Parameters:

pPred the predicate tree whose possible redundancy is to be checked

Returns:
true if the pPred is redundant with this tree, false otherwise

Definition at line 224 of file PredicateTree.cpp.
References left, right, type, and value.
Referenced by addAndPredicate.

PredicateTree* LcgInfo::PredicateTree::left ( ) const [inline]

Returns a pointer to the left child node of this node.
Null for LEAF nodes or for BOOLEAN nodes with mValue="NOT".

Returns:
pointer to the left child node or null

Definition at line 202 of file PredicateTree.h.
Referenced by addAndPredicate, clear, LcgInfo::SQLtoSQLPredicateTree::clone, LcgInfo::SQLtoLDAPPredicateTree::clone, empty, LcgInfo::SQLtoSQLPredicateTree::evaluate, LcgInfo::SQLtoLDAPPredicateTree::evaluate, incrementDepth, LcgInfo::SQLPredicateTree::insertPredicate, isIdentity, isRedundant, translate, and ~PredicateTree.

bool const LcgInfo::PredicateTree::PredicateTree::operator== ( PredicateTree const & other )

Overloads the equality comparison operator for PredicateTree objects.
It recursively compares the value of this node and all the nodes below it.
Parameters:

other the tree that has to be compared with this one

Returns:
true if the trees are equal, false otherwise

void PredicateTree::print ( )

Returns a representation of the predicate tree structure for which this node is the root.

Returns:
a string with the representation of the whole predicate tree

Definition at line 179 of file PredicateTree.cpp.
References value.

bool PredicateTree::relatesTables ( )

Check if this node is of type COMPARISON and if it relates two table keys.
It is assumed that if the right child node (which must be a leaf node) is nor a literal neither a number (and thus it is a table.row name), then the comparison effectively relates two tables.

Returns:
true for COMPARISON nodes whose right child is not a literal or a number

Definition at line 209 of file PredicateTree.cpp.
References LcgInfo::isLiteral, LcgInfo::isNumber, right, type, and value.

PredicateTree* LcgInfo::PredicateTree::right ( ) const [inline]

Returns a pointer to the right child node of this node.
Null for LEAF nodes.

Returns:
pointer to the right child node or null

Definition at line 208 of file PredicateTree.h.
Referenced by addAndPredicate, clear, LcgInfo::SQLtoSQLPredicateTree::clone, LcgInfo::SQLtoLDAPPredicateTree::clone, empty, LcgInfo::SQLtoSQLPredicateTree::evaluate, LcgInfo::SQLtoLDAPPredicateTree::evaluate, incrementDepth, LcgInfo::SQLPredicateTree::insertPredicate, isIdentity, isRedundant, relatesTables, translate, and ~PredicateTree.

void LcgInfo::PredicateTree::setDepth ( int pDepth ) [inline]

Sets the depth of this node in the true.

Parameters:

pDepth the depth value of the node (0 for root, 1 for its children...)

Definition at line 226 of file PredicateTree.h.
Referenced by clear, and incrementDepth.

void PredicateTree::setLeft ( PredicateTree * pLeft = NULL )

Sets the pointer to the left child node, and sets the child depth to be one more than that of the current node.

Parameters:

pLeft pointer to a node or null

Definition at line 194 of file PredicateTree.cpp.
References depth.
Referenced by addAndPredicate, clear, LcgInfo::SQLPredicateTree::insertPredicate, translate, and ~PredicateTree.

void PredicateTree::setRight ( PredicateTree * pRight = NULL )

Sets the pointer to the left child node, and sets the child depth to be one more than that of the current node.

Parameters:

pLeft pointer to a node or null

Definition at line 198 of file PredicateTree.cpp.
References depth.
Referenced by addAndPredicate, clear, LcgInfo::SQLPredicateTree::insertPredicate, translate, and ~PredicateTree.

void LcgInfo::PredicateTree::setType ( NodeType const & pType ) [inline]

Sets the type of this node.

Parameters:

pType the type to be set for this node

Definition at line 214 of file PredicateTree.h.
References NodeType.
Referenced by addAndPredicate.

void LcgInfo::PredicateTree::setValue ( std::string const & pValue ) [inline]

Sets the contents of the information carried by this node.

Parameters:

pValue a string with the contents

Definition at line 220 of file PredicateTree.h.
Referenced by addAndPredicate, clear, and translate.

void PredicateTree::translate ( TableRowTranslator * pTRowT,

std::vector< std::string > * pOrgTables,

std::set< std::string > * pNewTables

)

Traslates the contents of this node (if it is a LEAF), or of its descendent LEAF nodes, by applying the mapping loaded in pTRowT.
It takes into account any new predicates that must be applied (as indicated by pTRowT), and adds them in the proper place using addAndPredicate(). It uses the list of possible tables (e.g.: those of the SQL query's FROM clause), to be able to deal with incomplete row names (i.e. without their corresponding table name). It also updates the list of table names of the resulting query (e.g. those of the FROM clause of the resulting query). It may throw a QueryTranslationException if the added predicates defined in the mapping file are not well-formed, or if the attribute matching using the mapping file is not working properly.
Parameters:

pTRowT the object that performs the translation of each table.row element

pFromList pointer to the list of possible tables to complete table.row names

pNewTables pointer to the new list of tables for the resulting query

Definition at line 83 of file PredicateTree.cpp.
References addAndPredicate, LcgInfo::extractTable, LcgInfo::int2str, LcgInfo::isLiteral, LcgInfo::isNumber, left, right, setLeft, setRight, setValue, type, and value.

NodeType LcgInfo::PredicateTree::type ( ) const [inline]

Says the type of node that this is.
It is one of the values of NodeType.

Returns:
the type of this node

Definition at line 131 of file PredicateTree.h.
References NodeType.
Referenced by LcgInfo::SQLtoSQLPredicateTree::clone, LcgInfo::SQLtoLDAPPredicateTree::clone, LcgInfo::SQLtoSQLPredicateTree::evaluate, LcgInfo::SQLtoLDAPPredicateTree::evaluate, isIdentity, isRedundant, relatesTables, and translate.

std::string LcgInfo::PredicateTree::value ( ) const [inline]

Returns the contents of the information carried by this node.

Returns:
a string with the contents of this node

Definition at line 137 of file PredicateTree.h.
Referenced by LcgInfo::SQLtoSQLPredicateTree::clone, LcgInfo::SQLtoLDAPPredicateTree::clone, empty, LcgInfo::SQLtoSQLPredicateTree::evaluate, LcgInfo::SQLtoLDAPPredicateTree::evaluate, isRedundant, print, relatesTables, and translate.

The documentation for this class was generated from the following files:

Generated on Tue Oct 5 14:42:45 2004 for LCG Information System Interface by

LcgInfo::PredicateTree Class Reference

Public Types

Public Methods

Protected Methods

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation