Restructuring view maintenance system and method

BACKGROUND OF THE INVENTION

[0001] 1. The Field of the Invention

[0002] The present invention relates to the maintenance of replicated data within databases. More specifically, the present invention relates to manners of maintaining data integrity within database tables having heterogeneous schemas.

[0003] 2. The Relevant Technology

[0004] Information replication frequently occurs in modem database usage. An entity or organization may have access to various tables or “relations” within a one or more databases. The various tables may contain partially or fully replicated information. That is, the information or “data” within different tables may be equivalent. Additionally, the various tables may exhibit heterogeneous formatting, or “schemas.” That is, the information within the various tables may be organized into different combinations of relations, rows, and columns, possibly with different relation names, row names, and columns. Such tables are referred to herein as being “restructuring views” of each other.

[0005] Tables containing replicated data may occur naturally. That is, the various tables exist for independent purposes. For instance, separate departments of an organization may individually maintain their own data or tables within a common database. However, the data that is populated within the various tables may originate from a common source. Separate databases that contain replicated information and heterogeneous schemas may also exist at different locations within a particular organization. Replicated information may also be generated and maintained by different organizations within separate databases that are commonly available over large scale networks such as the Internet.

[0006] In another scenario, data may also be replicated in multiple tables for research purposes. A first table or “base table” is generally a naturally occurring database. Other tables may be replicated as subsets of the first table. The replications often take the form of views. A view is a mechanism employed by database languages, such as SQL, that may act as a filter. A view may show only a portion of the data in the table to the user.

[0007] Views, as abbreviated forms of the tables, can be searched more quickly than the full table or set of tables. A view may be created every time it is referenced. A view may also be “materialized” and exist in a persistent form.

[0008] Generally, when data is replicated, such as for research purposes, integrity is maintained through the use of materialized views. A multiple database system (MDBS), in which materialized views are used for research and complex querying, is known as a data warehouse. Various tools for managing such data warehouses exist, one example of which is IBM's DataJoiner® product.

[0009] It may be a primary objective in designing database systems to expedite query servicing (i.e. reduce query latencies) by optimizing the query system. The use of materialized views is one manner in which the art has approached query optimization. It is often the case that certain materialized views can be more efficiently accessed for certain types of queries while others are more efficient for other types of queries. Thus, one technique for speeding up query servicing is to maintain a plurality of materialized views and to selectively direct queries to the appropriate materialized view for which the query can be most rapidly serviced.

[0010] A further development in the art of MDBS management is the addition of certain management tools to database languages such as SQL. One such tool is SchemaSQL. SchemaSQL is a proposed extension to the SQL language that promotes efficient manipulation and classification of materialized views. For instance, SchemaSQL provides “view definitions,” which allow one materialized view to be mapped to another.

[0011] Conventional management and querying of views presumes that the views exhibit a common schema. Nevertheless, as discussed above, many naturally occurring multiple database systems include databases having heterogeneous schemas. Additionally, tables that are restructuring views of each other may, as discussed, be created for research purposes. Accordingly, many database systems include base tables and replicated tables that are restructuring views of those tables. While the prior art provides manners of maintaining standard materialized views, no provisions have been made for maintaining tables that are restructuring views of each other.

[0012] Accordingly, a need exists for a manner of maintaining database tables that are restructuring views of each other. Such a maintenance system, to be most advantageous, should be easily implemented with existing technology and noninvasive to the MDBS on which it is intended to operate. Such a maintenance system and its method of use are disclosed herein.

OBJECTS AND BRIEF SUMMARY OF THE INVENTION

[0013] The apparatus of the present invention has been developed in response to the present state of the art, and in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available view maintenance systems. Thus, it is an overall objective of the present invention to provide a view maintenance system and method for a database management system that is capable of maintaining materialized views that are restructuring views of one or more base tables.

[0014] To achieve the foregoing object, and in accordance with the invention as embodied and broadly described herein in the preferred embodiment, a system for incremental maintenance of replicated information between a base table and a target table that are restructured representations of each other is provided. In the embodiments provided herein, the system includes: a monitoring module that receives notification of base table modifications; a consultation module that consults the base table about the nature of the base table modifications in response notification by the monitoring module; and a conversion module that receives the nature of the modifications from the consultation module and propagates the base table modifications into the target table, including propagating base table metadata changes into the target table.

[0015] In one embodiment, the base table and the target table are restructuring views of each other and are configured with heterogeneous schemas. Additionally, the system may include a mapping module configured to map the base table into the target table using various operators including without limitation fold operators, unfold operators, split operators, and unite operators.

[0016] The conversion module may also determine which mapping operators were used in mapping the base table to the target table and select a set of propagation operations to be used in propagating the base table modifications to the target table. For example, when the base table is mapped to the target table using a split operator, the set of propagation operations may include an insert operation, a create target table operation, a move row operation, an update operation, a delete operation, and a drop all target tables operation.

[0017] Another class of mapping operators supported in accordance with the invention are unite operators. In situations where restructuring views of the base table and the target table are related by a unite operator the conversion module may select a set of propagating operations such as an insert operation, an update operation, a delete operation, an update corresponding rows operation, and a delete corresponding rows operation.

[0018] Fold and unfold mapping operators are also supported in accordance with the invention. When the restructuring views of the base table and the target table are related by fold operators, the conversion module may select a set of propagating operations such as inserting, updating, and deleting a set of corresponding rows as well as inserting, updating, renaming, and deleting columns. One unfold mapping operator in accordance with the invention corresponds with a set of propagating operations that includes without limitation an insert column operation, an update row operation, an insert row operation, a set corresponding value to null operation, and a delete column operation.

[0019] An attendant method of for incremental maintenance of replicated information between a base table and a target table that are restructured representations of each other is also disclosed herein, and in certain embodiments comprises: receiving notification of modifications to the base table, including modifications to metadata of the base table; consulting the base table about the nature of the modifications to the base table in response to receipt of notification by the monitoring module; receiving the nature of the modifications; and propagating the modifications into the target table, including propagating changes to the metadata of the base table into the target table.

[0020] In one embodiment, the base table and the target table are restructuring views of each and have schemas that are heterogeneous.

[0021] The method may further comprise mapping the base table into the target table using an operator selected from the group consisting of a fold operator, an unfold operator, a split operator, and a unite operator.

[0022] The step of propagating the modifications into the target table may further comprise determining which of the operators were used in mapping the base table to the target table and selecting operations for propagating the modifications to the target table based upon the particular operator originally used.

[0023] The step of propagating the modifications into the target table may also comprise propagating the modifications to the target table according to the nature of the modifications to the base table, including selecting an operation from among a split operation, an insert operation, an update operation, and a delete operation.

[0024] The step of propagating the modifications into the target table further may also comprise selecting a propagation operation to propagate the modifications to the target table according to the nature of the modifications to the base table, the propagation operation selected from the group consisting of an insert operation, an update operation, a delete operation, a renaming relation operation; and a drop table operation.

[0025] These and other objects, features, and advantages of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.

BRIEF DESCRIPTION OF THE DRAWINGS

[0026] In order that the manner in which the above-recited and other advantages and objects of the invention are obtained will be readily understood, a more particular description of the invention briefly described above will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments of the invention and are not therefore to be considered to be limiting of its scope, the invention will be described and explained with additional specificity and detail through the use of the accompanying drawings in which:

[0027]FIG. 1 is a schematic block diagram illustrating one embodiment of a computer system for use with the present invention.

[0028]FIG. 2 is a schematic block diagram illustrating one embodiment of a database management program suitable for implementing the maintenance system and method of the present invention.

[0029]FIG. 2<i>a </i>is a schematic block diagram illustrating a maintenance module of the present invention.

[0030]FIG. 3 illustrates four database tables that are restructuring views of each other.

[0031]FIG. 4 depicts four schematic flow chart diagrams, illustrating respectively a fold is operation, an unfold operation, a split operation, and a unite operation.

[0032]FIG. 5 is a schematic block diagram illustrating one embodiment of a MDBS system and a schema mapping of the MDBS system.

[0033]FIG. 5<i>a </i>illustrates a canonical database table.

[0034]FIG. 6 is a schematic flow chart diagram illustrating a maintenance method of the present invention.

[0035]FIG. 7 is a schematic flow chart diagram illustrating one embodiment of a mapping operation of the present invention.

[0036]FIGS. 8<i>a </i>through <b>8</b><i>d </i>are schematic flow chart diagrams illustrating manners of converting changes on a base table to tables that are restructuring views of the base table.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0037] The presently preferred embodiments of the present invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. It will be readily understood that the components of the present invention, as generally described and illustrated in the figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the apparatus, system, and method of the present invention, as represented in FIGS. 1 through 6<i>d</i>, is not intended to limit the scope of the invention, as claimed, but is merely representative of presently preferred embodiments of the invention.

[0038]FIGS. 1 through 6<i>d </i>are schematic block diagrams and flow chart diagrams which illustrate in more detail the preferred embodiments of the present invention. The schematic block diagrams illustrate certain embodiments of modules for performing various functions of the present invention. In general, the represented modules include therein executable and operational data for operation within a computer system of FIG. 1 in accordance with the present invention.

[0039] As used herein, the term module or subsystem are intended to include any type of computer instructions and computer executable code that may be located within a memory device and/or transmitted as electronic signals over a system bus or network. An identified module of executable code may, for instance, be organized as an object, procedure, or function. Nevertheless, the instructions of an identified module need not be located together, but may comprise disparate instructions stored in different locations which together comprise the module and achieve the purpose stated for the module. Indeed, a module could be a single software instruction, or many instructions, and may even be distributed over several different code segments, among different programs, and across several memory devices.

[0040] Similarly, operational data may be identified and illustrated herein within modules, and may be embodied in any suitable form and organized within any suitable type of data structure. The operational data may be collected as a single data set, or may be distributed over different locations including over different storage devices, and may at least partially exist merely as electronic signals on a system bus or network.

[0041]FIG. 1 is a schematic block diagram that illustrates a computer system <b>10</b> in which executable and operational data, operating in accordance with the present invention, may be hosted on one or more computer stations <b>12</b> in a network <b>14</b>. The network <b>14</b> may comprise a wide area network (WAN) and may also comprise an interconnected system of networks, one particular example of which is the Internet and the World Wide Web supported on the Internet.

[0042] A typical computer station <b>12</b> may include a processor or CPU <b>16</b>. The CPU <b>16</b> may be operably connected to one or more memory devices <b>18</b>. The memory devices <b>18</b> are depicted as including a non-volatile storage device <b>20</b> such as a hard disk drive or CD ROM drive, a read-only memory (ROM) <b>22</b>, and a random access volatile memory (RAM) <b>24</b>.

[0043] The computer station <b>12</b> or system <b>10</b> in general may also include one or more input devices <b>26</b> for receiving inputs form a user or form another device. Similarly, one or more output devices <b>28</b> may be provided within or be accessible from the computer system <b>10</b>. A network port such as a network interface card <b>30</b> may be provided for connecting to outside devices through the network <b>14</b>. In the case where the network <b>14</b> is remote from the computer station, the network interface card <b>30</b> may comprise a modem, and may connect to the network <b>14</b> through a local access line such as a telephone line.

[0044] Within any given station <b>12</b>, a system bus <b>32</b> may operably interconnect the CPU <b>16</b>, the memory devices <b>18</b>, the input devices <b>26</b>, the output devices <b>28</b> the network card <b>30</b>, and one or more additional ports <b>34</b>. The system bus <b>32</b> and a network backbone <b>36</b> may be thought of as data carriers. As such, the system bus <b>32</b> and the network backbone <b>36</b> may be embodied in numerous configurations. For instance, wire, fiber optic line, wireless electromagnetic communications by visible light, infrared, and radio frequencies may be implemented as appropriate.

[0045] In general, the network <b>14</b> may comprise a single local network (LAN), a wide area network (WAN), several adjoining networks, an intranet, or as in the manner depicted, a system of interconnected networks such as the Internet <b>40</b>. The individual stations <b>12</b> communicate with each other over the backbone <b>36</b> and/or over the Internet <b>40</b> with varying degrees and types of communications capabilities and logic capability. The individual stations <b>12</b> may include a mainframe computer on which the modules of the present invention may be hosted.

[0046] Different communication protocols, e.g., ISO/OSI, IPX, TCP/IP, may be used on the network, but in the case of the Internet, a single, layered communications protocol (TCP/IP) generally enables communications between the differing networks <b>14</b> and stations <b>12</b>. Thus, a communication link may exist, in general, between any of the stations <b>12</b>.

[0047] The stations <b>12</b> connected on the network <b>14</b> may comprise application servers <b>42</b>, is and/or other resources or peripherals <b>44</b>, such as printers and scanners. Other networks may be in communication with the network <b>14</b> through a router <b>38</b> and/or over the Internet <b>40</b>.

[0048] The database maintenance system and method of the present invention may be implemented within a database management system. For the purposes of understanding the invention, a database management system capable of generating and querying tables that are restructuring views of each other will first be explained.

[0049] Referring now to FIG. 2, a multi-database system (MDBS) <b>50</b> that may be used in the implementation of the present invention in one embodiment includes a plurality of modules containing executable code and operational data suitable for execution by the CPU and for operation within the memory devices <b>18</b> of FIG. 1. Of course, the memory devices <b>18</b> in which the modules of the present invention are located may also be distributed across both local and remote computer stations <b>12</b>.

[0050] The MDBS <b>50</b> is shown in FIG. 2 comprising a central database management program (central program) <b>52</b> operating in conjunction with a plurality of database systems <b>54</b>, each having one or more database tables <b>58</b>. The database systems <b>54</b> may be local to the central program <b>52</b>, existing on a common hard disk drive <b>20</b> within a common computer station <b>12</b>. Alternatively, the database systems <b>54</b> may be remote to the central program <b>52</b>, communicating across a remote link <b>56</b>. The remote link <b>56</b> may comprise a network <b>14</b> (of FIG. 1) which may be a LAN or a WAN. The remote link <b>56</b> may also comprise a more global communication network, such as the Internet <b>40</b>. While an example is given where the database tables <b>58</b> are within separate database systems <b>54</b>, the tables <b>58</b> could be part of a common database program or system.

[0051] Each of the database systems <b>54</b> is preferably provided with a management module <b>60</b> that is configured for conducting such tasks as user interface, maintenance, query response, and the like. Within the database systems <b>54</b> may also be provided a catalog <b>80</b>, is as will be discussed below. Examples of database systems <b>54</b> with which the central program <b>52</b> may communicate include Sybase™, Informix™, Oracle™, and SQL Server™, SQL Anywhere™, Terradata™, and IBM's DB2™ in its various forms and configurations.

[0052] The central database management program <b>52</b> may be a single database management program such as IBM's DB2™, or may be a linking and communicating program that allows a user at a central location to communicate with a plurality of database systems, regardless of where the databases are located. Preferably, the central program <b>52</b> is also configured to allow a user to communicate with different types of database systems <b>54</b> in a federated environment, and to conduct operations upon the database systems <b>54</b>. These operations may include, for example, generation or maintenance of tables within the database systems <b>54</b>, maintenance, and communications such as querying the database systems <b>54</b>. One example of a central database management program <b>52</b>, given by way of example, is DataJoiner™, distributed by IBM Corporation of Rochester, N.Y.

[0053] The MDBS <b>50</b> as shown in FIG. 2 communicates with a plurality of database tables <b>58</b> that may be tables within one or more common databases, or may be within separate database systems <b>54</b> as depicted. The database tables <b>58</b> include a base table <b>58</b><i>a</i>, a first restructuring view table (RV<b>2</b>) <b>58</b><i>b</i>, a second restructuring view table (RV<b>2</b>) <b>58</b><i>c</i>, and a third restructuring view table (RV<b>3</b>) <b>58</b><i>d</i>. The restructuring view tables RV<b>1</b>, RV<b>2</b>, and RV<b>3</b> are all restructuring views of the base table, containing identical data, but having heterogenous schema, as discussed above. The restructuring views RVl, RV<b>2</b>, and RV<b>3</b> may be naturally occurring, or may have been created for improving query efficiency, research, data mining or the like. In one embodiment, the restructuring views RV<b>1</b>, RV<b>2</b>, and RV<b>3</b> are generated by the restructuring view creation module <b>70</b> using schema mapping operators as will be discussed.

[0054] In the depicted embodiment, the central program <b>52</b> comprises an interface module <b>62</b> for allowing a human user to interact with the central program <b>52</b>. Also shown is a communication module <b>64</b> for effecting communications with the database systems <b>54</b>, a management module <b>66</b> for managing interactions between the different database systems <b>54</b>, a restructuring view creation module <b>70</b> for creating restructuring views of a base table, and a maintenance module <b>72</b> for maintaining a consistency of contents of the database tables <b>58</b>. Additionally, in the depicted embodiment, the management program <b>52</b> comprises a query processing module <b>74</b> for efficiently querying the various database tables <b>58</b> and a catalog <b>76</b> listing information regarding the various database tables <b>58</b>.

[0055] The query processing module <b>74</b> may be configured to receive a query from a user through the user interface module <b>62</b> and to transmit the query to the relevant database systems <b>54</b> to answer the query. In a further embodiment, the query processing module <b>74</b> is also configured to optimize the query into an optimized query plan that accesses the requested data efficiently. One example of a manner of configuring a query processing module is described in our copending patent application Ser. No. 09/412,034 filed on Oct. 4, 1999 for Query Optimization System and Method, which is hereby incorporated by reference into this document.

[0056] The catalog <b>76</b> in one embodiment contains information <b>88</b> regarding each of the communicating database systems <b>54</b>. For instance, a mapping of each database table <b>58</b> may be stored within the catalog <b>76</b>. Other information regarding the schema, contents, database system type, and the like may also be stored within the catalog <b>76</b>.

[0057] The maintenance module <b>72</b> is preferably configured with a monitoring module <b>104</b>, a consultation module <b>106</b>, a conversion module <b>108</b>, and a mapping module <b>102</b>. The operation of the maintenance module <b>72</b> will be discussed in greater detail with reference to FIG. 2<i>a</i>. As shown in FIG. 2<i>a</i>, one embodiment of a mapping module <b>102</b> comprises a plurality of restructuring operators <b>112</b>, a middleware schema <b>114</b>, and a schema mapping module <b>116</b>.

[0058] In one embodiment of the present invention, the mapping module <b>102</b> is used to express a schema mapping of the database tables <b>58</b>. The schema mapping may be in the form of view definitions <b>126</b> which, in one embodiment, comprise view definitions under the proposed addition to the SQL language entitled SchemaSQL, which is discussed below.

[0059] The schema mapping may be used in order to generate the restructuring views <b>58</b><i>b</i>, <b>58</b><i>c</i>, <b>58</b><i>d </i>by restructuring the base table <b>58</b><i>a</i>. The schema mapping may also be achieved with the use of the operators <b>112</b> which represent and implement the various operations involved in restructuring a base table to a restructuring view and vice verse. In one embodiment, the view definitions <b>126</b> employ the operators <b>112</b> to express the schema mapping of the database tables <b>58</b>. One example of the employment of the operators <b>112</b> is shown in FIG. 4 and is discussed below in greater detail.

[0060] In one embodiment, the schema mapping achieved by the mapping module <b>102</b> employs a middleware schema <b>114</b> that functions as a central point in the conversions between a base table and a restructuring view. In the depicted embodiment, the middleware schema <b>114</b> comprises a canonical schema <b>115</b> which may be used to map the base table to a canonical table <b>117</b>.

[0061] The canonical table <b>117</b> is devised of data which is partially or fully equivalent to the data of the database tables <b>58</b> of the MDBS <b>50</b>. Additionally, the canonical table <b>117</b> has a schema which is either equivalent to or a restructuring view of each database <b>58</b> of the MDBS <b>50</b>. Preferably, the canonical schema module <b>115</b> devises and references the canonical table <b>117</b> , but does not materialize the canonical table <b>117</b>. The canonical table <b>117</b> and the canonical schema in general are discussed below in greater detail.

DATABASE EXAMPLES

[0062]FIG. 3 shows a MDBS <b>170</b> containing four representative database tables <b>170</b> which will be used throughout this discussion as examples. The database tables <b>170</b> may or may not correspond to the database tables <b>58</b> of FIG. 2. Of course, only a portion of the database tables <b>170</b> are represented, in order to show the particular schemas of the databases. The database tables <b>170</b> are restructuring views of each other, and as such, any of the database tables <b>170</b> can be treated as the base table or the restructuring views. In the given example, all of the database tables <b>170</b> are naturally occurring within a stock brokerage and are generated from a feeder database and a common set of data. Accordingly, the database tables <b>170</b> contain identical data, but express the data with heterogeneous schemas which are restructuring views of each other.

[0063] A risk-analysis department database <b>172</b> is shown configured with an ibm relation <b>174</b> and a msft relation <b>184</b>. A research department database <b>180</b> is shown with an ibm relation and a msft relation. A traders department database <b>186</b> is shown with an ag<b>007</b> relation <b>188</b> and anag<b>0</b>o<b>8</b> relation <b>190</b>. A profit-loss department database <b>192</b> is shown with a single relation, a buysell relation <b>194</b>.

[0064] Each of the database tables <b>170</b> of FIG. 3 comprises a table name <b>196</b>, one or more relations <b>198</b>, relation names <b>199</b>, columns <b>200</b>, column names or attributes <b>202</b>, rows <b>204</b>, and column data <b>206</b>.

SchemaSQL

[0065] As the MDBS <b>50</b> of FIG. 2 may employ the proposed SchemaSQL extension of the SQL language, it is helpful to discuss the semantics and syntax of the SchemaSQL language in greater detail. A more elaborate treatment of the language including its formal semantics and giving numerous illustrative examples is found in Subbu I. N. Subramanian, A Foundation for Integrating Heterogeneous Data Sources. PhD thesis, Department of Computer Science, Concordia University, Montreal, Canada 1997. The discussion herein references Table 1, which lists queries directed to the various representative database tables <b>170</b> of FIG. 3. <tables id="TABLE-US-00001" num="1"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><thead><row><entry /><entry namest="OFFSET" nameend="1" align="center">TABLE 1</entry></row><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>select distinct A</entry></row><row><entry /><entry>from risk-analysis −&gt; S, risk-analysis::S −&gt; A</entry></row><row><entry /><entry>where A &lt; &gt; “date” and A &lt; &gt; “xaction”</entry></row><row><entry /><entry>(Q1)</entry></row><row><entry /><entry>select distinct T.agent</entry></row><row><entry /><entry>from research −&gt; S, research::S T</entry></row><row><entry /><entry>(Q2)</entry></row><row><entry /><entry>select distinct A</entry></row><row><entry /><entry>from traders −&gt; A</entry></row><row><entry /><entry>(Q3)</entry></row><row><entry /><entry>select distinct T.agent</entry></row><row><entry /><entry>from profit-loss::buysell T</entry></row><row><entry /><entry>(Q4)</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row><row><entry /><entry namest="OFFSET" nameend="1" align="left"><!--footnotes removed--></entry></row></tbody></tgroup></table></tables>

[0066] SQL queries allow variable declaration over the tuples in a relation. In contrast, SchemaSQL permits the declaration of variables that can range over (1) names of the relations in a database, (2) names of the attributes in a relation, and (3) values appearing in a column corresponding to a given attribute in a relation, in addition to tuple variables allowed in SQL. Variable declarations in SchemaSQL follows the same syntax as &lt;range&gt; &lt;var&gt; in SQL, where &lt;var&gt; is any identifier.

[0067] Table 1 shows the query “List names of all agents” expressed as SchemaSQL queries on the brokerage databases of FIG. 3. The simplest of them all is the query Q<b>4</b> on the profit-loss database. In query Q<b>4</b>, T is a tuple variable that ranges over the buysell relation. The SchemaSQL syntax requires specifying the database name of the relation. Apart from this minor variation, query Q<b>4</b> is also a SQL query.

[0068] Query Q<b>3</b> on the traders database, on the other hand, is a SchemaSQL query that makes use of a relation name variable to list the names of all the agents. Note that the agent names appear as relation names in the traders database. In query Q<b>3</b>, the declaration traders-&gt; A declares A as a variable that ranges over the relation names. In the research database, the agent names appear under the agent column across all the stock relations.

[0069] Query Q<b>2</b> captures this by declaring a relation variable, and A as an attribute name variable that ranges over the attribute names of the stock relations (risk-analysis::S-&gt;A) with the provision that it does not range over the column names that are not agent names (captured by the where clause).

[0070] Besides querying, SchemaSQL also has the ability to define restructuring views of the data in databases that catapult data values to schema name positions and vice verse. For example, the brokerage firm databases of FIG. 1 can all be represented as SchemaSQL views of one another. In the following section of the restructuring operators are introduced and defined using generic SchemaSQL view definitions.

Restructuring Operators

[0071]FIG. 4 contains schematic flow charts (a) through (d) illustrating embodiments of the basic operation of the operators <b>112</b> of FIG. 2. Flowchart (a) illustrates a fold operation <b>210</b>. Flowchart (b) illustrates an unfold operation <b>230</b>. Flowchart (c) illustrates a split operation <b>250</b>, and flowchart (d) illustrates an unfold operation <b>270</b>.

[0072] The fold operator <b>74</b> can be characterized as folding column names into column data. The column names in the input relation on which the fold operator acts appear as column values in the output relation. For example, the SchemaSQL view definition V<b>2</b> of table 2 below captures the ibm relation of the research database as a view of the ibm relation of the risk-analysis database. The fold operator <b>74</b> in one embodiment accomplishes a fold operation <b>210</b> of FIG. 4.

[0073] Referring to FIG. 4, the fold operation <b>210</b> will be discussed in terms of an input table and a transformed output table. The fold operation <b>210</b> starts at step <b>212</b> and progresses to a step <b>214</b> in which the processor <b>16</b> receives a SchemaSQL or other suitable view definition <b>82</b> embodying instructions for implementing the fold operation. At a step <b>216</b>, in accordance with the view definition <b>82</b>, a new relation is created based upon the input table and is provided with an additional column obtained from the create view clause.

[0074] At a step <b>218</b>, column names from the input table are placed in the new column as column data. At a step <b>220</b>, new rows are created to contain the data within previously within the columns which are being folded. At a step <b>222</b>, the folded column data is placed in the new rows. At a step <b>224</b>, the operation ends.

[0075] The risk-analysis department table <b>172</b> and research department table <b>180</b> of FIG. 3 illustrate one example of the fold operation <b>210</b>. Applying the fold operation <b>210</b> to the risk-analysis department table <b>172</b> results in the reformation to the research department table <b>180</b>. Specified column names <b>202</b> of the risk-analysis department table <b>172</b> are folded into column data <b>206</b> in the research department table <b>180</b>.

[0076] The fold operation <b>210</b> can also be expressed in a particular example as a generic a SchemaSQL definition in which, C1, C2, etc., denote distinct individual column names, &lt;C&gt; denotes a set of column names, and X, Y, T, A, etc. denote distinct variables. The view definition is as follows:

[0077] create view db::rel′ (C1, C2, &lt;C&gt;) as

[0078] select X, Y, T. &lt;C&gt;

[0079] from db::rel T. db::rel-&gt; X, T.X Y

[0080] where preserveConditions (X)

[0081] In this definition, C1, C2 are not equivalent to &lt;C&gt;. We call C1 the foldOn column and C2 the foldBy column. The set of columns &lt;C&gt; is called the PRESERVE-d columns. The preserveConditions (X) statement ensures that the PRESERVE-d columns indeed get preserved in the output schema.

[0082] The unfold operator <b>78</b> is the inverse of the fold operator <b>74</b>. The unfold operator <b>78</b> transports the column values in the input relation into column name positions in the output relation in an information preserving manner. For example, the relation ibm of the risk-analysis database in FIG. 3(<i>i</i>) is an unfold-ed representation of the relation ibm of the research database, FIG. 3(<i>ii</i>). This is because agents appear as column values in the latter database, and appear as column names in the former. The unfold operator <b>78</b> may be characterized by the unfold operation <b>230</b> of FIG. 4.

[0083] The unfold operation <b>230</b> starts at a step <b>232</b> and progresses to a step <b>234</b> where the processor <b>16</b> receives a SchemaSQL or other suitable view definition embodying instructions for implementing the unfold operation. In accordance with the view definition, at a step <b>236</b>, column data from a specified column of the input relation are transformed into column names and placed in the output relation. At a step <b>238</b>, data from rows in which each data transformed to attributes appeared is placed in rows with data from a specified column of the input relation appearing as column data for the new columns of the output relation. The unfold operation ends at a step <b>240</b>.

[0084] The risk-analysis department table <b>172</b> and research department table <b>180</b> of FIG. 3 also illustrate an example of the unfold operation <b>230</b>. Applying the unfold operation <b>230</b> to the research department table <b>180</b> results in a reformation to the risk-analysis department table <b>172</b>. The unfold operation <b>230</b> results in specified column values in the input relation, the research department table <b>180</b> being transported into column name positions in the output relation, the risk-analysis department table <b>172</b>.

[0085] The unfold operation <b>230</b> can also be expressed in a particular example as a generic SchemaSQL definition in which, C1, C2, etc., denote distinct individual column names, &lt;C&gt; denotes a set of column names, and X, Y, T, A, etc. denote distinct variables. The view definition is as follows:

[0086] create view db::rel′ (X, &lt;C&gt;) as

[0087] select Y,T. &lt;C&gt;

[0088] from db::rel T, T.C1 X, T.C2 Y

[0089] In this relation, C1, C2 are note equivalent to &lt;C&gt;. We call C1 the unfoldOn column and C2 the unfoldby column. The set of columns represented by &lt;C&gt; are the preserve-d columns. In the example V<b>1</b> in Table 2 below, the unfoldOn column is agent and the unfoldBy column is value. Date and xaction are the preserve-d columns.

[0090] The split operator restructures a specified relation into a set of relations whose names are obtained from specified column values in the original relation. For example, the agent<b>007</b> and agent <b>008</b> relations <b>188</b>, <b>190</b> of the traders database in FIG. 3(<i>iii</i>) is a split rendering of the stock_trades relation of FIG. 9. One embodiment of the manner of operation of the split operator <b>76</b> is illustrated by the split operation <b>250</b> FIG. 4.

[0091] The split operation <b>250</b> starts at a step <b>252</b> and progresses to a step <b>254</b> in which the processor <b>16</b> receives a SchemaSQL or other suitable view definition embodying instructions for implementing the split operation. In accordance with the view definition, at a step <b>256</b>, the new relations that are to be created are specified in the view definition, which may be entered as a parameter by a user. At a step <b>258</b>, specified column names are transformed to relation names. At a step <b>262</b>, rows corresponding to the input relation column data placed as column names in the output relation are placed into the output relation. The split operation <b>250</b> ends at a step <b>264</b>.

[0092] The traders department table <b>186</b> and profit-loss department table <b>192</b> of FIG. 3 also illustrate an example of the split operation <b>250</b>. Applying the split operation <b>250</b> to the profit-loss department table <b>192</b> results in a reformation to the traders department table <b>186</b>. The split operation <b>250</b> results in a restructuring of the buysell relation <b>194</b> into a set of relations ag<b>007</b> (<b>188</b>), and ag<b>008</b> (<b>190</b>) whose names are obtained from column values <b>206</b> in the original relation, buysell <b>194</b>.

[0093] The split operation <b>250</b> can also be expressed in a particular example as a generic SchemaSQL definition in which, C1, C2 etc., denote distinct individual column names, &lt;C&gt; denotes a set of column names, and X, Y, T, A, etc. denote distinct variables. The view definition is as follows:

[0094] create view db::X (!C?) As

[0095] select R. !C?

[0096] From db::rel R, R. Cl X

[0097] In this relation, we call C1 the splitOn column. All the relations in db not affected by the split operator are called the preserve-d relations. In the example view definition V<b>3</b> in Table 2 below, agent is the splitOn column. Assuming that there are no other relations in db, the set of preserve-d relations is the empty set. A unique characteristic of the split operator, compared to the other restructuring operators and the classical relational algebra operators is that, it takes a single relation as input and generates a set of relations as output. The split operator is the only operator in the present invention that produces a set of relations as output. Due to the nature of the split operator, a restructuring-view in general can be a set of relations in a database.

[0098] The unite operator <b>80</b> is the inverse of split operator <b>76</b>. The unite operator has the effect of combining several relations conforming to the same schema into a single relation, so that the relation names of the input relations appear in the data position in the transformed schema. For example, the stock_trades relation of FIG. 9 is a result of the unite operator applied on the agent relations of the traders database in FIG. 3(<i>iii</i>). The unite operator <b>80</b> in one embodiment performs the unite operation <b>270</b> of FIG. 4.

[0099] The unite operation <b>270</b> starts at a step <b>272</b>. At a step <b>274</b>, the processor <b>16</b> receives a SchemaSQL or other suitable view definition embodying instructions for implementing the split operation. In accordance with the view definition, at a step <b>276</b>, an output relation is created with a new column with a column name specified by the user, possibly through a parameter call or in response to a prompt.

[0100] At a step <b>278</b>, specified relation names from the input relation are placed in the output relation in the new column. At a step <b>280</b>, data rows for each occurrence of the new column name from the input relation are placed in the output relation. The unfold operation <b>270</b> ends at a step <b>282</b>.

[0101] The traders department table <b>186</b> and profit-loss department table <b>192</b> of FIG. 3 also illustrate an example of the unite operation <b>270</b>. Applying the unite operation <b>270</b> to the traders department table <b>186</b> results in a reformation to the profit-loss department table <b>192</b>. The unite operation <b>270</b> results in a combining of specified relations, ag<b>007</b> (<b>188</b>) and ag<b>008</b> (<b>190</b>) into a single relation, buysell <b>194</b>, so that the relation names ag<b>007</b>, ag<b>008</b> appear in the data position <b>206</b> in the transformed profit-loss department table <b>192</b>.

[0102] The unite operation <b>270</b> can also be expressed in a particular example as a generic SchemaSQL definition in which, C1, C2, etc. denote distinct individual column names, &lt;C&gt; denotes a set of column names, and X, Y, T, A, etc. denote distinct variables. The view definition is as follows:

[0103] create view db::rel′ (C1, &lt;C&gt;)

[0104] select X, T.&lt;C&gt;

[0105] from db-&gt; X, X T

[0106] where preserveConditions (X)

[0107] In this view definition, we call C1 the uniteon column. We call the complement of the set of relations in the database on which unite acts as the preserve-d relations. The preserveConditions (X) conditions ensure that the PRESERVE-d relations indeed get preserved in the output database. In example V4 of Table 2 below, the uniteon column is agent. All relations of the traders database participate in the unite operator. So the set of PRESERVE-d relations is the empty set. <tables id="TABLE-US-00002" num="2"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="35PT" align="left" /><colspec colname="1" colwidth="182PT" align="left" /><thead><row><entry /><entry namest="OFFSET" nameend="1" align="center">TABLE 2</entry></row><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>create view</entry></row><row><entry /><entry>risk-analysis::ibm (date, xaction, A) as</entry></row><row><entry /><entry>select I.date, I.xation, V</entry></row><row><entry /><entry>from research::ibm I, I.agent A, I.value V</entry></row><row><entry /><entry>(V1)</entry></row><row><entry /><entry>create view</entry></row><row><entry /><entry>research::ibm (date, xaction, agent, value) as</entry></row><row><entry /><entry>from risk-analysis::ibm I,</entry></row><row><entry /><entry>risk-analysis::ibm−&gt;A, I.A V</entry></row><row><entry /><entry>where A! =′date′ and A!= ′xaction′</entry></row><row><entry /><entry>(V2)</entry></row><row><entry /><entry>create view</entry></row><row><entry /><entry>traders::A(date, stock, xaction, value) as</entry></row><row><entry /><entry>select R.date, R.stock, R.xaction, R.value</entry></row><row><entry /><entry>from db::stock_trades R, R.agent A</entry></row><row><entry /><entry>(V3)</entry></row><row><entry /><entry>create view</entry></row><row><entry /><entry>db::stock_trades (date, stock, agent, xaction, value) as</entry></row><row><entry /><entry>select T.date, T.stock, A, T.xaction,</entry></row><row><entry /><entry>T value</entry></row><row><entry /><entry>from traders −&gt; A, A T</entry></row><row><entry /><entry>(V4)</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

Examples Illustrating the Restructuring Operations

[0108] Table 3 is a listing of the restructuring transformation among the database tables <b>58</b> of FIG. 3. The preserve information for Split and Unite is the empty set in this example. <tables id="TABLE-US-00003" num="3"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="70PT" align="left" /><colspec colname="2" colwidth="84PT" align="left" /><colspec colname="3" colwidth="63PT" align="left" /><thead><row><entry namest="1" nameend="3" align="center">TABLE 3</entry></row><row><entry /></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry>Source (db/rel)</entry><entry>Restructuring Expression</entry><entry>Destination</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>research::ibm</entry><entry>unfold on agent by value</entry><entry>risk-analysis::ibm</entry></row><row><entry /><entry>preserve date, xaction</entry></row><row><entry>risk-analysis::ibm</entry><entry>fold on agent by value</entry><entry>research::ibm</entry></row><row><entry /><entry>preserve date, xaction</entry></row><row><entry>profit-loss::buysell</entry><entry>fold on xaction by value</entry><entry>traders</entry></row><row><entry /><entry>preserve date, stock, agent;</entry></row><row><entry /><entry>split on agent</entry></row><row><entry>traders</entry><entry>unite on agent;</entry><entry>p r o f i t -</entry></row><row><entry /><entry /><entry>loss::buysell</entry></row><row><entry /><entry>unfold on xaction by value</entry></row><row><entry /><entry>preserve date, stock, agent</entry></row><row><entry>research</entry><entry>unite on stock;</entry><entry>traders</entry></row><row><entry /><entry>split on agent</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

MDBS Architecture

[0109]FIG. 5 represents one embodiment of a MDBS data management architecture <b>300</b> suitable for use with the query optimization system <b>50</b> of FIG. 1. Also shown in FIG. 5 is a schema mapping module <b>322</b> for mapping restructuring views <b>316</b>, <b>318</b>, <b>320</b> from one or more base tables <b>302</b>, <b>304</b>, <b>306</b>. Whereas the restructuring views <b>170</b> of FIG. 3 are naturally occurring, FIG. 5 illustrates an arrangement that may occur within data warehouses. The restructuring view creation module <b>70</b> of FIG. 2 may, in one embodiment, employ the schema mapping module <b>322</b> in generating database tables that are restructuring views of a base table.

[0110] As discussed, the MDBS <b>50</b> may be implemented using IBM's DataJoiner™ product. DataJoiner is a heterogeneous database system that provides a single database image of multiple databases and provides transparent access to tables at remote databases through user defined aliases that can be accessed as local tables. DataJoiner is also a fully functional relational database system. Queries submitted to the MDBS are optimized using a cost based optimizer that has knowledge of the remote optimizer capabilities to generate an optimal global plan.

[0111] In FIG. 5, the schema mapping module <b>322</b> is used to transform the base tables <b>302</b>, <b>304</b>, <b>306</b> into restructuring views <b>316</b>, <b>318</b>, <b>320</b>. In so doing, a mapping <b>308</b>, <b>310</b> is first generated capable of transforming the base tables into the canonical schema. From the canonical schema <b>312</b>, <b>314</b>, the base tables <b>302</b>, <b>304</b>, <b>306</b> are transformed into restructuring views <b>316</b>, <b>318</b>, <b>320</b>. The system is preferably managed by a system such as DataJoiner™ which implements the query optimization system <b>50</b> of FIG. 2 to promote rapid querying and analysis of data within the base tables <b>302</b>, <b>304</b>, <b>306</b>.

Canonical Schema

[0112] The restructuring operators of the previous section, by blurring the distinction between data and meta-data, provide a framework where seamless mapping and querying of both data and schema is possible. From a practical perspective, the need for querying schema components arises because the tokens that the application treats as data appears as a schema component in the database. The notion of canonical schema introduced in this section is based on the observation that if all the objects of query-able interest are modeled as data, the application can express its queries in any first-order query language (such as SQL) and would not need the capability for metadata querying. Thus, canonical schema is a central component in one embodiment of a query processing architecture suitable for use with the present invention.

[0113] The canonical schema of the present invention is the same as the first-order schema presented in Miller R. J., Using Schematically Heterogeneous Structures, published in: In Proceedings of the ACM SIGMOD Conference, pages 189-200, Seattle, Wash., May 1998. We first define the canonical schema and then present a result that brings out the power of the restructuring operators.

Definition of Canonical Schema.

[0114] Given a set of queries Q, a relational schema S is called a canonical schema relative to Q if all queries Q can be expressed as first-order queries on S. For example, the schema of the relation Stock_trades of FIG. 9 is a canonical schema relative to the queries we have considered so far in this paper because all objects of query-able interest, namely date, stock, agent, xaction, and value, are modeled as data. We now present the following theorem that establishes the power of the restructuring algebra.

[0115] Let V be a restructuring-view, Q be a set of queries on V, and S be a canonical schema relative to Q. There exist expressions τ, τ′ consisting only of the restructuring operators such that for every instance V_Ion V,

[0116] (1) τ(V I)=S_Iis an instance of S,

[0117] (2) τ′ (S_I)=V_Iand

[0118] (3) S_Isatisfies the following property:

[0119] ∀ Q ε Q, there exists a first-order query Q′ on S such that Q(V_I)≡Q′ (S_I)

[0120] Proof Sketch: There are two parts of this proof. The first part proves that the transformation has the ability to restructure a schema to a canonical schema and back. The proof is based on the observation that the operators retain the canonical schema information every step of the way. The second part proves that the transformation is performed in an information preserving manner. The proof for the this draws on the semantics of SchemaSQL. The details are presented in Miller.

[0121]FIG. 5<i>a </i>shows one embodiment of a canonical table <b>426</b> presented as a representative example of the canonical table <b>92</b> of FIG. 2. The canonical table <b>426</b> is entitled stock_trades. The stock_trades canonical table <b>426</b> of FIG. 5<i>a </i>is generated based upon the restructuring views tables <b>170</b> of FIG. 3.

[0122] Referring now to FIG. 6, one method of maintaining a MDBS having one or more database tables that are restructuring views of each other will now be described. The method <b>350</b> begins at a start step <b>352</b> and progresses to a step <b>354</b> in which the subject database tables are mapped. One embodiment wherein the MDBS comprises the MDBS <b>50</b> of FIG. 2 will be given herein as an example. In accordance with this embodiment, the restructuring view database tables <b>58</b><i>b</i>, <b>58</b><i>c</i>, and <b>58</b><i>c </i>are mapped to the base table <b>58</b><i>a</i>. This may be conducted manually, but is in one embodiment conducted automatically by a mapping module such as the mapping module <b>102</b> of FIGS. 2 and 2<i>a</i>. FIG. 6<i>a </i>describes one manner of automatically mapping a restructuring view to a base table.

[0123] Referring momentarily to FIG. 6<i>a</i>, the mapping step <b>354</b> may be conducted as a method starting at a start step <b>380</b>. At a step <b>382</b>, the restructuring view table and the base table are examined to determine the differences in the schemas thereof. Once the differences are obtained, those differences are characterized. In so doing, the method <b>354</b> initially checks, as indicated by a step <b>384</b>, whether the differences indicate that a split has occurred. This inquiry may take the form of checking whether data in one column of one table has been transformed to a relation name in the restructuring view table. For example, the traders department table <b>186</b> is a split representation of the profit-loss department table <b>192</b>. If a split has occurred, the mapping is defined using the split operator at a step <b>386</b>.

[0124] At a step <b>388</b>, the method <b>354</b> checks to see if a unite has occurred. This inquiry may take the form of checking whether relation names in the base table have been transformed to column data in the target database. For example, the profit-loss department table <b>192</b> is a split representation of the traders department table <b>186</b>. If a unite has occurred, the mapping is defined using a unite operator at a step <b>390</b>.

[0125] At a step <b>392</b>, the method <b>354</b> checks to see if a fold has occurred. This inquiry may take the form of checking whether column names in the base database have been moved to column data in the target database. For instance, the research department table <b>180</b> is a folded representation of the risk-analysis department table <b>172</b>. If a fold has occurred, the mapping is defined using a fold operator at a step <b>394</b>.

[0126] At a step <b>396</b>, the method <b>354</b> checks to see if an unfold has occurred. This may take the form of checking whether column data in the base table have been moved to column names in the target table. For instance, the risk-analysis department table <b>172</b> is an unfolded representation of the research department table <b>180</b>. If an unfold has occurred, the mapping is defined using an unfold operator at a step <b>397</b>.

[0127] At a step <b>398</b>, a SQL view definition is generated using the operators as determined in the above steps. The SQL view definitions are preferably similar to those discussed above, and maybe combinations of definitions where more than a single operator is used to describe a single mapping. The method <b>354</b> ends at a step <b>399</b>, and is preferably conducted for each restructuring view in the MDBS. The mapping is preferably stored within the MDBS, and in one embodiment, within the information <b>88</b> of the catalog <b>76</b> of the central database management program <b>52</b> of FIG. 2.

[0128] Returning to FIG. 6, once the restructuring view tables are mapped to the base table at the step <b>354</b>, the method <b>350</b> progresses to a step <b>356</b> where changes to the base table are continually monitored. This is conducted in one embodiment with a monitoring module such as the monitoring module <b>104</b> of FIG. 2. The monitoring may be conducted using triggers programmed into the base table as is known in the art. The triggers inform the monitoring module every time there has been a change to data in the base table, and in a preferred embodiment, also every time there has been a change to metadata of the base table.

[0129] Of course, where the restructuring views or multiple base tables are separate databases subject to change independent of the others, and it is wished to maintain a consistency of data within the tables, each table may be monitored by a program such as the central database management program <b>52</b> and the changes noted and propagated into all of the corresponding tables as will be discussed.

[0130] At a step <b>358</b>, notification of a change is received by the monitoring module. At a step <b>360</b>, the change is investigated to determine the exact nature of the change. In one embodiment, this is conducted using a consultation module such as the consultation module <b>106</b> of FIGS. 2 and 2<i>a</i>. The consultation module preferably consults a log within the base table <b>38</b> (the table in which the change occurs, though of course, any of the tables <b>38</b> could be the subject of the change) which lists modifications to the base table <b>58</b>. In one embodiment, the log is contained within a catalog <b>80</b> of the base table.

[0131] At a step <b>362</b>, the mapping between the restructuring view <b>58</b><i>a</i>, <b>58</b><i>b</i>, <b>58</b><i>c </i>being updated and the base table <b>58</b><i>a </i>is fetched. This may comprise retrieving the mapping from the information <b>88</b> stored within the catalog for the restructuring view. Once again, any of the restructuring view tables may comprise a base table in an embodiments such as that of FIG. 3 where each table is a restructuring view of the others, and changes to any of the tables could be made to the rest of the changes using the method of the present invention.

[0132] As indicated at a step <b>364</b>, for each change noted within the log and located at the step <b>360</b>, steps <b>366</b> and <b>368</b> are conducted. At the step <b>366</b>, the particular change is correlated with a management operation. At a step <b>368</b>, that management operation is conducted. The determination within Step <b>366</b> depends upon the mapping conducted above and is illustrated by FIGS. 8<i>a </i>through <b>8</b><i>d </i>according to the particular mapping of the restructuring view table being updated and the base table upon which each change has occurred. For instance if the mapping retrieved at the step <b>362</b> indicates a split operation between the base table and the target table (the restructuring view of the base table), the method of FIG. 8<i>a </i>is conducted. If the mapping indicates a unite operation, the method of FIG. 8<i>b </i>is conducted. If the mapping indicates a fold operation, the method of FIG. 8<i>c </i>is conducted. Finally, if the mapping indicates an unfold operation, the method of FIG. 8<i>d </i>is conducted.

[0133] Referring now to FIGS. 8<i>a </i>through <b>8</b><i>d</i>, each of the determinations and their corresponding operations will now be described. Beginning with FIG. 8<i>a</i>, if the mapping includes a split operation, a correlation module such as the correlation module <b>144</b> begins a correlation operation at a step <b>402</b> and proceeds to a step <b>404</b>. At the step <b>404</b>, the correlation module checks whether the changes require an insert operation. If an insert operation is required, the correlation operation proceeds to a step <b>405</b>.

[0134] At a step <b>405</b>, the correlation module determines which target table corresponds to the tuple. For instance, for each tuple added to the source relation that is split, the split column value is preferably converted to a relation name. If a target table with the desired relation name exists, the insert is conducted at a step <b>406</b>. If there is no such target table, a table is created with the split column value as the relation name at a step <b>407</b>.

[0135] Otherwise, the correlation method proceeds to a step <b>408</b>, where the correlation module checks whether the changes require an update operation. At a step <b>409</b>, the correlation module checks whether the required update involves a splitting column. If the splitting column value is not updated, a tuple update is conducted at a step <b>410</b>. Step <b>410</b> updates the target table corresponding to the split column value.

[0136] If step <b>409</b> determines that the required update involves a splitting column, the correlation module proceeds to a step <b>411</b>. At the step <b>411</b>, as in step <b>405</b>, the correlation module checks whether a target table with the desired relation name exists. If not, a target table is created at the step <b>407</b> and the tuple is moved to the newly created table. Otherwise, the correlation module proceeds to a step <b>412</b>.

[0137] At step <b>412</b>, the correlation module moves the associated tuple from a target table corresponding to the old split column value, to a target table corresponding to the new split column value. Thus, if the split column is updated in the source relation, the tuple is moved from the table that corresponds to the old split column value to the target table that corresponds to the updated split column value. The source table is preferably deleted at this time if it is empty. If required, source table deletion may be conducted at either step <b>407</b> or step <b>412</b>.

[0138] U Referring back to step <b>408</b>, if the changes do not require an update operation, the correlation module proceeds to a step <b>413</b>. At step <b>413</b>, the correlation module checks whether the changes require a delete operation. If so, at step <b>414</b>, the tuple is deleted from the target table associated with the split column value. If the deleted tuple is the last tuple in the target table, the target table is preferably deleted.

[0139] If step <b>413</b> determines that no delete operation is required, the correlation module proceeds to a step <b>415</b>. At step <b>415</b>, the correlation module checks whether a drop table operation is required. If so, all target tables are dropped at a step <b>416</b> before proceeding to a step <b>418</b>. If step <b>415</b> determines that no drop table operation is required, the correlation module also proceeds to step <b>418</b>. The method ends at step <b>418</b>.

[0140] Referring to FIG. 8<i>b</i>, if the mapping indicates a unite operation, the correlation module begins the method at the step <b>420</b>. At the step <b>422</b>, the changes are examined to determine if an insert operation is required. This comprises checking whether a tuple has been added to any of the source tables. If so, a corresponding tuple is added to the target table at a step <b>428</b>, and the relation name of the source table is transformed into a column value.

[0141] Otherwise, the method proceeds to a step <b>430</b> where the correlation module checks whether the changes require an update operation. An update is conducted whenever an update occurs in any of the source tables. A source table update is translated into an update of the corresponding tuple in the target table at a step <b>432</b>. The tuple in the target table is identified by the column values of the row that is updated.

[0142] Otherwise, the method proceeds to a step <b>434</b> where the correlation module checks whether the changes require a delete operation. A delete is conducted when an entry in the source column is deleted and comprises a deletion of the corresponding entry in the target column. This is conducted at a step <b>436</b>.

[0143] Otherwise, the method proceeds to a step <b>438</b> where the correlation module checks whether the changes correspond to a rename column operation. If a rename column operation is required, the method proceeds to a step <b>440</b>. Step <b>440</b> translates the column rename into an update of the target table tuples in the rows associated with the particular source table.

[0144] Thus, a rename column operation is conducted when a column is renamed in one of the source tables. The renamed column may involve multiple rows, in instances, for example when the particular source table has multiple rows. Each row associated with a source table has a folded column value corresponding to the source table relation.

[0145] If no rename column operation is required, the method proceeds from step <b>438</b> to a step <b>442</b> whereupon the correlation module checks whether the changes correspond to a drop table operation. When one of the source tables is dropped, multiple deletes are conducted on the target table at a step <b>444</b>. Step <b>444</b> deletes the rows associated with the particular source table. Each row associated with the dropped table will have a folded column value corresponding to the relation (name) of the dropped table. The method proceeds from step <b>444</b> and other steps to end at a step <b>446</b>.

[0146] Referring to FIG. 8<i>c</i>, if the mapping indicates a fold operation, the correlation module begins the method beginning at a step <b>450</b>. At a step <b>452</b>, the changes to the source table are examined to determine if they correlate with an inserted row. If so, the method proceeds to step <b>454</b>. Step <b>454</b> inserts one row per source table folding column into the target table. Since the tuples associated with the folding columns fold into a single column in the target, inserting one row for each folding column maintains an association between source table tuples and target table tuples.

[0147] If the correlation module determines at step <b>452</b>, that no row has been inserted into the source table, step <b>456</b> checks whether a row has been updated. If so, the method proceeds to step <b>458</b>. Step <b>458</b> updates the corresponding rows in the target table (one row per folding column), otherwise the method proceeds to step <b>460</b>. Step <b>460</b> checks if the changes correspond to a delete row operation. If so, step <b>462</b> deletes the rows containing target table tuples that correspond to the tuples deleted in the source table row. If the changes do not correspond to a delete row operation the method proceeds from step <b>460</b> to step <b>464</b>.

[0148] At step <b>464</b>, the changes are examined to determine whether a column has been inserted into the source table. If a column has been inserted, the method advances to a step <b>465</b> to determine if the inserted column is a folding column. If a folding column was inserted, the method proceeds to a step <b>466</b> to insert a set of corresponding rows in the target table. The inserted rows contain tuples corresponding to the tuples in the inserted source table column. If step <b>465</b> determines the inserted column was not a folding column, the method instead proceeds to step <b>468</b>. Step <b>468</b> inserts a column into the target table corresponding to a non-folding source table column.

[0149] If the correlation module determines at step <b>464</b>, that the changes do not correspond to a column insert operation, the correlation module proceeds to step <b>470</b> to check if the changes correspond to a column update operation. If so, the method proceeds to step <b>471</b> to determine the nature of the update. If the update is associated with a folding column, the method proceeds to step <b>472</b>. Step <b>472</b> updates the target table tuples corresponding to the updated source table column. If the updated source table column is not a folding column, the method proceeds from step <b>471</b> to step <b>474</b>. Step <b>474</b> updates the target table column corresponding to a non-folding source table column.

[0150] If the result of the inquiry of step <b>470</b> is no, the method proceeds to a step <b>476</b> where the correlation module checks whether the changes correspond to a column rename operation. If so, the method proceeds to a step <b>478</b> to determine if the updated source table column is a folding column. If the updated column is a folding column the method proceeds to a step <b>480</b>, otherwise to a step <b>482</b>.

[0151] Similar to step <b>472</b>, step <b>480</b> updates the target table tuples corresponding to a source table column. Renaming of a column maps to target table updates in that the folding operation transforms column names into folded column values. Since the renaming is column based, the number of corresponding tuples or rows affected by the rename corresponds to the number of rows in the source table. Step <b>482</b>, however, simply renames the target table column since the renamed source table column is determined to be a non-folding column.

[0152] The method proceeds from step <b>476</b> to step <b>484</b> if the changes do not correspond to a column rename operation. At step <b>486</b>, the correlation module checks whether the changes correspond to a delete column operation. If the changes do correspond, the method proceeds to a step <b>486</b>, otherwise to a step <b>492</b>. At step <b>486</b>, the correlation module determines whether the column delete involves a folding column. If a folding column is involved, the method proceeds to a step <b>488</b>, otherwise the method proceeds to a step <b>490</b>.

[0153] Since a folding column is involved, step <b>488</b> deletes the rows in the target table containing tuples that correspond to tuples in a source table column that is a folding column. Step <b>490</b> however, deletes a column in the target table rather than rows (as in step <b>488</b>) since a non-folding column is involved. After executing step <b>488</b> or step <b>490</b>, the method ends at a step <b>492</b>. The correlation module may also proceed to step <b>492</b> from certain other steps as depicted in FIG. 8<i>c. </i>

[0154] Referring to FIG. 8<i>d</i>, if the mapping indicates an unfold operation, the correlation module begins the method beginning at a step <b>500</b>. At a step <b>502</b>, the changes are examined to determine whether a row insert operation is necessary. If necessary, the method proceeds to a step <b>504</b>.

[0155] At step <b>504</b>, the correlation module checks if the value in the unfolding or pivoting column is a new value i.e. if there is no column name in the target table corresponding to the pivoting column value of the inserted row. The pivoting or unfolding column is the column from which the unfolded column names (in the target table) are derived. If the pivoting column value is new, the method proceeds to a step <b>506</b> and inserts a new column in the target table with a column name that corresponds to the pivoting column value of the inserted row.

[0156] If the result of the inquiry of step <b>504</b> is no, the method proceeds to a step <b>508</b>, where the correlation module checks to see if an appropriate target table row is available to store the tuples associated with the inserted row. Checking for an available appropriate row may comprise searching for a row with a null value in the column with a name corresponding to the pivoting column value in the inserted row. If an appropriate row is available, the method proceeds to a step <b>510</b> and updates the row. Otherwise, the method proceeds to a step <b>512</b> and inserts a row into the target table.

[0157] The method proceeds from step <b>502</b> to a step <b>514</b> if the changes do not correspond to a row insert operation. At step <b>514</b>, the correlation module checks whether the changes correspond to a row update operation. If the changes correspond, the method proceeds to a step <b>516</b>. Step <b>51</b> is similar to step <b>54</b> in that the correlation module-checks if the pivoting column value (in the inserted row) is a new value. If the value is new, the method proceeds to a step <b>518</b> and inserts a new column into the target table. The name of the new column corresponds to the new pivoting column value.

[0158] If, at step <b>516</b>, the pivoting column value is not new, the method proceeds to a step <b>520</b>. At step <b>520</b>, similar to step <b>508</b>, the correlation module checks if an appropriate row is available in the target table. If an appropriate row is available, the method proceeds to a step <b>522</b>, otherwise to a step <b>524</b>. Step <b>522</b> updates the appropriate row while step <b>524</b> inserts a new row into the target table.

[0159] The correlation module proceeds from step <b>514</b> to step <b>526</b> if the changes do not correspond to a row update operation. At step <b>526</b>, the correlation module determines if the changes correspond to a delete row operation. If the changes do correspond, the method proceeds to a step <b>528</b>. Since the source table deleted row corresponds to a specific tuple in the target table, step <b>528</b> places a null value in the target table.

[0160] After placing a null value in the target table, the method may, in one embodiment, check whether the column in which the null value was placed contains all null values. If so, the method executes step <b>532</b> and deletes the column in which the null value was placed. In either case, the method proceeds to a step <b>534</b> whereupon the method ends.

[0161] Returning back to FIG. 6, once the operation is conducted at the step <b>368</b> as determined by the methods of FIGS. 8<i>a </i>through <b>8</b><i>d</i>, the next change is fetched at the step <b>364</b> until all changes have been propagated to the restructuring view (target table). The process then loops back to the step <b>356</b> ,where the monitoring module continues to monitor the base table(s) for new changes. The method ends upon shutdown of the MDBS at a step <b>372</b>.