1 //--------------------------------------------------------------------- 2 // <copyright file="BasicViewGenerator.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 // 6 // @owner Microsoft 7 // @backupOwner Microsoft 8 //--------------------------------------------------------------------- 9 10 namespace System.Data.Mapping.ViewGeneration 11 { 12 using System.Collections.Generic; 13 using System.Data.Common.Utils; 14 using System.Data.Entity; 15 using System.Data.Mapping.ViewGeneration.QueryRewriting; 16 using System.Data.Mapping.ViewGeneration.Structures; 17 using System.Data.Mapping.ViewGeneration.Utils; 18 using System.Data.Mapping.ViewGeneration.Validation; 19 using System.Data.Metadata.Edm; 20 using System.Diagnostics; 21 using System.Linq; 22 using System.Text; 23 24 // This class generates a view for an extent that may contain self-joins 25 // and self-unions -- this can be later simplified or optimized 26 // Output: A cell tree with LeftCellWrappers as nodes connected by Union, IJ, 27 // LOJ, FOJs 28 internal class BasicViewGenerator : InternalBase 29 { 30 31 #region Constructor 32 // effects: Creates a view generator object that can be used to generate views 33 // based on usedCells (projectedSlotMap are useful for deciphering the fields) BasicViewGenerator(MemberProjectionIndex projectedSlotMap, List<LeftCellWrapper> usedCells, FragmentQuery activeDomain, ViewgenContext context, MemberDomainMap domainMap, ErrorLog errorLog, ConfigViewGenerator config)34 internal BasicViewGenerator(MemberProjectionIndex projectedSlotMap, List<LeftCellWrapper> usedCells, FragmentQuery activeDomain, 35 ViewgenContext context, MemberDomainMap domainMap, ErrorLog errorLog, ConfigViewGenerator config) 36 { 37 Debug.Assert(usedCells.Count > 0, "No used cells"); 38 m_projectedSlotMap = projectedSlotMap; 39 m_usedCells = usedCells; 40 m_viewgenContext = context; 41 m_activeDomain = activeDomain; 42 m_errorLog = errorLog; 43 m_config = config; 44 m_domainMap = domainMap; 45 } 46 #endregion 47 48 #region Fields 49 private MemberProjectionIndex m_projectedSlotMap; 50 private List<LeftCellWrapper> m_usedCells; 51 // Active domain comprises all multiconstants that need to be reconstructed 52 private FragmentQuery m_activeDomain; 53 // these two are temporarily needed for checking containment 54 private ViewgenContext m_viewgenContext; 55 private ErrorLog m_errorLog; 56 private ConfigViewGenerator m_config; 57 private MemberDomainMap m_domainMap; 58 #endregion 59 60 #region Properties 61 private FragmentQueryProcessor LeftQP 62 { 63 get { return m_viewgenContext.LeftFragmentQP; } 64 } 65 #endregion 66 67 #region Exposed Methods 68 // effects: Given the set of used cells for an extent, returns a 69 // view to generate that extent CreateViewExpression()70 internal CellTreeNode CreateViewExpression() 71 { 72 // Create an initial FOJ group with all the used cells as children 73 OpCellTreeNode fojNode = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.FOJ); 74 75 // Add all the used cells as children to fojNode. This is a valid 76 // view for the extent. We later try to optimize it 77 foreach (LeftCellWrapper cell in m_usedCells) 78 { 79 LeafCellTreeNode cellNode = new LeafCellTreeNode(m_viewgenContext, cell); 80 fojNode.Add(cellNode); 81 } 82 83 //rootNode = GroupByNesting(rootNode); 84 // Group cells by the "right" extent (recall that we are 85 // generating the view for the left extent) so that cells of the 86 // same extent are in the same subtree 87 CellTreeNode rootNode = GroupByRightExtent(fojNode); 88 89 // Change some of the FOJs to Unions, IJs and LOJs 90 rootNode = IsolateUnions(rootNode); 91 92 // The isolation with Union is different from IsolateUnions -- 93 // the above isolation finds collections of chidren in a 94 // node and connects them by union. The below one only considers 95 // two children at a time 96 rootNode = IsolateByOperator(rootNode, CellTreeOpType.Union); 97 rootNode = IsolateByOperator(rootNode, CellTreeOpType.IJ); 98 rootNode = IsolateByOperator(rootNode, CellTreeOpType.LOJ); 99 if (m_viewgenContext.ViewTarget == ViewTarget.QueryView) 100 { 101 rootNode = ConvertUnionsToNormalizedLOJs(rootNode); 102 } 103 104 return rootNode; 105 } 106 107 #endregion 108 109 #region Private Methods 110 // requires: The tree rooted at cellTreeNode is an FOJ tree of 111 // LeafCellTreeNodes only, i.e., there is an FOJ node with the 112 // children being LeafCellTreeNodes 113 // 114 // effects: Given a tree rooted at rootNode, ensures that cells 115 // of the same right extent are placed in their own subtree below 116 // cellTreeNode. That is, if there are 3 cells of extent A and 2 of 117 // extent B (i.e., 5 cells with an FOJ on it), the resulting tree has 118 // an FOJ node with two children -- FOJ nodes. These FOJ nodes have 2 119 // and 3 children GroupByRightExtent(CellTreeNode rootNode)120 internal CellTreeNode GroupByRightExtent(CellTreeNode rootNode) 121 { 122 // A dictionary that maps an extent to the nodes are from that extent 123 // We want a ref comparer here 124 KeyToListMap<EntitySetBase, LeafCellTreeNode> extentMap = 125 new KeyToListMap<EntitySetBase, LeafCellTreeNode>(EqualityComparer<EntitySetBase>.Default); 126 127 // CR_Meek_Low: method can be simplified (Map<Extent, OpCellTreeNode>, populate as you go) 128 // (becomes self-documenting) 129 // For each leaf child, find the extent of the child and place it 130 // in extentMap 131 foreach (LeafCellTreeNode childNode in rootNode.Children) 132 { 133 // A cell may contain P, P.PA -- we return P 134 // CHANGE_Microsoft_FEATURE_COMPOSITION Need to fix for composition!! 135 EntitySetBase extent = childNode.LeftCellWrapper.RightCellQuery.Extent; // relation or extent to group by 136 Debug.Assert(extent != null, "Each cell must have a right extent"); 137 138 // Add the childNode as a child of the FOJ tree for "extent" 139 extentMap.Add(extent, childNode); 140 } 141 // Now go through the extent map and create FOJ nodes for each extent 142 // Place the nodes for that extent in the newly-created FOJ subtree 143 // Also add the op node for every node as a child of the final result 144 OpCellTreeNode result = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.FOJ); 145 146 foreach (EntitySetBase extent in extentMap.Keys) 147 { 148 OpCellTreeNode extentFojNode = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.FOJ); 149 foreach (LeafCellTreeNode childNode in extentMap.ListForKey(extent)) 150 { 151 extentFojNode.Add(childNode); 152 } 153 result.Add(extentFojNode); 154 } 155 // We call Flatten to remove any unnecessary nestings 156 // where an OpNode has only 1 child. 157 return result.Flatten(); 158 } 159 160 // requires: cellTreeNode has a tree such that all its intermediate nodes 161 // are FOJ nodes only 162 // effects: Converts the tree rooted at rootNode (recursively) in 163 // following way and returns a new rootNode -- it partitions 164 // rootNode's children such that no two different partitions have 165 // any overlapping constants. These partitions are connected by Union 166 // nodes (since there is no overlapping). 167 // Note: Method may modify rootNode's contents and children IsolateUnions(CellTreeNode rootNode)168 private CellTreeNode IsolateUnions(CellTreeNode rootNode) 169 { 170 if (rootNode.Children.Count <= 1) 171 { 172 // No partitioning of children needs to be done 173 return rootNode; 174 } 175 176 Debug.Assert(rootNode.OpType == CellTreeOpType.FOJ, "So far, we have FOJs only"); 177 178 // Recursively, transform the subtrees rooted at cellTreeNode's children 179 for (int i = 0; i < rootNode.Children.Count; i++) 180 { 181 // Method modifies input as well 182 rootNode.Children[i] = IsolateUnions(rootNode.Children[i]); 183 } 184 185 // Different children groups are connected by a Union 186 // node -- the secltion domain of one group is disjoint from 187 // another group's selection domain, i.e., group A1 contributes 188 // tuples to the extent which are disjoint from the tuples by 189 // A2. So we can connect these groups by union alls. 190 // Inside each group, we continue to connect children of the same 191 // group using FOJ 192 OpCellTreeNode unionNode = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.Union); 193 194 // childrenSet keeps track of the children that need to be procesed/partitioned 195 ModifiableIteratorCollection<CellTreeNode> childrenSet = new ModifiableIteratorCollection<CellTreeNode>(rootNode.Children); 196 197 while (false == childrenSet.IsEmpty) 198 { 199 // Start a new group 200 // Make an FOJ node to connect children of the same group 201 OpCellTreeNode fojNode = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.FOJ); 202 203 // Add one of the root's children as a child to the foj node 204 CellTreeNode someChild = childrenSet.RemoveOneElement(); 205 fojNode.Add(someChild); 206 207 // We now want a transitive closure of the overlap between the 208 // the children node. We keep checking each child with the 209 // fojNode and add it as a child of fojNode if there is an 210 // overlap. Note that when a node is added to the fojNode, 211 // its constants are propagated to the fojNode -- so we do 212 // get transitive closure in terms of intersection 213 foreach (CellTreeNode child in childrenSet.Elements()) 214 { 215 if (!IsDisjoint(fojNode, child)) 216 { 217 fojNode.Add(child); 218 childrenSet.RemoveCurrentOfIterator(); 219 // To ensure that we get all overlapping node, we 220 // need to restart checking all the children 221 childrenSet.ResetIterator(); 222 } 223 } 224 // Now we have a group of children nodes rooted at 225 // fojNode. Add this fojNode to the union 226 unionNode.Add(fojNode); 227 } 228 229 // The union node as the root of the view 230 CellTreeNode result = unionNode.Flatten(); 231 return result; 232 } 233 234 /// <summary> 235 /// Traverse the tree and perform the following rewrites: 236 /// 1. Flatten unions contained as left children of LOJs: LOJ(A, Union(B, C)) -> LOJ(A, B, C). 237 /// 2. Rewrite flat LOJs into nested LOJs. The nesting is determined by FKs between right cell table PKs. 238 /// Example: if we have an LOJ(A, B, C, D) and we know there are FKs from C.PK and D.PK to B.PK, 239 /// we want to rewrite into this - LOJ(A, LOJ(B, C, D)). 240 /// 3. As a special case we also look into LOJ driving node (left most child in LOJ) and if it is an IJ, 241 /// then we consider attaching LOJ children to nodes inside IJ based on the same principle as above. 242 /// Example: LOJ(IJ(A, B, C), D, E, F) -> LOJ(IJ(LOJ(A, D), B, LOJ(C, E)), F) iff D has FK to A and E has FK to C. 243 /// 244 /// This normalization enables FK-based join elimination in plan compiler, so for a query such as 245 /// "select e.ID from ABCDSet" we want plan compiler to produce "select a.ID from A" instead of 246 /// "select a.ID from A LOJ B LOJ C LOJ D". 247 /// </summary> ConvertUnionsToNormalizedLOJs(CellTreeNode rootNode)248 private CellTreeNode ConvertUnionsToNormalizedLOJs(CellTreeNode rootNode) 249 { 250 // Recursively, transform the subtrees rooted at rootNode's children. 251 for (int i = 0; i < rootNode.Children.Count; i++) 252 { 253 // Method modifies input as well. 254 rootNode.Children[i] = ConvertUnionsToNormalizedLOJs(rootNode.Children[i]); 255 } 256 257 // We rewrite only LOJs. 258 if (rootNode.OpType != CellTreeOpType.LOJ || rootNode.Children.Count < 2) 259 { 260 return rootNode; 261 } 262 263 // Create the resulting LOJ node. 264 var result = new OpCellTreeNode(m_viewgenContext, rootNode.OpType); 265 266 // Create working collection for the LOJ children. 267 var children = new List<CellTreeNode>(); 268 269 // If rootNode looks something like ((V0 IJ V1) LOJ V2 LOJ V3), 270 // and it turns out that there are FK associations from V2 or V3 pointing, let's say at V0, 271 // then we want to rewrite the result as (V1 IJ (V0 LOJ V2 LOJ V3)). 272 // If we don't do this, then plan compiler won't have a chance to eliminate LOJ V2 LOJ V3. 273 // Hence, flatten the first child or rootNode if it's IJ, but remember that its parts are driving nodes for the LOJ, 274 // so that we don't accidentally nest them. 275 OpCellTreeNode resultIJDriver = null; 276 HashSet<CellTreeNode> resultIJDriverChildren = null; 277 if (rootNode.Children[0].OpType == CellTreeOpType.IJ) 278 { 279 // Create empty resultIJDriver node and add it as the first child (driving) into the LOJ result. 280 resultIJDriver = new OpCellTreeNode(m_viewgenContext, rootNode.Children[0].OpType); 281 result.Add(resultIJDriver); 282 283 children.AddRange(rootNode.Children[0].Children); 284 resultIJDriverChildren = new HashSet<CellTreeNode>(rootNode.Children[0].Children); 285 } 286 else 287 { 288 result.Add(rootNode.Children[0]); 289 } 290 291 // Flatten unions in non-driving nodes: (V0 LOJ (V1 Union V2 Union V3)) -> (V0 LOJ V1 LOJ V2 LOJ V3) 292 foreach (var child in rootNode.Children.Skip(1)) 293 { 294 var opNode = child as OpCellTreeNode; 295 if (opNode != null && opNode.OpType == CellTreeOpType.Union) 296 { 297 children.AddRange(opNode.Children); 298 } 299 else 300 { 301 children.Add(child); 302 } 303 } 304 305 // A dictionary that maps an extent to the nodes that are from that extent. 306 // We want a ref comparer here. 307 var extentMap = new KeyToListMap<EntitySet, LeafCellTreeNode>(EqualityComparer<EntitySet>.Default); 308 // Note that we skip non-leaf nodes (non-leaf nodes don't have FKs) and attach them directly to the result. 309 foreach (var child in children) 310 { 311 var leaf = child as LeafCellTreeNode; 312 if (leaf != null) 313 { 314 EntitySetBase extent = GetLeafNodeTable(leaf); 315 if (extent != null) 316 { 317 extentMap.Add((EntitySet)extent, leaf); 318 } 319 } 320 else 321 { 322 if (resultIJDriverChildren != null && resultIJDriverChildren.Contains(child)) 323 { 324 resultIJDriver.Add(child); 325 } 326 else 327 { 328 result.Add(child); 329 } 330 } 331 } 332 333 // We only deal with simple cases - one node per extent, remove the rest from children and attach directly to result. 334 var nonTrivial = extentMap.KeyValuePairs.Where(m => m.Value.Count > 1).ToArray(); 335 foreach (var m in nonTrivial) 336 { 337 extentMap.RemoveKey(m.Key); 338 foreach (var n in m.Value) 339 { 340 if (resultIJDriverChildren != null && resultIJDriverChildren.Contains(n)) 341 { 342 resultIJDriver.Add(n); 343 } 344 else 345 { 346 result.Add(n); 347 } 348 } 349 } 350 Debug.Assert(extentMap.KeyValuePairs.All(m => m.Value.Count == 1), "extentMap must map to single nodes only."); 351 352 // Walk the extents in extentMap and for each extent build PK -> FK1(PK1), FK2(PK2), ... map 353 // where PK is the primary key of the left extent, and FKn(PKn) is an FK of a right extent that 354 // points to the PK of the left extent and is based on the PK columns of the right extent. 355 // Example: 356 // table tBaseType(Id int, c1 int), PK = (tBaseType.Id) 357 // table tDerivedType1(Id int, c2 int), PK1 = (tDerivedType1.Id), FK1 = (tDerivedType1.Id -> tBaseType.Id) 358 // table tDerivedType2(Id int, c3 int), PK2 = (tDerivedType2.Id), FK2 = (tDerivedType2.Id -> tBaseType.Id) 359 // Will produce: 360 // (tBaseType) -> (tDerivedType1, tDerivedType2) 361 var pkFkMap = new KeyToListMap<EntitySet, EntitySet>(EqualityComparer<EntitySet>.Default); 362 // Also for each extent in extentMap, build another map (extent) -> (LOJ node). 363 // It will be used to construct the nesting in the next step. 364 var extentLOJs = new Dictionary<EntitySet, OpCellTreeNode>(EqualityComparer<EntitySet>.Default); 365 foreach (var extentInfo in extentMap.KeyValuePairs) 366 { 367 var principalExtent = extentInfo.Key; 368 foreach (var fkExtent in GetFKOverPKDependents(principalExtent)) 369 { 370 // Only track fkExtents that are in extentMap. 371 System.Collections.ObjectModel.ReadOnlyCollection<LeafCellTreeNode> nodes; 372 if (extentMap.TryGetListForKey(fkExtent, out nodes)) 373 { 374 // Make sure that we are not adding resultIJDriverChildren as FK dependents - we do not want them to get nested. 375 if (resultIJDriverChildren == null || !resultIJDriverChildren.Contains(nodes.Single())) 376 { 377 pkFkMap.Add(principalExtent, fkExtent); 378 } 379 } 380 } 381 var extentLojNode = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.LOJ); 382 extentLojNode.Add(extentInfo.Value.Single()); 383 extentLOJs.Add(principalExtent, extentLojNode); 384 } 385 386 // Construct LOJ nesting inside extentLOJs based on the information in pkFkMap. 387 // Also, track nested extents using nestedExtents. 388 // Example: 389 // We start with nestedExtents empty extentLOJs as such: 390 // tBaseType -> LOJ(BaseTypeNode) 391 // tDerivedType1 -> LOJ(DerivedType1Node)* 392 // tDerivedType2 -> LOJ(DerivedType2Node)** 393 // Note that * and ** represent object references. So each time something is nested, 394 // we don't clone, but nest the original LOJ. When we get to processing the extent of that LOJ, 395 // we might add other children to that nested LOJ. 396 // As we walk pkFkMap, we end up with this: 397 // tBaseType -> LOJ(BaseTypeNode, LOJ(DerivedType1Node)*, LOJ(DerivedType2Node)**) 398 // tDerivedType1 -> LOJ(DerivedType1Node)* 399 // tDerivedType2 -> LOJ(DerivedType2Node)** 400 // nestedExtens = (tDerivedType1, tDerivedType2) 401 var nestedExtents = new Dictionary<EntitySet, EntitySet>(EqualityComparer<EntitySet>.Default); 402 foreach (var m in pkFkMap.KeyValuePairs) 403 { 404 var principalExtent = m.Key; 405 foreach (var fkExtent in m.Value) 406 { 407 OpCellTreeNode fkExtentLOJ; 408 if (extentLOJs.TryGetValue(fkExtent, out fkExtentLOJ) && 409 // make sure we don't nest twice and we don't create a cycle. 410 !nestedExtents.ContainsKey(fkExtent) && !CheckLOJCycle(fkExtent, principalExtent, nestedExtents)) 411 { 412 extentLOJs[m.Key].Add(fkExtentLOJ); 413 nestedExtents.Add(fkExtent, principalExtent); 414 } 415 } 416 } 417 418 // Now we need to grab the LOJs that have not been nested and add them to the result. 419 // All LOJs that have been nested must be somewhere inside the LOJs that have not been nested, 420 // so they as well end up in the result as part of the unnested ones. 421 foreach (var m in extentLOJs) 422 { 423 if (!nestedExtents.ContainsKey(m.Key)) 424 { 425 // extentLOJ represents (Vx LOJ Vy LOJ(Vm LOJ Vn)) where Vx is the original node from rootNode.Children or resultIJDriverChildren. 426 var extentLOJ = m.Value; 427 if (resultIJDriverChildren != null && resultIJDriverChildren.Contains(extentLOJ.Children[0])) 428 { 429 resultIJDriver.Add(extentLOJ); 430 } 431 else 432 { 433 result.Add(extentLOJ); 434 } 435 } 436 } 437 438 return result.Flatten(); 439 } 440 GetFKOverPKDependents(EntitySet principal)441 private static IEnumerable<EntitySet> GetFKOverPKDependents(EntitySet principal) 442 { 443 foreach (var pkFkInfo in principal.ForeignKeyPrincipals) 444 { 445 // If principal has a related extent with FK pointing to principal and the FK is based on PK columns of the related extent, 446 // then add it. 447 var pkColumns = pkFkInfo.Item2.ToRole.GetEntityType().KeyMembers; 448 var fkColumns = pkFkInfo.Item2.ToProperties; 449 if (pkColumns.Count == fkColumns.Count) 450 { 451 // Compare PK to FK columns, order is important (otherwise it's not an FK over PK). 452 int i = 0; 453 for (; i < pkColumns.Count && pkColumns[i].EdmEquals(fkColumns[i]); ++i); 454 if (i == pkColumns.Count) 455 { 456 yield return pkFkInfo.Item1.AssociationSetEnds.Where(ase => ase.Name == pkFkInfo.Item2.ToRole.Name).Single().EntitySet; 457 } 458 } 459 } 460 } 461 GetLeafNodeTable(LeafCellTreeNode leaf)462 private static EntitySet GetLeafNodeTable(LeafCellTreeNode leaf) 463 { 464 return leaf.LeftCellWrapper.RightCellQuery.Extent as EntitySet; 465 } 466 CheckLOJCycle(EntitySet child, EntitySet parent, Dictionary<EntitySet, EntitySet> nestedExtents)467 private static bool CheckLOJCycle(EntitySet child, EntitySet parent, Dictionary<EntitySet, EntitySet> nestedExtents) 468 { 469 do 470 { 471 if (EqualityComparer<EntitySet>.Default.Equals(parent, child)) 472 { 473 return true; 474 } 475 } 476 while (nestedExtents.TryGetValue(parent, out parent)); 477 return false; 478 } 479 480 // requires: opTypeToIsolate must be LOJ, IJ, or Union 481 // effects: Given a tree rooted at rootNode, determines if there 482 // are any FOJs that can be replaced by opTypeToIsolate. If so, 483 // does that and a returns a new tree with the replaced operators 484 // Note: Method may modify rootNode's contents and children IsolateByOperator(CellTreeNode rootNode, CellTreeOpType opTypeToIsolate)485 internal CellTreeNode IsolateByOperator(CellTreeNode rootNode, CellTreeOpType opTypeToIsolate) 486 { 487 Debug.Assert(opTypeToIsolate == CellTreeOpType.IJ || opTypeToIsolate == CellTreeOpType.LOJ 488 || opTypeToIsolate == CellTreeOpType.Union, 489 "IsolateJoins can only be called for IJs, LOJs, and Unions"); 490 491 List<CellTreeNode> children = rootNode.Children; 492 if (children.Count <= 1) 493 { 494 // No child or one child - do nothing 495 return rootNode; 496 } 497 498 // Replace the FOJs with IJs/LOJs/Unions in the children's subtrees first 499 for (int i = 0; i < children.Count; i++) 500 { 501 // Method modifies input as well 502 children[i] = IsolateByOperator(children[i], opTypeToIsolate); 503 } 504 // Only FOJs and LOJs can be coverted (to IJs, Unions, LOJs) -- 505 // so if the node is not that, we can ignore it (or if the node is already of 506 // the same type that we want) 507 if (rootNode.OpType != CellTreeOpType.FOJ && rootNode.OpType != CellTreeOpType.LOJ || 508 rootNode.OpType == opTypeToIsolate) 509 { 510 return rootNode; 511 } 512 513 // Create a new node with the same type as the input cell node type 514 OpCellTreeNode newRootNode = new OpCellTreeNode(m_viewgenContext, rootNode.OpType); 515 516 // We start a new "group" with one of the children X - we create 517 // a newChildNode with type "opTypeToIsolate". Then we 518 // determine if any of the remaining children should be in the 519 // same group as X. 520 521 // childrenSet keeps track of the children that need to be procesed/partitioned 522 ModifiableIteratorCollection<CellTreeNode> childrenSet = new ModifiableIteratorCollection<CellTreeNode>(children); 523 524 // Find groups with same or subsumed constants and create a join 525 // or union node for them. We do this so that some of the FOJs 526 // can be replaced by union and join nodes 527 // 528 while (false == childrenSet.IsEmpty) 529 { 530 // Start a new "group" with some child node (for the opTypeToIsolate node type) 531 532 OpCellTreeNode groupNode = new OpCellTreeNode(m_viewgenContext, opTypeToIsolate); 533 CellTreeNode someChild = childrenSet.RemoveOneElement(); 534 groupNode.Add(someChild); 535 536 // Go through the remaining children and determine if their 537 // constants are subsets/equal/disjoint w.r.t the joinNode 538 // constants. 539 540 foreach (CellTreeNode child in childrenSet.Elements()) 541 { 542 // Check if we can add the child as part of this 543 // groupNode (with opTypeToIsolate being LOJ, IJ, or Union) 544 if (TryAddChildToGroup(opTypeToIsolate, child, groupNode)) 545 { 546 childrenSet.RemoveCurrentOfIterator(); 547 548 // For LOJ, suppose that child A did not subsume B or 549 // vice-versa. But child C subsumes both. To ensure 550 // that we can get A, B, C in the same group, we 551 // reset the iterator so that when C is added in B's 552 // loop, we can reconsider A. 553 // 554 // For IJ, adding a child to groupNode does not change the range of it, 555 // so there is no need to reconsider previously skipped children. 556 // 557 // For Union, adding a child to groupNode increases the range of the groupNode, 558 // hence previously skipped (because they weren't disjoint with groupNode) children will continue 559 // being ignored because they would still have an overlap with one of the nodes inside groupNode. 560 561 if (opTypeToIsolate == CellTreeOpType.LOJ) 562 { 563 childrenSet.ResetIterator(); 564 } 565 } 566 } 567 // The new Union/LOJ/IJ node needs to be connected to the root 568 newRootNode.Add(groupNode); 569 } 570 return newRootNode.Flatten(); 571 } 572 573 // effects: Determines if the childNode can be added as a child of the 574 // groupNode using te operation "opTypeToIsolate". E.g., if 575 // opTypeToIsolate is inner join, we can add child to group node if 576 // childNode and groupNode have the same multiconstantsets, i.e., they have 577 // the same selection condition 578 // Modifies groupNode to contain groupNode at the appropriate 579 // position (for LOJs, the child could be added to the beginning) TryAddChildToGroup(CellTreeOpType opTypeToIsolate, CellTreeNode childNode, OpCellTreeNode groupNode)580 private bool TryAddChildToGroup(CellTreeOpType opTypeToIsolate, CellTreeNode childNode, 581 OpCellTreeNode groupNode) 582 { 583 switch (opTypeToIsolate) 584 { 585 case CellTreeOpType.IJ: 586 // For Inner join, the constants of the node and 587 // the child must be the same, i.e., if the cells 588 // are producing exactly same tuples (same selection) 589 if (IsEquivalentTo(childNode, groupNode)) 590 { 591 groupNode.Add(childNode); 592 return true; 593 } 594 break; 595 596 case CellTreeOpType.LOJ: 597 // If one cell's selection condition subsumes 598 // another, we can use LOJ. We need to check for 599 // "subsumes" on both sides 600 if (IsContainedIn(childNode, groupNode)) 601 { 602 groupNode.Add(childNode); 603 return true; 604 } 605 else if (IsContainedIn(groupNode, childNode)) 606 { 607 // child subsumes the whole group -- add it first 608 groupNode.AddFirst(childNode); 609 return true; 610 } 611 break; 612 613 case CellTreeOpType.Union: 614 // If the selection conditions are disjoint, we can use UNION ALL 615 // We cannot use active domain here; disjointness is guaranteed only 616 // if we check the entire selection domain 617 if (IsDisjoint(childNode, groupNode)) 618 { 619 groupNode.Add(childNode); 620 return true; 621 } 622 break; 623 } 624 return false; 625 } 626 IsDisjoint(CellTreeNode n1, CellTreeNode n2)627 private bool IsDisjoint(CellTreeNode n1, CellTreeNode n2) 628 { 629 bool isQueryView = (m_viewgenContext.ViewTarget == ViewTarget.QueryView); 630 631 bool isDisjointLeft = LeftQP.IsDisjointFrom(n1.LeftFragmentQuery, n2.LeftFragmentQuery); 632 633 if (isDisjointLeft && m_viewgenContext.ViewTarget == ViewTarget.QueryView) 634 { 635 return true; 636 } 637 638 CellTreeNode n = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.IJ, n1, n2); 639 bool isDisjointRight = n.IsEmptyRightFragmentQuery; 640 641 if (m_viewgenContext.ViewTarget == ViewTarget.UpdateView && 642 isDisjointLeft && !isDisjointRight) 643 { 644 645 if (ErrorPatternMatcher.FindMappingErrors(m_viewgenContext, m_domainMap, m_errorLog)) 646 { 647 return false; 648 } 649 650 651 StringBuilder builder = new StringBuilder(Strings.Viewgen_RightSideNotDisjoint(m_viewgenContext.Extent.ToString())); 652 builder.AppendLine(); 653 654 //Retrieve the offending state 655 FragmentQuery intersection = LeftQP.Intersect(n1.RightFragmentQuery, n2.RightFragmentQuery); 656 if (LeftQP.IsSatisfiable(intersection)) 657 { 658 intersection.Condition.ExpensiveSimplify(); 659 RewritingValidator.EntityConfigurationToUserString(intersection.Condition, builder); 660 } 661 662 //Add Error 663 m_errorLog.AddEntry(new ErrorLog.Record(true, ViewGenErrorCode.DisjointConstraintViolation, 664 builder.ToString(), m_viewgenContext.AllWrappersForExtent, String.Empty)); 665 666 ExceptionHelpers.ThrowMappingException(m_errorLog, m_config); 667 668 669 return false; 670 } 671 672 return (isDisjointLeft || isDisjointRight); 673 } 674 IsContainedIn(CellTreeNode n1, CellTreeNode n2)675 private bool IsContainedIn(CellTreeNode n1, CellTreeNode n2) 676 { 677 // Decide whether to IJ or LOJ using the domains that are filtered by the active domain 678 // The net effect is that some unneeded multiconstants will be pruned away in IJ/LOJ 679 // It is desirable to do so since we are only interested in the active domain 680 FragmentQuery n1Active = LeftQP.Intersect(n1.LeftFragmentQuery, m_activeDomain); 681 FragmentQuery n2Active = LeftQP.Intersect(n2.LeftFragmentQuery, m_activeDomain); 682 683 bool isContainedLeft = LeftQP.IsContainedIn(n1Active, n2Active); 684 685 if (isContainedLeft) 686 { 687 return true; 688 } 689 690 CellTreeNode n = new OpCellTreeNode(m_viewgenContext, CellTreeOpType.LASJ, n1, n2); 691 bool isContainedRight = n.IsEmptyRightFragmentQuery; 692 693 return isContainedRight; 694 } 695 IsEquivalentTo(CellTreeNode n1, CellTreeNode n2)696 private bool IsEquivalentTo(CellTreeNode n1, CellTreeNode n2) 697 { 698 return IsContainedIn(n1, n2) && IsContainedIn(n2, n1); 699 } 700 701 #endregion 702 703 #region String methods ToCompactString(StringBuilder builder)704 internal override void ToCompactString(StringBuilder builder) 705 { 706 // We just print the slotmap for now 707 m_projectedSlotMap.ToCompactString(builder); 708 } 709 #endregion 710 } 711 } 712