%*********************************************************************************************************************************
% RULE FOR RUNNING THE OPTIMIZER
% true if (GraphOut, NodesOut) is the best query plan that can be constructed, and if it has cost FinalCost.  The optimizer
% works by taking an input plan (stored in the predicate database) and repeatedly applying the transformations allowed by
% the transform\6 predicate.  At each step, the optimizer maintains a current set of good plans.  It tries all possible
% transformations on every plan in that set, and retains the best few plans that are optained.  The number of
% transformations used to compute the query plan must be at most NumTransformsToAllow, and at every step of the optimization,
% the best NumAlternativesToKeep alternative plans are retained.  Thus, if NumAlternativesToKeep = 1, then the optimzer
% uses a purely greedy search.

optimize(FinalCost, GraphOut, NodesOut, NumTransformsToAllow, NumAlternativesToKeep) :-	
	%**** the first few lines simply make lists out of all of the parts of the query plan that are stored in the predicate database
	%**** the reason for the "current_predicate(parent/2)" and the like is that before we make a list out of all of the "parent"
	%**** database entries, we need to make sure that there is actually a "parent" relation (otherwise, setof will abosrt)
	(current_predicate(parent/2) -> setof(parent(Parent, Child), parent(Parent, Child), GraphIn); GraphIn = []),
	(current_predicate(join/2) -> setof(join(NodeName, Data), join(NodeName, Data), Joins); Joins = []),
	(current_predicate(selection/2) -> setof(selection(NodeName, Data), selection(NodeName, Data), Selections); Selections = []),
	(current_predicate(tableScan/2) -> setof(tableScan(NodeName, Data), tableScan(NodeName, Data), TableScans); TableScans = []),
	dePartition([Joins, Selections, TableScans], NodesIn),
	setof(stats(NodeName, AttValCounts, NumTuples), stats(NodeName, AttValCounts, NumTuples), PrelimCosts),
	%**** do a costing of the initial query plan
	costPlan(GraphIn, NodesIn, PrelimCosts, CostsIn),
	%**** and actually run the optimization
	doSeriesOfTransforms([goodPlan(9e99, GraphIn, NodesIn, CostsIn)], 
		[goodPlan(FinalCost, GraphOut, NodesOut, _)|_], NumTransformsToAllow, NumAlternativesToKeep).

%*********************************************************************************************************************************
% RULE FOR RUNNING THE OPTIMIZER
% true if, starting with the set StartPlans, you (1) do a series of SeriesLen steps where at each step you apply all possible
% transformations to every plan in StartPlans (2) retain the best NumToKeepEachStep plans at each step, you will eventually
% get to the set of plans EndPlans

doSeriesOfTransforms(StartPlans, EndPlans, SeriesLen, NumToKeepEachStep) :-
	SeriesLen > 0,
	SeriesLenMinusOne is SeriesLen - 1,
	transformEveryQueryPlanWeHave(StartPlans, WhatYouGetInOneStep, NumToKeepEachStep),
	doSeriesOfTransforms(WhatYouGetInOneStep, EndPlans, SeriesLenMinusOne, NumToKeepEachStep).

doSeriesOfTransforms(StartPlans, EndPlans, 0, _) :-
	StartPlans = EndPlans.

%*********************************************************************************************************************************
% RULE FOR COMPUTING THE FEW BEST PLANS THAT CAN BE OBTAINED FROM RUNNING ALL POSSIBLE TRANSFORMS ON THE CURRENT SET OF PLANS
% returns true if you start with the set BestPlans, run all possible transforms, keep NumToKeep of the resulting plans,
% you will get the set NextPlans as a result

transformEveryQueryPlanWeHave(BestPlans, NextPlans, NumToKeep) :-
	setof(OneSublist, getAllTransformsForOneQueryPlan(BestPlans, OneSublist), PartitionedList),
	dePartition(PartitionedList, UnSortedList),
	sort(UnSortedList, SortedList),
	length(SortedList, ListLen),
	(ListLen > NumToKeep -> Remainder is ListLen - NumToKeep, getLastOnes(SortedList, LastOnes, Remainder);
	 LastOnes = []),
	append(NextPlans, LastOnes, SortedList). 

%*********************************************************************************************************************************
% RULE FOR RUNNING ALL POSSIBLE TRANSFORMS ON A SET OF QUERY PLANS
% true if, when you run all possible transformations on every query plan in the set BestPlans, you get the set NextPlans 

getAllTransformsForOneQueryPlan(BestPlans, NextPlans) :-
	member(goodPlan(_, Graph, Nodes, Costs), BestPlans), 
	setof(goodPlan(FinalCost, GraphOut, NodesOut, CostsOut), 
	      (transform(Graph, Nodes, Costs, GraphOut, NodesOut, CostsOut),
		 member(stats(planRoot, thisIsTheTotalCost, FinalCost), CostsOut)),
		NextPlans).

%*********************************************************************************************************************************
% RULE FOR COSTING AN ENTIRE QUERY PLAN
% true if, given the query plan (GraphIn, NodesIn), where all tableScan nodes in NodesIn have a corresponding cost data 
% entry in CostsIn, CostsOut gives the cost for every other node in the plan

costPlan(GraphIn, NodesIn, CostsIn, CostsOut) :-
	member(parent(planRoot, ChildNode), GraphIn),
	append([stats(planRoot, thisIsTheTotalCost, 0)], CostsIn, IntCosts),
	costPlan(ChildNode, GraphIn, NodesIn, IntCosts, CostsOut).

%*********************************************************************************************************************************
% RULE FOR COSTING THE PART OF A PLAN ANCHORED AT A GIVEN NODE
% like the last rule, except that rather than costing the entire plan, only the portion of the plan anchored at WhichNode
% is costed, and the resulting statistical entries are found in CostsOut

%**** Version that deals with the case where WhichNode is a join
costPlan(WhichNode, GraphIn, NodesIn, CostsIn, CostsOut) :-
	member(join(WhichNode, _), NodesIn),
	select(parent(WhichNode, LHSChild), GraphIn, Trash),
	member(parent(WhichNode, RHSChild), Trash),
	costPlan(LHSChild, GraphIn, NodesIn, CostsIn, CostsInInt1),
	costPlan(RHSChild, GraphIn, NodesIn, CostsInInt1, CostsInInt2),
	LHSChild @< RHSChild, % this is here so we don't do the join twice, interchanging the left and right sides!
	addCostForNewNode(WhichNode, GraphIn, NodesIn, CostsInInt2, CostsOut).

%**** Version that deals with the case where WhichNode is a tableScan
costPlan(WhichNode, _, NodesIn, CostsIn, CostsOut) :-
	member(tableScan(WhichNode, _), NodesIn),
	CostsIn = CostsOut.

%**** Version that deals with the case where WhichNode is a selection operation
costPlan(WhichNode, GraphIn, NodesIn, CostsIn, CostsOut) :-
	member(selection(WhichNode, _), NodesIn),
	member(parent(WhichNode, Child), GraphIn),
	costPlan(Child, GraphIn, NodesIn, CostsIn, CostsInInt),
	addCostForNewNode(WhichNode, GraphIn, NodesIn, CostsInInt, CostsOut).

%*********************************************************************************************************************************
% RULE FOR COMPUTING THE NUMBER OF TUPLES AND ATTRIBUTE VALUES THAT MAKE IT PAST A BOOLEAN PREDICATE
% this is the computeSelectivity rule, which is used to see how many tuples result from applying a specific boolPred.  It 
% also describes how the list of attribute value counts is modified by the predicate.  For exmaple, if the list of att
% value counts is [numVals(table3(att1), 10), numVals(table2(att1), 5)] before a check of table2(att1) = 22, then after
% applying the pred the list of attribute value counts will be given by [numVals(table3(att1), 10), numVals(table2(att1), 1)].
% All of the various versions of computeSelectivity are identical, except that they deal with different types of predicates.
% All versions return true if applying WhichPred to a relation of size NumInputTuples with attribute value counts given by 
% InAttValCounts will result in a relation of size NumOutputTuples and whose attribute value counts are given by OutAttValCounts.

%**** Version that deals with a predicate that tests equality with a literal value
computeSelectivity(WhichPred, NumInputTuples, NumOutputTuples, InAttValCounts, OutAttValCounts) :-
	(current_predicate(equals/3) -> equals(WhichPred, AttName, literal); false),
	select(numVals(AttName, AttValCount), InAttValCounts, IntCounts),
	append([numVals(AttName, 1)], IntCounts, OutAttValCounts),
	NumOutputTuples is NumInputTuples / AttValCount.

%**** Version that deals with a predicate that tests equality of two database attributes
computeSelectivity(WhichPred, NumInputTuples, NumOutputTuples, InAttValCounts, OutAttValCounts) :-
	(current_predicate(equals/3) -> equals(WhichPred, LHSAttName, RHSAttName); false),
	not(equals(WhichPred, LHSAttName, literal)),
	select(numVals(LHSAttName, LHSAttValCount), InAttValCounts, IntCounts1),
	select(numVals(RHSAttName, RHSAttValCount), IntCounts1, IntCounts2),
	(LHSAttValCount < RHSAttValCount -> NumGroups is LHSAttValCount; NumGroups is RHSAttValCount),
	append([numVals(LHSAttName, NumGroups), numVals(RHSAttName, NumGroups)], IntCounts2, OutAttValCounts),
	NumOutputTuples is NumGroups * NumInputTuples / (LHSAttValCount * RHSAttValCount).

%**** Version that deals with a boolean "and" predicate
computeSelectivity(WhichPred, NumInputTuples, NumOutputTuples, InAttValCounts, OutAttValCounts) :-
	(current_predicate(booland/3) -> booland(WhichPred, LHSPred, RHSPred); false),
	computeSelectivity(LHSPred, NumInputTuples, NumOuputTuplesInt, InAttValCounts, OutAttValCountsInt),
	computeSelectivity(RHSPred, NumOuputTuplesInt, NumOutputTuples, OutAttValCountsInt, OutAttValCounts).

%**** Version that deals with a boolean "or" predicate
computeSelectivity(WhichPred, NumInputTuples, NumOutputTuples, InAttValCounts, OutAttValCounts) :-
	(current_predicate(boolor/3) -> boolor(WhichPred, LHSPred, RHSPred); false),
	computeSelectivity(LHSPred, NumInputTuples, NumOuputTuplesLeft, InAttValCounts, OutAttValCountsLHS),
	computeSelectivity(RHSPred, NumInputTuples, NumOutputTuplesRight, InAttValCounts, OutAttValCountsRHS),
	mergeValCountLists(OutAttValCountsLHS, OutAttValCountsRHS, InAttValCounts, OutAttValCounts),
	NumOutputTuples is (NumOuputTuplesLeft + NumOutputTuplesRight) - (NumOuputTuplesLeft / NumInputTuples) * 
		(NumOutputTuplesRight / NumInputTuples) * NumInputTuples.

%**** This version of computeSelectivity is a little different in that rather than having a single predicate name
%**** as the first parameter, a list of predicate names is given as the first parameter.  It is assumed that the
%**** actual predicate we are dealing with is a logical "and" of all of those predicates in the list
computeSelectivity([FirstPredToAnd|OtherPredsToAnd], NumInputTuples, NumOutputTuples, InAttValCounts, OutAttValCounts) :-
	computeSelectivity(FirstPredToAnd, NumInputTuples, NumOuputTuplesInt, InAttValCounts, OutAttValCountsInt),
	computeSelectivity(OtherPredsToAnd, NumOuputTuplesInt, NumOutputTuples, OutAttValCountsInt, OutAttValCounts).

computeSelectivity([], NumInputTuples, NumOutputTuples, InAttValCounts, OutAttValCounts) :-
	NumOutputTuples = NumInputTuples, 
	InAttValCounts = OutAttValCounts.

%*********************************************************************************************************************************
% RULE FOR RECONCILING TWO LISTS OF ATTRIBUTE VALUE COUNTS THAT ARE INPUT INTO AN "OR"
% This is used when dealing with the attribute value count lists for an "or" predicate.  The issue is as follows.  Say that
% you are "or"ing the results of pred1 and pred2.  pred1 returns [numVals(table3(att1), 10), numVals(table2(att1), 5)] as its
% attribute value count list, pred2 returns [numVals(table3(att1), 10), numVals(table2(att1), 2)], and the original number of
% attribute values was [numVals(table3(att1), 10), numVals(table2(att1), 5)].  In this case, the two lists should be reconciled
% so that the actual number of attribute value counts is [numVals(table3(att1), 10), numVals(table2(att1), 5)] (since you are
% "or"ing, and you know that the result of the LHS of the or contained all of the input attribute values, it makes sense to assume
% as an approximateion that the result of the "or" contains all of the original attribute values).  Thus, this predicate returns
% true if OutAttValCounts is a reconciled version of the first and the second params (where the first and second params are val
% count lists for the LHS and RHS of an "or" operation, respectively), where the original numbers of attribute value counts are
% given in InAttValCounts.

mergeValCountLists([numVals(AttName, NumGroupsInLHS)|RemainderLHS], OutAttValCountsRHS, InAttValCounts, OutAttValCounts) :-
	select(numVals(AttName, NumGroupsInRHS), OutAttValCountsRHS, RemainderRHS),
	select(numVals(AttName, NumGroupsInOrig), InAttValCounts, RemainderOrig),
	NumGroupsTogether is NumGroupsInLHS + NumGroupsInRHS - ((NumGroupsInLHS / NumGroupsInOrig) * 
		(NumGroupsInRHS / NumGroupsInOrig) * NumGroupsInOrig),
	mergeValCountLists(RemainderLHS, RemainderRHS, RemainderOrig, OutAttValCountsInt),
	append([numVals(AttName, NumGroupsTogether)], OutAttValCountsInt, OutAttValCounts).

mergeValCountLists([], [], [], []).

%********************************************************************************************************************************* 
% RULE THAT IMPLEMENTS PUSHING DOWN SELECTIONS PAST A JOIN
% returns true if (GraphOut, NodesOut) can legally result from pushing some selection operation down into and/or past a join 
% in the query plan represented by (GraphIn, NodesIn) 

transform(GraphIn, NodesIn, CostsIn, GraphOut, NodesOut, CostsOut) :-
	%**** find some selection predicate that is above some join
	select(selection(SelectionNodeID, SelectionPredicateList), NodesIn, IntNodes1), 
	select(join(JoinNodeID, JoinPredicateList), IntNodes1, IntNodes2),
	select(parent(SelectionNodeID, JoinNodeID), GraphIn, IntGraph1),
	%**** find the parent of the selection, as well as the two children of the join
	select(parent(SelectionParentID, SelectionNodeID), IntGraph1, IntGraph2),
	select(parent(JoinNodeID, JoinLHSChildID), IntGraph2, Trash),
	member(parent(JoinNodeID, JoinRHSChildID), Trash), 
	%**** it is the same transformation if we switch the LHS and RHS, so just allow one ordering!
	JoinLHSChildID @> JoinRHSChildID, 
	%**** cut the selection out of the query plan
	append([parent(SelectionParentID, JoinNodeID)], IntGraph2, IntGraph3),
	%**** find all atts that are reachable from either the LHS or the RHS of the join
	allAttsReachable(LHSChildAtts, JoinLHSChildID, GraphIn, NodesIn),
	allAttsReachable(RHSChildAtts, JoinRHSChildID, GraphIn, NodesIn),
	%**** use those attributes to partition all of the predicates in the selection into three subsets: those that can be
	%**** pushed down to the left, those that can be pushed to the right, and those that need to be inside of the join because
	%**** they deal with attributes from both the LHS and the RHS of the join
	partitionPredsOverJoin(SelectionPredicateList, TopPredicateList, LeftPredicateList, RightPredicateList, LHSChildAtts, RHSChildAtts),
	%**** give the join his new predicates	
	append(JoinPredicateList, TopPredicateList, NewJoinPredicateList),
	append([join(JoinNodeID, NewJoinPredicateList)], IntNodes2, IntNodes3),
	%**** add new selection operations on the LHS and the RHS of the join, if needed
	addSelection(JoinLHSChildID, NewLHSChildID, LeftPredicateList, IntGraph3, IntNodes3, IntGraph4, IntNodes4),
	addSelection(JoinRHSChildID, NewRHSChildID, RightPredicateList, IntGraph4, IntNodes4, GraphOut, NodesOut),
	%**** add costing information for the two new nodes, if they were created
	(NewLHSChildID == nothing -> (IntCosts1 = CostsIn); addCostForNewNode(NewLHSChildID, GraphOut, NodesOut, CostsIn, IntCosts1)),
	(NewRHSChildID == nothing -> (IntCosts2 = IntCosts1); addCostForNewNode(NewRHSChildID, GraphOut, NodesOut, IntCosts1, IntCosts2)),
	%**** move the old costing information for the selection down onto the join, and kill the join's old costing info
	superimposeExistingCost(SelectionNodeID, JoinNodeID, IntCosts2, CostsOut).

%*********************************************************************************************************************************
% RULE THAT IMPLEMENTS AN EMPTY TRANSFORMATION THAT DOES NOTHING

transform(GraphIn, NodesIn, CostsIn, GraphIn, NodesIn, CostsIn).

%*********************************************************************************************************************************
% RULE THAT IMPLEMENTS CHANGING JOIN ORDERS
% returns true if (GraphOut, NodesOut) can legally result from taking a sub-plan of the form (A join (B join C)) somewhere in
% (GraphIn, NodesIn), and re-ordering it to (B join (A join C))

transform(GraphIn, NodesIn, CostsIn, GraphOut, NodesOut, CostsOut) :-
	%**** choose a join called TopJoinNodeID, with children BotJoinNodeID and TopLHSNodeID, where BotJoinNodeID is a join
	%**** with children BotLHSNodeID and BotRHSNodeID
	select(join(TopJoinNodeID, TopJoinPredList), NodesIn, IntNodes1), 
	select(parent(TopJoinNodeID, BotJoinNodeID), GraphIn, IntGraph1),
	select(join(BotJoinNodeID, BotJoinPredList), IntNodes1, IntNodes2),
	select(parent(TopJoinNodeID, TopLHSNodeID), IntGraph1, IntGraph2),
	select(parent(BotJoinNodeID, BotLHSNodeID), IntGraph2, IntGraph3),
	select(parent(BotJoinNodeID, BotRHSNodeID), IntGraph3, IntGraph4),
	%**** change who is a parent of who: TopJoinNodeID will now be a parent of BotLHSNodeID and BotJoinNodeID; BotJoinNodeID
	%**** will now be a parent of TopLHSNodeID and BotRHSNodeID
	append([parent(TopJoinNodeID, BotLHSNodeID), parent(BotJoinNodeID, TopLHSNodeID), 
		parent(BotJoinNodeID, BotRHSNodeID), parent(TopJoinNodeID, BotJoinNodeID)], IntGraph4, GraphOut),
	%**** now that we have scrambled up the join order, we have to give the correct predicates to everyone
	allAttsReachable(LHSAtts, BotLHSNodeID, GraphOut, IntNodes2),
	allAttsReachable(RHSAtts, BotJoinNodeID, GraphOut, IntNodes2),
	append(TopJoinPredList, BotJoinPredList, AllJoinPreds),
	partitionPredsOverJoin(AllJoinPreds, NewTopJoinPredList, _, NewBotJoinPredList, LHSAtts, RHSAtts),
	append([join(TopJoinNodeID, NewTopJoinPredList), join(BotJoinNodeID, NewBotJoinPredList)], IntNodes2, NodesOut),
	%**** and recost BotJoinNodeID, since his children have changed
	addCostForNewNode(BotJoinNodeID, GraphOut, NodesOut, CostsIn, CostsOut).	

%********************************************************************************************************************************* 
% RULE THAT CUTS COSTING INFO FOR A REMOVED NODE OUT OF A PLAN
% returns true if, when you cut OntoMe (with parent FromMe) out of a query plan with cost info CostsIn, you get CostsOut 

superimposeExistingCost(FromMe, OntoMe, CostsIn, CostsOut) :-
	select(stats(FromMe, AttCountsToCopy, NumTuplesToCopy), CostsIn, IntCosts1),
	select(stats(OntoMe, _, OldTupleCount), IntCosts1, IntCosts2),
	append([stats(OntoMe, AttCountsToCopy, NumTuplesToCopy)], IntCosts2, IntCosts3),
	select(stats(planRoot, thisIsTheTotalCost, TotCost), IntCosts3, IntCosts4),
	NewTotCost is TotCost - round(OldTupleCount),
	append([stats(planRoot, thisIsTheTotalCost, NewTotCost)], IntCosts4, CostsOut).

%********************************************************************************************************************************* 
% RULE THAT ADDS COSTING INFO FOR A NEW NODE ADDED TO A QUERY PLAN 
% returns true if, when WhichNode is added to the query plan specified by (GraphIn, NodesIn, CostsIn), the new costing info
% is CostsOut.  Note that this can handle the case where the node WhichNode is already present in CostsIn; in this case, the
% old costing info is simply over-written

%**** version that deals with adding a join
addCostForNewNode(WhichNode, GraphIn, NodesIn, CostsIn, CostsOut) :-
	member(join(WhichNode, Preds), NodesIn),
	select(parent(WhichNode, LHSChild), GraphIn, Trash),
	member(parent(WhichNode, RHSChild), Trash),
	LHSChild @> RHSChild,
	member(stats(LHSChild, LHSAttCounts, LHSNumTuples), CostsIn),
	member(stats(RHSChild, RHSAttCounts, RHSNumTuples), CostsIn),
	BaseTuples is LHSNumTuples * RHSNumTuples,
	append(LHSAttCounts, RHSAttCounts, AttValCounts),
	computeSelectivity(Preds, BaseTuples, NumOutputTuples, AttValCounts, OutAttValCounts),
	(member(stats(WhichNode, _, _), CostsIn) -> select(stats(WhichNode, _, OldCosts), CostsIn, IntCosts1); 
	 IntCosts1 = CostsIn, OldCosts is 0),
	append([stats(WhichNode, OutAttValCounts, NumOutputTuples)], IntCosts1, IntCosts2),
	select(stats(planRoot, thisIsTheTotalCost, TotCost), IntCosts2, IntCosts3),
	NewTotCost is TotCost - round(OldCosts) + round(NumOutputTuples),
	append([stats(planRoot, thisIsTheTotalCost, NewTotCost)], IntCosts3, CostsOut).
	
%**** version that deals with adding a selection
addCostForNewNode(WhichNode, GraphIn, NodesIn, CostsIn, CostsOut) :-
	member(selection(WhichNode, Preds), NodesIn),
	member(parent(WhichNode, Child), GraphIn),
	member(stats(Child, AttValCounts, NumTuples), CostsIn),
	computeSelectivity(Preds, NumTuples, NumOutputTuples, AttValCounts, OutAttValCounts),
	(member(stats(WhichNode, _, _), CostsIn) -> select(stats(WhichNode, _, OldCosts), CostsIn, IntCosts1);
	 IntCosts1 = CostsIn, OldCosts is 0),
	append([stats(WhichNode, OutAttValCounts, NumOutputTuples)], IntCosts1, IntCosts2),
	select(stats(planRoot, thisIsTheTotalCost, TotCost), IntCosts2, IntCosts3),
	NewTotCost is TotCost - round(OldCosts) + round(NumOutputTuples),
	append([stats(planRoot, thisIsTheTotalCost, NewTotCost)], IntCosts3, CostsOut).

%*********************************************************************************************************************************
% RULE THAT DESCRIBES HOW TO ADD A SELECTION PREDICATE TO A QUERY PLAN
% returns true if the query plan represented by (NodesOut, GraphOut) is equivalent to the one represented by
% (NodesIn, GraphIn), with the one difference that a new selection operation with predicates SelectionPreds has been
% added above the node AboveMe in the query plan.

addSelection(AboveMe, NewNodeName, SelectionPreds, GraphIn, NodesIn, GraphOut, NodesOut) :-
	length(SelectionPreds, N), N > 0,
	gensym(nodeFoobieMamma, NewNodeName),
	select(parent(ParentNode, AboveMe), GraphIn, IntGraph1),
	append([parent(NewNodeName, AboveMe), parent(ParentNode, NewNodeName)], IntGraph1, GraphOut),
	append([selection(NewNodeName, SelectionPreds)], NodesIn, NodesOut).

addSelection(_, NewNodeName, [], NodesIn, GraphIn, NodesOut, GraphOut) :-
	NodesOut = NodesIn,
	GraphOut = GraphIn,
	NewNodeName = nothing.

%*********************************************************************************************************************************
% RULE THAT DESCRIBES HOW TO PARTITION A LIST OF PREDICATES OVER A JOIN
% returns true if the first param is partitioned so that (1) all boolPreds referring only to LHSChildAtts are found in
% LeftPredicateList (2) all boolPreds referring only to RHSChildAtts are found in RightPredicateList, and (3) all others are
% found in TopPredicateList

partitionPredsOverJoin([Head|Tail], TopPredicateList, LeftPredicateList, RightPredicateList, LHSChildAtts, RHSChildAtts) :-
	(current_predicate(boolPred/2) -> boolPred(Head, AttList); false),
	(isSubset(AttList, LHSChildAtts) -> (append([Head], IntLeftPredicateList, LeftPredicateList),
		IntRightPredicateList = RightPredicateList, IntTopPredicateList = TopPredicateList);
	 isSubset(AttList, RHSChildAtts) -> (append([Head], IntRightPredicateList, RightPredicateList),
		IntLeftPredicateList = LeftPredicateList, IntTopPredicateList = TopPredicateList);
	 (append([Head], IntTopPredicateList, TopPredicateList), IntRightPredicateList = RightPredicateList, IntLeftPredicateList = LeftPredicateList)),
	 partitionPredsOverJoin(Tail, IntTopPredicateList, IntLeftPredicateList, IntRightPredicateList, LHSChildAtts, RHSChildAtts).

partitionPredsOverJoin([], [], [], [], _, _).

%*********************************************************************************************************************************
% RULE THAT DESCRIBES HOW TO DETERMINE ALL ATTRIUTES REACHABLE FROM A GIVEN NODE
% returns true if AllReachable is exactly the set of attributes that can be found be descending the query plan (represented
% by Graph and Nodes) downward from the operation locaed at NodeID

allAttsReachable(AllReachable, NodeID, Graph, Nodes) :-
	setof(AllAtts, ScanNodeID^(member(tableScan(ScanNodeID, AllAtts), Nodes), ancestor(NodeID, ScanNodeID, Graph)), AttList),
	dePartition(AttList, AllReachable).

%*********************************************************************************************************************************
% RULE FOR MERGING ALL OF THE ELEMENTS OF A LIST OF LISTS SO THAT YOU GET A SINGLE LIST
% assuming that the first arg is a list of lists, this returns true if the second arg results from appending all of those lists
% together; for example, dePartition ([[1,2,3],[3],[4,5]], [1,2,3,3,4,5]) is true.

dePartition([], []).

dePartition([Head|Tail], ListOut) :-
	dePartition(Tail, TempList),
	append(Head, TempList, ListOut).
	
%*********************************************************************************************************************************
% RULE FOR DETERMINING IF ONE NODE IS AN ANCESTOR OF ANOTHER IN A GRAPH
% returns true if a node (the first arg) in the query plan (the third arg) is an an ancestor of the second arg

ancestor(Anc, Anc, _).

ancestor(Anc, Desc, Graph) :-
	member(parent(Intermediate, Desc), Graph),
	ancestor(Anc, Intermediate, Graph).
	
%*********************************************************************************************************************************
% RULE FOR DETERMINING WHETHER ONE LIST IS A SUBSET OF ANOTHER
% true if all of the items in the first arg (a list) are containted within the second arg (also a list)

isSubset([], _).

isSubset([Head|Tail], MyList) :-
	member(Head, MyList),
	isSubset(Tail, MyList).

%*********************************************************************************************************************************
% RULE FOR OBTAINING ONLY THE LAST FEW ITEMS IN A LIST
% true if OutList contains exactly the last NumToGet items in the input list

getLastOnes([Head|Tail], OutList, NumToGet) :-
	length(Tail, ListLen),
	NumToGetMinusOne is NumToGet - 1,
	(ListLen == NumToGetMinusOne -> OutList = [Head|Tail];
	 getLastOnes(Tail, OutList, NumToGet)).
