mcs/class/referencesource/System.Data.Entity/System/Data/Mapping/ViewGeneration/CellPartitioner.cs

   1 //---------------------------------------------------------------------
   2 // <copyright file="CellPartioner.cs" company="Microsoft">
   3 //      Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //
   6 // @owner Microsoft
   7 // @backupOwner Microsoft
   8 //---------------------------------------------------------------------
   9
  10
  11 using System.Data.Common.Utils;
  12 using System.Data.Mapping.ViewGeneration.Structures;
  13 using System.Collections.Generic;
  14 using System.Data.Mapping.ViewGeneration.Validation;
  15 using System.Text;
  16 using System.Data.Mapping.Update.Internal;
  17 using System.Collections.ObjectModel;
  18 using System.Data.Metadata.Edm;
  19
  20 namespace System.Data.Mapping.ViewGeneration
  21 {
  22
  23     using CellGroup = Set<Cell>;
  24
  25     // This class is responsible for partitioning cells into groups of cells
  26     // that are related and for which view generation needs to be done together
  27     internal class CellPartitioner : InternalBase
  28     {
  29
  30         #region Constructor
  31         // effects: Creates a partitioner for cells with extra information
  32         // about foreign key constraints
  33         internal CellPartitioner(IEnumerable<Cell> cells, IEnumerable<ForeignConstraint> foreignKeyConstraints)
  34         {
  35             m_foreignKeyConstraints = foreignKeyConstraints;
  36             m_cells = cells;
  37         }
  38         #endregion
  39
  40         #region Fields
  41         private IEnumerable<Cell> m_cells;
  42         private IEnumerable<ForeignConstraint> m_foreignKeyConstraints;
  43         #endregion
  44
  45         #region Available Methods
  46         // effects: Given a list of cells, segments them into multiple
  47         // "groups" such that view generation (including validation) of one
  48         // group can be done independently of another group. Returns the
  49         // groups as a list (uses the foreign key information as well)
  50         internal List<CellGroup> GroupRelatedCells()
  51         {
  52             // If two cells share the same C or S, we place them in the same group
  53             // For each cell, determine the Cis and Sis that it refers
  54             // to. For every Ci (Si), keep track of the cells that Ci is
  55             // contained in. At the end, run through the Cis and Sis and do a
  56             // "connected components" algorithm to determine partitions
  57
  58             // Now form a graph between different cells -- then compute the connected
  59             // components in it
  60             UndirectedGraph<Cell> graph = new UndirectedGraph<Cell>(EqualityComparer<Cell>.Default);
  61
  62             List<Cell> alreadyAddedCells = new List<Cell>();
  63             // For each extent, add an edge between it and all previously
  64             // added extents with which it overlaps
  65
  66             foreach (Cell cell in m_cells)
  67             {
  68                 graph.AddVertex(cell);
  69                 // Add an edge from this cell to the already added cells
  70                 EntitySetBase firstCExtent = cell.CQuery.Extent;
  71                 EntitySetBase firstSExtent = cell.SQuery.Extent;
  72                 foreach (Cell existingCell in alreadyAddedCells)
  73                 {
  74                     EntitySetBase secondCExtent = existingCell.CQuery.Extent;
  75                     EntitySetBase secondSExtent = existingCell.SQuery.Extent;
  76
  77                     // Add an edge between cell and existingCell if
  78                     // * They have the same C or S extent
  79                     // * They are linked via a foreign key between the S extents
  80                     // * They are linked via a relationship
  81                     bool sameExtent = secondCExtent.Equals(firstCExtent) || secondSExtent.Equals(firstSExtent);
  82                     bool linkViaForeignKey = OverlapViaForeignKeys(cell, existingCell);
  83                     bool linkViaRelationship = AreCellsConnectedViaRelationship(cell, existingCell);
  84
  85                     if (sameExtent || linkViaForeignKey || linkViaRelationship)
  86                     {
  87                         graph.AddEdge(existingCell, cell);
  88                     }
  89                 }
  90                 alreadyAddedCells.Add(cell);
  91             }
  92
  93             // Now determine the connected components of this graph
  94             List<CellGroup> result = GenerateConnectedComponents(graph);
  95             return result;
  96         }
  97         #endregion
  98
  99         #region Private Methods
 100
 101         // effects: Returns true iff cell1 is an extent at the end of cell2's
 102         // relationship set or vice versa
 103         private static bool AreCellsConnectedViaRelationship(Cell cell1, Cell cell2)
 104         {
 105             AssociationSet cRelationSet1 = cell1.CQuery.Extent as AssociationSet;
 106             AssociationSet cRelationSet2 = cell2.CQuery.Extent as AssociationSet;
 107             if (cRelationSet1 != null && MetadataHelper.IsExtentAtSomeRelationshipEnd(cRelationSet1, cell2.CQuery.Extent))
 108             {
 109                 return true;
 110             }
 111             if (cRelationSet2 != null && MetadataHelper.IsExtentAtSomeRelationshipEnd(cRelationSet2, cell1.CQuery.Extent))
 112             {
 113                 return true;
 114             }
 115             return false;
 116         }
 117         // effects: Given a graph of cell groups, returns a list of cellgroup
 118         // such that each cellgroup contains all the cells that are in the
 119         // same connected component
 120         private static List<CellGroup> GenerateConnectedComponents(UndirectedGraph<Cell> graph)
 121         {
 122             KeyToListMap<int, Cell> groupMap = graph.GenerateConnectedComponents();
 123
 124             // Run through the list of groups and generate the merged groups
 125             List<CellGroup> result = new List<CellGroup>();
 126             foreach (int setNum in groupMap.Keys)
 127             {
 128                 ReadOnlyCollection<Cell> cellsInComponent = groupMap.ListForKey(setNum);
 129                 CellGroup component = new CellGroup(cellsInComponent);
 130                 result.Add(component);
 131             }
 132             return result;
 133         }
 134
 135         // effects: Returns true iff there is a foreign key constraint
 136         // between cell1 and cell2's S extents
 137         private bool OverlapViaForeignKeys(Cell cell1, Cell cell2)
 138         {
 139             EntitySetBase sExtent1 = cell1.SQuery.Extent;
 140             EntitySetBase sExtent2 = cell2.SQuery.Extent;
 141
 142             foreach (ForeignConstraint constraint in m_foreignKeyConstraints)
 143             {
 144                 if (sExtent1.Equals(constraint.ParentTable) && sExtent2.Equals(constraint.ChildTable) ||
 145                     sExtent2.Equals(constraint.ParentTable) && sExtent1.Equals(constraint.ChildTable))
 146                 {
 147                     return true;
 148                 }
 149             }
 150             return false;
 151         }
 152         #endregion
 153
 154         internal override void ToCompactString(StringBuilder builder)
 155         {
 156             Cell.CellsToBuilder(builder, m_cells);
 157         }
 158     }
 159 }