Abstract:
Systems and methods are disclosed for providing view maintenance by buffering one or more search results in a cache; and incrementally maintaining the search results by analyzing a source data update and updating the cache based on a relevance of the update to the search results.

Description:
BACKGROUND  
       [0001]     XML (Extensible Markup Language) is a system for defining, validating, and sharing document formats. XML uses tags to distinguish document structures, and attributes to encode extra document information. The XML semi-structured data model has become the choice both in data and document management systems because of its capability of representing irregular data while keeping the data structure as much as it exists. Thus, XML has become the data model of many of the state-of-the-art technologies such as XML web services. Web service response times have large impacts on the response time of the front-end application since the front-end application may invoke multiple web service operations to serve an end-user request.  
         [0002]     Caching data by maintaining materialized views (or query results) has many well-known benefits; one of the major benefits is improving query performance by answering queries from the cache instead of querying the source data. Caching data by maintaining materialized views typically requires updating the cache appropriately to reflect dynamic source updates. To be useful, a materialized view needs to be continuously maintained to reflect dynamic source updates. The problem of efficient incremental view maintenance has been addressed extensively in the context of relational data models but only few works have addressed it in the context of semi-structured data models.  
         [0003]     Current web services caching approaches, e.g. the approach of Microsoft&#39;s .NET framework, follow a time-based invalidation scheme in which the cached results are invalidated after a pre-specified time period (life time). The drawbacks of such a scheme are: (1) the cached results are likely to be over-invalidated since the invalidation process does not take into account the relevance of the source updates to the cached results, (2) the invalidation operation implies recomputing the views whenever they are required again; this recomputation process is generally an expensive one, and (3) the “freshness” of the cached results is not guaranteed because source updates may take place just after a result has been cached, the effect of these updates will not be reflected in the cache before the lifetime of the cache expires. This might be inappropriate for critical applications which require a high level of consistency between the source and the cache.  
         [0004]     The XML views maintained at the cache are assumed to be the results of certain queries (view specifications) issued against a source XML document. The W3C consortium is currently working towards standardizing XPath and XQuery as XML query and view specification languages. Path expressions form the core of the XPath and XQuery languages: they are the language constructs which are used to select and retrieve data from XML data sources. The retrieved data can be manipulated by other language constructs to form the final XML query result. Therefore, caching the results of path expressions could be potentially beneficial to answer general XML queries efficiently.  
         [0005]     Generally, in order to maintain cached views, a maintenance algorithm needs to issue queries to the data source; querying the source is generally an expensive operation in terms of time and processing since the data source is usually huge in size. Conventional techniques for providing incremental view maintenance for structured data such as XML data is inapplicable to Web service caching and many other practical use cases due to the following limitations: (1) view specification models and source update models are very limited, (2) amount of additional data stored for maintenance (intermediate results) can be arbitrarily large regardless of the size of cached view results.  
       SUMMARY  
       [0006]     Systems and methods are disclosed for providing view maintenance by buffering one or more search results in a cache; and incrementally maintaining the search results by analyzing a source data update and updating the cache based on a relevance of the update to the search results.  
         [0007]     Advantages of the system may include one or more of the following. The system provides incremental maintenance of views defined over XML documents using path expressions. The system minimizes the number and the size of the source queries which are used to maintain the cached results. The incremental view maintenance updates cached views to reflect source updates without a full recomputation of views. As a result, the system provides solutions for fast, scalable management of update management of distributed content with interdependency. The system also enables efficient Web service cache management that addresses performance issues of Web services. The solutions can be applied to other XML content dependency management applications such as: (1) XML content delivery including RSS dissemination (2) scalable configuration management of distributed systems (such as grid applications) through change dependency monitoring.  
         [0008]     Other advantages can be as follows. The view specification language is powerful and standardized enough to be used in realistic applications. The size of the auxiliary data maintained with the views is upper bounded; it depends on the expression size and the answer size regardless of the source data size. The system does not require a source schema—the source data can be any general well-formed XML document. Moreover, the system off-loads processing from the back-end application to provide web services scalability. Thus, maintaining XML views is an integral problem that needs to be handled efficiently. Further, the view definitions are not restricted to monotonic. That is, the system handles cases where an addition in the source could result in addition or deletion in the view. Similarly, we handle cases where a deletion in the source could result in addition or deletion in the view.  
         [0009]     The system also preserves the privacy of the data source; it is not required that the definitions of the expression predicates be disclosed for the maintenance algorithm to do its job. Only the expression axis and label tests are required. The predicate definitions might include any proprietary user defined functions. This privacy-preserving property is essential for web service caching projects where the web service provider might not be willing to disclose all the details of the view definitions (web service operations) to a third-party that is caching the web service responses.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]      FIG. 1  shows a block diagram of an exemplary system that provides incremental maintenance of path-expression views.  
         [0011]      FIG. 2  shows an exemplary XML document represented as an ordered tree.  
         [0012]      FIG. 3  shows an exemplary process for performing incremental maintenance.  
         [0013]      FIG. 4  shows a second exemplary process for performing incremental maintenance.  
         [0014]      FIGS. 5A, 5B ,  6 A and  6 B show various performance comparisons for updating path expression views.  
         [0015]      FIG. 7  shows an exemplary XML tree illustrating an incremental maintenance example.  
     
    
     DESCRIPTION  
       [0016]      FIG. 1  shows a block diagram of an exemplary system that provides incremental maintenance of path-expression views. The system has a cache  10  and a source data system  20 . The cache  10  includes an auxiliary database  12  which communicates with a cache maintainer  16 . The maintainer  16  provides a plurality of views  14  or search results.  
         [0017]     The source data system  20  includes data  22 , which is structured data such as XML data as well as an update engine  24  that updates the maintainer  16 . A search query would access the cached views  14  if the cached data provides a current response. Alternatively, the query would access the source data  22  to formulate an answer to the query.  
         [0018]     In one embodiment, the data  22  contains documents that conform to the Extensible Markup Language. The data uses tags (for example &lt;em&gt;emphasis&lt;/em&gt; for emphasis), to distinguish document structures, and attributes (for example, in &lt;A HREF=“http://www.xml.com/”&gt;, HREF is the attribute name, and http://www.xml.com/ is the attribute value) to encode extra document information.  
         [0019]      FIG. 2  shows an exemplary XML document represented as an ordered tree in which every node n is a pair &lt;n.id, n.label&gt; where n.id is a node identifier that uniquely identifies the node among all the nodes in the XML tree and n.label is a string that describes the node type and value. Upper-case letters represent the node labels. For example, A, B, and C are node labels and numeric subscripts are used to distinguish different nodes that have the same label. Thus, A i  and A j  refer to two distinct nodes with the same label A.  
         [0020]     The pictorial illustration of  FIG. 2  is used to capture the ancestor and descendent relationships among the nodes, and the tree order is from left to right in  FIG. 2 . Typically, the node identifier has the following properties: 
        1. Dynamic; i.e. adding and deleting nodes in the source tree do not require reassignment of node identifiers as the property preserves the source node identities;     2. Reflecting the document order; i.e. given the identifiers of any two nodes n i  and n j , it can be determined if n i  is before or after n j  in the preorder traversal of the source tree. This property is required to keep the order of nodes in the cached view in correspondence with the original document order of nodes; and     3. Reflecting the containment relationships among the nodes; i.e. given the identifiers of two nodes n i  and n j , it can be determined if n i  and n j  have ancestor or descendant relationship. This property is used by XML query processors.        
 
         [0024]     The label has the following properties: 
        if n corresponds to an XML element then label represents the element name;     if n corresponds to an XML attribute then label represents the attribute name; and     if n corresponds to a value of any type then label is the value representation, hence it may have types associated with it.        
 
         [0028]     Based on the definition of node labels, a selection condition in a query involving the node name, kind, or type is represented as a label test. For example, a condition that retrieves ‘book’ elements is a label test and a condition that retrieves nodes storing values greater than 5 is also a label test. A label test could also be the wildcard character “*” which matches all labels.  
         [0029]     The XML tree of  FIG. 2  can be updated to reflect updates to the source XML document. In this context, a source update is a transformation of the source XML document. Although the transformation could be in the form of changes to the leaf nodes as well as internal nodes in the tree, one embodiment works with primitive transformations that operate at the level of the leaf nodes in an XML tree. Any arbitrary transformation to the source tree, e.g. adding or deleting a sub-tree from the source, can be expressed in terms of the following two primitive operations: (1) Add a leaf node, and (2) Delete a leaf node. More formally, an update U is a pair &lt;U.type, U.path&gt; where U type is the type of the update: Add (add a leaf node) or Delete (delete a leaf node). U.path is the path of all the ancestors of the added or deleted node starting with the document root and ending with the added or deleted node itself. Each node in U.path is given by both its label and its identifier. The added or deleted node is referred to as U.node. For example, U=&lt;Add, (R, X 1 , A 1 , B 1 , Z)&gt; represents the addition of node Z as a child node of node B 1  in the XML document shown in  FIG. 2 .  
         [0030]     Path expressions are the basic building blocks of XML queries. A path expression E of size N is a sequence of N steps: (s 1 , s 2 , . . . s N ). A step s i  is a triple &lt;s i .axis, s i .label, s i .pred&gt; where: 
        s i .axis is an axis test; it is either a child selector (denoted by ‘/’) or a descendant selector (denoted by ‘//’). The axis test selects nodes based on the tree structure.     s i .label is a label test; it selects some of the nodes that passed the axis test. The label test is evaluated by examining only the node label without examining any other nodes or structures in the tree.     s i .pred is a predicate test; it further filters the nodes that have passed both the axis test and the label test. Unlike the label test, the predicate test can be any complex condition examining the labels and the structure of the nodes in the sub-tree of the node being tested. A predicate can use aggregate functions, user defined functions, operators, quantifiers, for example.        
 
         [0034]     The first s i  processing starts at a pre-specified sequence of nodes in the source tree called the expression context C. Given an expression E, a document tree D, and a sequence of context nodes C (a sequence of some of the nodes of D), a query, Q, denoted as Q=q(E, C, D) returns a sequence of nodes R as a result. Conceptually, the execution of s i  (i&gt;1) starts at the sequence outputted from executing s i−1 . The intermediate result of step s i  (1&lt;i&lt;N) as R i =q(s i , R i−1 , D), R 0 =C.  
         [0035]     Every R i , (1&lt;i&lt;N) is a sequence of nodes ordered by the document order. The final result R is defined as the result of the last operation; i.e. R=R N .  
         [0036]     For example, consider the query Q=q(E, C, D) where: D is the document tree of  FIG. 2 , C=(X 1 , X 2 , X 3 ), and the steps of E are specified as follows:  
         [0037]     s 1 =/A  
         [0038]     s 2 =//B [Count (//E)&gt;1 OR Count(/D)&gt;1] 
         [0039]     s 3 =//C [Count (//E)=0] 
         [0040]     s 4 =//D  
         [0041]     In this query, the first step s 1  starts at every node in C and selects all children with label A; this results in R 1 =(A 1 , A 2 , A 3 ). Then s 2  starts at every node in R 1  and selects all the descendants with label B that have at least one descendant labeled E or at least one child labeled D; this results in R 2 =(B 2 , B 3 , B 4 , B 5 ). Starting at R 2 , step s 3  selects all the descendants labeled C that have no descendants labeled E; this results in R 3 =(C 3 , C 4 , C 5 , C 5 ). Finally, s 4  starts at R 3  and selects all the descendants labeled D. Hence, the final result of Q is R=R 4 =(D 3 , D 3 , D 4 , D 4 ).  
         [0042]     A node can be duplicated in the answer of any step. This shows the possibilities of multi-derivations in path expression views. Multiple occurrences of the same node in a sequence are differentiated by using a numeric superscript. For example, the result R is denoted as R=(D 3   1 , D 3   2 , D 4   1 , D 9   2 ).  
         [0043]     The incremental maintenance process uses the following definitions regarding path expressions: 
        1) Pred i (n) is true if and only if s i .pred evaluates to true at node n. For example, Pred 3 (C 1 ) in the example query above is true because C 1  satisfies the condition s 3 .pred=[Count(//E)=0] since C 1  has no descendants labeled E.     2) The Result Path of a node n in the result R, referred to as ResultPath(n), is the sub-sequence (may be noncontiguous) of the ancestors of n (including n) that matched the steps of E and thus caused n to appear in R. In the example query above, ResultPath(D 3   1 )=(X 1 , A 1 , B 2 , C 3 , D 3 ) and ResultPath(D 3   2 )=(X 1 , A 1 , B 2 , C 4 , D 3 ). The result paths have the same size, which is equal to N+1, where N is the expression size. This is because every element in a result path matches exactly one step of E and every step of E is matched by exactly one element in each result path; the extra 1 is because the first node in each path result is a context node from the sequence C which is not matching any step.     3) For every node n such that nεR, we define ResultPath i (n), i&gt;0 as the i-th element in the result path of n. By this definition,     ∀nεR, ResultPath 0 (n)εC, ResultPath N (n)=n.        
 
         [0048]     In one embodiment, certain simplification/restrictions are maintained to achieve an efficient view maintenance. First, only child and descendant axes are handled in the axis test as the child and descendant axes are the most commonly used axes in practice. The other axis types, such as parent and ancestor, are not handled. Second, a Predicate can examine only the subtree of the node being tested. In other words: Pred i (n), for all i, is exclusively evaluated by examining the subtree rooted at n. This simplification is based on the fact that a node in an XML document is semantically described by its descendants, and thus selecting a node should depend on its label and its descendants. With this approach, predicate evaluation can only be done at the source XML data. The benefit is that the predicates can be arbitrarily complex and the predicates can preserve the privacy/security of the XML data source.  
         [0049]     To illustrate an update, the result R of an example expression E is cached at the client site and subsequently the following update takes place at the source tree of  FIG. 2 : U=&lt;Add, (R, X 1 , A 1 , B 1 , E 5 )&gt;. The effect of this update is to change Pred 2 (B 1 ) from false to true. The direct effect of this change on the evaluation process of E is to add B 1  to the intermediate result R 2 . Since there is a new node added to R 2 , there is a possibility that this addition can induce other indirect additions in the subsequent intermediate results R i , i&gt;2. This is indeed the case in this scenario since nodes C 1  and C 3  would now qualify to be in R 3  as descendants of B 1 . Moreover, the inclusion of C 1  and C 3  causes D 1  and D 2  to be added to R 4 , i.e. to the cached result R. This illustrates that an update U can affect the final results R by impacting any of the intermediate result R i .  
         [0050]     In this example, U changed Pred i (n) for only one node (n=B i ) and one value of i (i=2). This change effectively added B 1  to R 2 . Consequently, other nodes were added to other intermediate results but without U changing any more predicates; these are nodes C 1 , C 2 , D 1 , and D 2  in the example. Thus, an update U causes a node n to be added to an intermediate result R i  under one of two possible scenarios:  
         [0051]     1. U changes Pred i (n) from false to true,  
         [0052]     2. U does not affect Pred i (n).  
         [0053]     The first case is a direct addition and to the second case is an indirect addition because it is caused indirectly through a direct addition. Direct deletion can occur when U changes Pred i (n) from true to false causing n to be deleted from R i . Indirect deletion can occur when n is deleted from R i  without U affecting Pred i (n). For example, if U=&lt;Add, (R, X 1 , A 1 , B 2 , C 3 , E 6 )&gt; then U directly deletes C 3  from R 3  because it changes Pred 3 (C 3 ) from true to false. This direct deletion induces the indirect deletion of the first occurrence of D 3  from R.  
         [0054]     In the following discussion, δ i   +  denotes the sequence of all nodes that U directly adds to R i ; δ i   −  denotes the sequence of all nodes that U directly deletes from R i , and δ i =δ i   + |_|δ i   − . Each of δ i   +  and δ i   −  could have repetition due to multi-derivation possibilities and that δ i   +  and δ i   −  are mutually disjoint because a node n can not be directly added to and deleted from R i  at the same time; that is because U can not change Pred i (n) from false to true and from true to false at the same time.  
         [0055]     Since any indirect addition or deletion is originated by a direct one, an embodiment of the maintenance process determines all direct additions and deletions at R i  and then determines the indirect effects that are induced by the direct effects. Ultimately the process determines indirect effects on the cached result R. The indirect effects on all the intermediate results R i , i&lt;N are not required per se, but they can be used to discover the final effects on R.  
         [0056]     To discover indirect effects from the direct ones, the process handles two cases:  
         [0057]     1. When a node n is directly added to R i , then the maintenance algorithm has to issue a query to the source to determine the indirect additions that might happen due to this direct addition. For example, when B 1  is added to R 2 , the indirectly added nodes C 1 , C 2 , D 1 , and D 2  can not be retrieved without querying the source because they had no existence at the cache before U occurred. In general, when a node n is directly added to R i  then, in order to retrieve the indirect additions at all R j , j&gt;i, the maintenance process needs to issue a source query with context as the singleton sequence (n) and with the steps sequence (s i+1 , s i+2 , . . . s N ). The query is denoted as: q((s i+1 , s i+2 , . . . s N ), (n), D).  
         [0058]     2. When a node n is directly deleted from R i , then the nodes of R that came to R because n used to belong to R i  are deleted from R i . In other words, all the nodes r of R i  that have ResultPath i (r)=n are deleted from R. In the example, the direct deletion of C 3  from R 3  results in deleting D 3   1  from R because ResultPath 3 (D 3   1 )=C 3 .  
         [0059]     Once result path of each node of R is known, the process discovers the necessary indirect deletions from R without issuing any source queries. The system thus keeps with every node nεR the result path ResultPath(n).  
         [0060]     The collection of all the result paths is kept as auxiliary data which is not itself a target, but it is just used to achieve efficient incremental maintenance of the cached result R. In one embodiment, this is the only auxiliary data used. No two result paths are the same; even if a single node from the source tree occurs multiple times in R, each occurrence will be associated with a different result path.  
         [0061]     The keeping of the result paths is not equivalent to keeping all the intermediate results R i s. In particular, if a node n in R i  does not lead to a node in R then the process does not keep n in the auxiliary data. For example, in the example  
         [0062]     /A//B[Count(//E)≧1 OR Count(/D)≧1]//C[Count(//E)=]//D 
        B 5  is in R 2 . However, B 5  did not lead to any node in R because none of its descendants were qualified to be in R 3  or R 4 . Thus, B 5  is not kept in the auxiliary data. Obviously, the number of such nodes like B 5  can be arbitrarily large in the source tree without any bound.        
 
         [0064]     The size of the auxiliary data is bounded regardless of the source tree. To compute this size, since each result path is of length N+1 and M is the size of the cached result R, then the size of the auxiliary data is O(M * N). The process stores only the node IDs in the result paths and the node labels are not needed. This limits the size of the auxiliary data because the node ids are machine generated as compact codes.  
         [0065]     The determination of the direct effects is discussed next. This determination is done in two phases for every R i : 1) the Axis&amp;Label test and 2) the Predicates test.  
         [0066]     (1) The Axis &amp; Label Test. For every R i , the sequence of direct effects δ i  is determined by querying the source because it might involve predicate evaluations to determine the nodes n for which Pred i (n) has changed due to U. Since the amount of source queries is to be minimized, the Axis &amp; Label phase identifies a sequence Δ i  such that, without any source queries, that δ i ⊂Δ i . In the Predicates Test phase, Δ i  is further filtered by predicates evaluations to identify the exact sequence δ i . In other words, the Axis &amp; Label Test works as a first-level filter for identifying δ i  since every node n in δ i  also belongs to U.path. In other words, if, due to U, a node n belongs to δ i  for any i, then n must also belong to U.path. This limits the search space to the nodes in U.path.  
         [0067]     Although U.path has all the information needed to conduct the axes and labels tests needed to identify δ i , it does not have enough information to evaluate the predicates at any of its nodes n because a predicate can refer to any node in the subtree of n. The process applies the Axes and Label tests to U.path, ignoring the predicates tests. The result is the sequence Δ i  which is a super-sequence of δ i .  
         [0068]     Computing the different Δ i &#39;s proceeds similar to computing the intermediate results R i &#39;s of the original view specification query except that the latter selects from the source tree D while the former selects from the single branch U.path. Any node n in any δ i  must have a node of the expression context C as an ancestor. Thus, the process initializes Δ 0  to be all the context nodes that exist in U.path, i.e. Δ 0 =C∩U.path. After this initialization, the process determines Δ i  (for i&gt;1) as all the nodes in U.path that satisfy s i .axis and s i .label starting at nodes in Δ i . This query is denoted as Δ i =q(s i .axis&amp;label, Δ i−1 ,U.path).  
         [0069]     The following example shows the computation of the Δ i s. In an update U of adding a node D 6  as a child of D 4 , U.path is the tree branch that starts with the root R and ends with D 6 . Computing the different Δ i &#39;s as described above results in: Δ 0 =(X 2 , X 3 ), Δ 1 =(A 2 , A 3 ), Δ 2 =(B 3 , B 4 , B 5 ), Δ 3 =(C 5 , C 5 ), Δ 4 =(D 4 , D 4 , D 6 , D 6 ).  
         [0070]     Δ i  is a supersequence of δ i : there are nodes in Δ i  that are not directly added to or deleted from R i . For the example shown above, using the predicates as defined in the example path expression, the only nodes that will be directly added are the two occurrences of D 6  that appear in Δ 4 . The other nodes n in all the computed Δ i &#39;s will not be added or deleted because U did not affect Pred i (n). Note that because D 6  did not exist before U occurred, the value of Pred i (D 6 ), for all i is false before U occurred. The same holds with deletion updates: if an update U deletes a node n from the source tree, the value of Pred i (n) is false after U occurred.  
         [0071]     (2) The Predicate Test. The Predicate Test identifies the sequence δ i  from the sequence Δ i . To accomplish this task, the process determines which nodes n in Δ i  had their Pred i (n) changed due to U. To detect such changes, the process compares, for every node, the values of Pred i (n) before and after U occurred. The value before U occurred is referred to as Pred i   before (n) and to the value after U occurred as Pred i   after (n). Nodes for which Pred i   after (n) are excluded because they are not affected by U. Nodes with their Pred i (n) changing due to U are directly added to or deleted from R i .  
         [0072]     The determination of the values of Pred i   after (n) and Pred i   before (n) for every node n in Δ i  is as follows. The value of Pred i   after (n) is computed simply by querying the source. This query, in general, will be processed very quickly as it just evaluates the predicate s i .pred at node n in the source tree D. the returned value is true or false. We denote this query as: pred q (s i .pred, (n), D).  
         [0000]     The query is performed by a source query processor with the following benefits:  
         [0000]    
       
         
           
              1. The process does not need to keep any auxiliary data that might be needed to evaluate complex predicates—if data from all nodes is stored to evaluate every predicate, then the size of the auxiliary data can be unbounded.  
              2. The source privacy is protected by not revealing the predicate definitions. A predicate definition may use proprietary functions that the data provider is not willing to disclose as in the case of web service providers.  
           
         
       
     
         [0075]     The value of Pred i   before (n) cannot be computed by a source query because the update U has already been incorporated at the source. Instead, the value of Pred i   before (n) is deduced as follows: if node n appears as the i-th element in the result path of any node in R then this implies that n was qualified for R i  before U occurred; hence, Pred i   before (n)=true. Let RP i (n) be true if and only if n is the i-th element of the result path of any node in R, then RP i (n)=&gt;Pred i   before (n). This shows how the auxiliary data—which was originally intended to be used for discovering indirect deletions—could help in the predicate test as well. However, if RP i (n) is false then the value of Pred i   before (n) cannot be determined because it may be false or true. Thus, if RP i (n) is false, there is an ambiguity about the value of Pred i   before (n).  
         [0076]     One implementation to resolve this situation includes in the auxiliary data all the nodes that qualify to be in any intermediate result R i  instead of only including those nodes that actually lead to nodes in the final result R. However, the size of the auxiliary data can become unbounded. In another implementation, the ambiguity is resolved by simply assuming that Pred i   before (n) is false. This assumption does not affect the result of discovering the indirect effects in R.  
         [0077]      FIG. 3  shows one embodiment of the process for view maintenance of XML path expressions. The maintenance process combines the two phases described above to determine the direct effects at every R i  and uses the determined direct effects to discover the ultimate effects on the cached result R. The process is as follows:  
                                                   Initialize: Δ 0  = C ∩ U.path           FOR (i=1; i ≦ N AND Δ i−1  is not empty; i++)             Compute Δ i  by applying the Axis &amp; Label test of s i  starting at             nodes of Δ i−1               Compute δ i  by applying the Predicates test of s i  to nodes of Δ i               Use δ i  to find all the indirect effects on R             Update R accordingly                        
         [0078]     In the first step of the loop, every Δ i  is computed from Δ i−1 . One implementation improves performance by excluding some nodes from Δ i−1  before moving on to the computation of Δ i  in the next loop iteration. This will result in a smaller Δ i  and hence in improved performance. The sequence achieved by reducing Δ i  is referred to as Λ i . Hence, in order to discover all the ultimate effects on R, the process only needs to start each iteration i only at the nodes n of the previous iteration for which the value of Pred i−1 (n) is true before and after U occurred. In other words, the process takes only the nodes n that have RP i−1 (n)=Pred i   after (n)=true.  
         [0079]      FIG. 4  shows another embodiment of the incremental view maintenance process. This process computes and uses the reduced sequences Λ i s instead of the Δ i s. For the initialization of Λ 0  and Λ 1 , it is more programmatically convenient to implement the reduction step at the end of each iteration instead of the beginning; step 2-7 in the process computes the reduced Λ i  to be used directly by step 2-1 of the following iteration.  
         [0080]     Step 2-2 issues small source queries to evaluate Pred i   after (n) for every node n in Λ i . According to the results of these queries, Λ i  is partitioned into the two disjoint sequences T and F. Then, step 2-3 identifies the nodes of T that will be considered as direct additions at R i .  
         [0081]     The sequences of nodes to be added to/deleted from R due to the direct effects at every iteration as R + /R − ,respectively. These sequences are computed by steps 2-4 and 2-5 respectively. Conforming to the process of discovering indirect effects, step 2-4 issues a source query while step 2-5 only uses the auxiliary data. Instead of issuing a separate source query for every direct addition, step 2-4 uses a single query with a combined context sequence which incorporates all the direct additions at one shot, this should perform better than issuing many queries.  
         [0082]     Finally, step 2-6 updates R by incorporating the nodes of R +  and R − . The maintenance process needs to maintain the auxiliary data as well as the cached result R. For every node n removed from R, ResultPath(n) is removed from the auxiliary data; and for every node n added to R, ResultPath(n) is added to the auxiliary data. Computing the result paths requires some cooperation from the source query processor: the query processor should return with every node n in the answer of the query in step 2-4 its result path ResultPath′(n). This result path is a partial path of length N−i&lt;N because the query in step 2-4 uses only steps s i+1 , s i+2 , . . . , s N  of the original expression. Thus, to get the full result path ResultPath(n), the process concatenates ResultPath′(n) to the right end of a second result path of length i. This second path is the one which led from a node in the original expression context C to the first node in ResultPath′(n); it can be found by tracing the sequences Λ 0 , Λ 1 , . . . Λ i  through the iterations 1, 2, . . . , i. For clarity of the presentation, this secondary process of maintaining the auxiliary data is not shown in the process of  FIG. 4 .  
         [0083]     The process of  FIG. 4  issues several source queries; however, the processing of these queries is computationally much less expensive than the alternative of issuing the original view specification language. The reason is that these queries are much smaller regarding theirs sizes and contexts than the original view specification query. This advantage of incremental maintenance over full recomputation is illustrated by the following tests.  
         [0084]     In the tests, the system maintains one cached object (such as an XPath query result) and processes node updates one by one. For each update, the time required for incremental maintenance is compared with the time required for the full view recomputation.  
         [0085]     The XMARK benchmark was used to generate source documents with two data sets of different sizes: Data set 1 (325236 nodes), and Data set 2 (1281843 nodes).  
         [0086]     The XML data source was implemented using a relational database. The node ids were generated based on the OrdPATH scheme. Each node was represented as a row of a table with the following columns {id, type, label, value, parent_id} where id is a node identifier and type is a node type (element, attribute, or value). When type is “element”, label represents the element name. When type is “attribute”, label represents the attribute name, and value represents the attribute value. When type is “value”, value represents the data value. Although an OrdPATH node id contains information about the id of the parent node, a column parent-id is used to represent the ID of the parent for performance optimization. The tests were done using an Oracle 9i database on a PC with Linux 8.0, Pentium 4 1800 MHz CPU, and 1 GB memory.  
         [0087]     The following two XPath queries were used:  
                                                   XPath Query 1:             /site/people/person [like (@id,“person2%”)]/name/text ( )           XPath Query 2:             /site/people [person [like (@id,“person1%”)]]/                      
        person[like(@id, “person2%”)]/name/text( )        
 
         [0089]     where “like” is a boolean predicate that corresponds to SQL&#39;s “like” operator.  
         [0090]     The XPath Query 1 is implemented as the following SQL join query:  
                                                   SELECT DISTINCT f.id           FROM x a, x b, x c, x d, x e, x f           WHERE a.type = “element” and a.label = “site”           and a.parent_id = “0” and b.type = “element”           and b.label = “people” and b.parent_id = a.id           and c.type = “element” and c.label = “person”           and c.parent_id = b.id and d.type = “attribute”           and d.label = “id” and d.value like “person2%”           and d.parent_id = c.id and e.type = “element”           and e.label = “name” and e.parent_id = c.id           and f.type = “value” and f.parent_id = e.id;                      
 
         [0091]     where “x” is the name of the table that contains the source nodes. Similarly, the XPath Query 2 is also implemented as a join query. The Predicate test query for the XPath query 1 is implemented as the following SQL query:  
                                                   SELECT *           FROM x c, x d           WHERE c.id = ?           and d.type = “attribute” and d.label = “id”           and d.value like “person2%” and d.parent_id = c.id;                      
 
 where ‘?’ represents a context node. 
 
         [0092]     For each data set and query pair, 100 source updates were randomly generated. An average of results for full query verses incremental maintenance is as follows:  
                                                                                               Data set 1   Data set 2                Query 1   Query 2   Query 1   Query 2                        Full query (msec)   1459.61   4412.2   6549.28   83066.25       Maintenance (msec)   134.13   237.01   355.3   1108.11                  
 
         [0093]     The results of the time comparison for all the updates are shown in  FIGS. 5A, 5B ,  6 A and  6 B. These figures show the advantage of incremental view maintenance approach. For example, for the second data set and second query, the full query takes 80 times longer to execute. The results show that the view maintenance process scales well with both data size and query complexity: the improvement for the smaller data set, less complex query pair (Data set 1, Query 1) is 10X while for the larger data set, more complex query pair (Data set 2, Query 2) the improvement is boosted 80X. The figures show that some updates have taken almost no time to be maintained while other updates have taken a relatively significant time. This is because the former class of updates either do not affect the view result or they cause only deletions at the view results; recall that deletions are processed using the auxiliary data without any source queries. The latter class of updates causes additions at the view and requires more processing time because it requires querying the source.  
         [0094]     The supported view specification language of path expressions is powerful for many applications. The size of the auxiliary data used in bounded as O(M * N) where M is the size of the cached result and N is the size of the view specification expression. The size of the auxiliary data is compact and does not exceed this bound regardless of the complexity of the source XML tree and regardless of the complexity of the predicates used in the view specification path expression. The process delegates any predicate evaluation to the source query processor; the benefits of this delegation are two-fold (1) No auxiliary data is kept for the evaluation of predicates; without this delegation, the size of the auxiliary data can not be bounded. (2) The privacy of the predicate definitions is preserved since the cache manager need not know such definitions in order to maintain the views. This property is useful when the predicate definitions include proprietary functions that the data provider is not willing to reveal, for example, an XML web service provider would be able to use the XML caching system without disclosing its complex predicate definitions. The process does not depend on any schemas for the source XML document, it can handle any general XML document. Regarding the efficiency of the maintenance process, the experimental results show that incrementally maintaining path expression views using the approach presented here is much faster than maintaining the views by recomputing the view specification query.  
         [0095]     One embodiment of the view maintenance process is written as the following code:  
                                                   NodeSet maintenance(NodeSet result, Expression e, NodeSet context,                  Update u, Document d, ResultPath rp) {            NodeSet r_plus = new NodeSet( ); // additions to the result            NodeSet r_minus = new NodeSet( ); // deletions to the result            NodeSet candidates = context.intersection(u); // C 0              // check each step of the expression            for(int i = 1; i &lt;= e.size( ) &amp;&amp; candidates.size( ) &gt; 0; i++) {             // find candidates of direct addition/deletion at the step i             candidates = q(e.step(i).axis_label, candidates, u); // C i               NodeSet addition = new NodeSet( ); // direct addition             NodeSet deletion = new NodeSet( ); // direct deletion             NodeSet candidate1 = new NodeSet( );            // check predicates for each candidate            foreach Node n in candidates {             boolean pred_before = predBefore(n,e,i,d,rp); // Pred i   before (n)             boolean pred_after = predAfter(n,e,i,d,rp); // Pred i   after (n)             if(pred_before == false &amp;&amp; pred_afer == true) {              addition.add(node);             } else if (pred_before == true &amp;&amp; pred_after == false) {              deletion.add(node);             } else if (pred_before == true &amp;&amp; pred_after == true) {              candidate1.add(node);             }            } // now we have Add i (addition), Del i (deletion)            // find the effect of direct additions to the result R+            r_plus.add(q(e.steps(i+1,e.size( )), plus,document));            // find the effect of direct deletions to the result R−            foreach Path p in rp (             if(deletion.includes(p.nodeAt(i)))               r_minus.add(p.resultNode( ));              }            }            candidate = candidate1; // C i ′           }           result.add(r_plus);           result.remove(r_minus);            return result;           }           boolean predBefore(Node n, Expression e, int i, Document d,           ResultPath rp) {            if(n.update_type == ‘add’) {             return false;            } else if(e.step(i).pred == null) {             return true;            } else {             return rp.includesAt(i,n);            }           }           boolean predAfter(Node n, Expression e, int i, Document d) {            if(n.update_type == ‘delete’) {             return false;            } else if(e.step(i).pred == null) {             return true;            } else {             return predq(e.step(i).pred,n,d);            }           }                      
 
         [0096]      FIG. 7  shows an exemplary XML tree illustrating an incremental maintenance example. In this example, the sample XML data is as follows:  
                                                   &lt;Products&gt;            &lt;Books&gt;             &lt;Book&gt;              &lt;Title&gt;The Catcher in the Rye&lt;/Title&gt;              &lt;Author&gt;J.D. Salinger&lt;/Author&gt;             &lt;Year&gt;1991&lt;/Year&gt;             &lt;Publisher&gt;Little,Brown&lt;Publisher&gt;             &lt;ISBN&gt;0316769487&lt;/ISBN&gt;             &lt;Subject&gt;Fiction&lt;/Subject&gt;             &lt;Subject&gt;Classics&lt;/Subject&gt;             &lt;Seller id=“http://bookstore1.com”&gt;              &lt;Name&gt;BookStoreOne&lt;/Name&gt;              &lt;Rating&gt;4&lt;/Rating&gt;              &lt;Price&gt;6.99&lt;/Price&gt;              &lt;Availability&gt;true&lt;Availability&gt;             &lt;Seller id=“http://bookstore2.com”&gt;              &lt;Name&gt;BookStoreTwo&lt;/Name&gt;              &lt;Rating&gt;3&lt;/Rating&gt;              &lt;Price&gt;5.99&lt;/Price&gt;              &lt;Availability&gt;true&lt;/Availability&gt;             &lt;/Seller&gt;            &lt;/Book&gt;            &lt;Book&gt;             &lt;Title&gt;Nine Stories&lt;/Title&gt;             &lt;Author&gt;J.D. Salinger&lt;/Author&gt;             &lt;Year&gt;1991&lt;/Year&gt;             &lt;Publisher&gt;Little,Brown&lt;Publisher&gt;             &lt;ISBN&gt;0316769509&lt;/ISBN&gt;             &lt;Subject&gt;Fiction&lt;/Subject&gt;             &lt;Subject&gt;Classics&lt;/Subject&gt;             &lt;Seller id=“http://bookstore2.com”&gt;              &lt;Name&gt;BookStoreTwo&lt;/Name&gt;              &lt;Rating&gt;3&lt;/Rating&gt;              &lt;Price&gt;5.99&lt;/Price&gt;              &lt;Availability&gt;true&lt;/Availability&gt;             &lt;/Seller&gt;             &lt;/Book&gt;             &lt;Book&gt;             &lt;Title&gt;Franny and Zooey&lt;/Title&gt;             &lt;Author&gt;J.D. Salinger&lt;/Author&gt;             &lt;Year&gt;1991&lt;/Year&gt;             &lt;Publisher&gt;Little,Brown&lt;Publisher&gt;             &lt;ISBN&gt;0316769495&lt;/ISBN&gt;             ....             &lt;/Book&gt;             ....            &lt;/Books&gt;            &lt;Music&gt;...&lt;/Music&gt;            &lt;DVD&gt;...&lt;/DVD&gt;           &lt;/Products&gt;                        
         [0097]     The following example, together with the nodes of  FIG. 7 , illustrates a query for a book written by Salinger and the price is less then $6. The result set is “The Catcher in the Rye” at node 01111 , “Nine Stories” at node 01121 , “Franny and Zooey” at node 01131 . The result path is shown as RP 1 .  
       EXAMPLE 1 
       [0098]    
       
         
               
             
           
               
                   
               
               
                   
               
             
             
               
                 Q 1  = //Book[Author = ‘J.D. Salinger’ and /Seller/Price &lt; 6]/Title/text( ) 
               
               
                 R 1  = {“The Catcher in the Rye” 01111 , “Nine Stories” 01121 , “Franny and 
               
               
                 Zooey” 01131 } 
               
               
                 RP 1  = [[00011,00111,01111],[00021,00121,01121],[00031,00131,01131]] 
               
               
                   
               
             
          
         
       
     
         [0099]     In example 1-1, an update changes the price for node  04812  from $10 to $12 and result set does not change as follows:  
       EXAMPLE 1-1 
       [0100]    
       
         
               
               
             
           
               
                   
                   
               
               
                   
                   
               
             
             
               
                   
                 U 1  = /Products 00000 /Music 00002 /CD 00012 /Seller 00812 /Price 04812 / 
               
               
                   
                 {“10”,“12”} 14812   
               
               
                   
                 C 0  = {Products 00000 } 
               
               
                   
                 C 1  = q(//Book,C 0 ,U 1 ) = { } 
               
               
                   
                 Since the candidate set C i  is empty the loop stops at the step i = 1. 
               
               
                   
                 There is no change in the result R 1 . 
               
               
                   
                   
               
             
          
         
       
     
         [0101]     In example 1-2, another update changes the price from $5.99 to $6.99 and the result set becomes “The Catcher in the Rye” 01111 , “Franny and Zooey” 01131    
       EXAMPLE 1-2 
       [0102]    
       
         
               
               
             
           
               
                   
                   
               
               
                   
                   
               
             
             
               
                   
                 U 2  = /Products 00000 /Books 00001 /Book 00021 /Seller 00821 /Price 04821 / 
               
               
                   
                 {“5.99”,“6.99”} 14821   
               
               
                   
                 C 0  = {Products 00000 } 
               
               
                   
                 C 1  = q(//Book,C 0 ,U 2 ) = {Book 00021 } 
               
               
                   
                 For each node in C 1 , the following predicate is checked: 
               
               
                   
                 Q1.step(1).pred= [Author = ‘J.D. Salinger’ and /Seller/Price &lt; 6] 
               
               
                   
                 The result is as follows: 
               
               
                   
                 Pred 1   before (Book 00021 ) = true (it is in the result path RP 1 ) 
               
               
                   
                 Pred 1   after (Book 00021 ) = false (query to the source) 
               
               
                   
                 Accordingly, direct additions and deletions found at the step 1 are: 
               
               
                   
                 Add 1  = { }, Del 1  = {Book 00021 }. 
               
               
                   
                 This causes the following deletion in the result 
               
               
                   
                 R −  = {“Nine Stories” 01121 } 
               
               
                   
                 Since C 1 ′ is empty, the loop stops here. 
               
               
                   
                 Finally, the result set is updated as: 
               
               
                   
                 R 1 ′ = {“The Catcher in the Rye” 01111 , “Franny and Zooey” 01131 } 
               
               
                   
                   
               
             
          
         
       
     
         [0103]     In Example 1-3, another update changes the price from $6.99 to $5.99 and the result set in this case does not change.  
       EXAMPLE 1-3 
       [0104]    
       
         
               
               
             
           
               
                   
                   
               
               
                   
                   
               
             
             
               
                   
                 U 3  = /Products 00000 /Books 00001 /Book 00011 /Seller 00811 /Price 04811 / 
               
               
                   
                 {“6.99”,“5.99”} 14811   
               
               
                   
                 C 0  = {Products 00000 } 
               
               
                   
                 C 1  = q(//Book,C 0 ,U 3 ) = {Book 00011 } 
               
               
                   
                 For each node in C 1 , the following predicate is checked: 
               
               
                   
                 Q1.step(1).pred= [Author = ‘J.D. Salinger’ and /Seller/Price &lt; 6] 
               
               
                   
                 The result is as follows: 
               
               
                   
                 Pred 1   before (Book 00011 ) = true (it was in the result path) 
               
               
                   
                 Pred 1   after (Book 00011 ) = true (query to the source) 
               
               
                   
                 Thus, there is no direct addition/deletion found at the step i = 1. 
               
               
                   
                 Since C 1 ′ = {Book 00011 }, the loop proceeds to the step 2 resulting: 
               
               
                   
                 C 2  = q(/Title,{Book 00011 },U 3 ) = { } 
               
               
                   
                 The loop stops here since the candidate set is empty. There is no 
               
               
                   
                 change in the result R 1 . 
               
               
                   
                   
               
             
          
         
       
     
         [0105]     Similarly, Examples 2, 2-1 and 2—are as follows:  
       EXAMPLE 2 
       [0106]    
       
         
               
               
             
           
               
                   
                   
               
               
                   
                   
               
             
             
               
                   
                 Q 2  = //Book[ISBN=0316769487]/Seller[Rating &gt; 3]/Price/text( ) 
               
               
                   
                 R 2  = {“6.99” 14811 } 
               
               
                   
                 RP 2  = [[00011,00811,04811,14811]] 
               
               
                   
                   
               
             
          
         
       
     
       EXAMPLE 2-1 
       [0107]    
       
         
               
             
           
               
                   
               
               
                   
               
             
             
               
                 U 1  = /Products 00000 /Music 00002 /CD 00012 /Seller 008212 /Price 04812 / 
               
               
                 {“10”,“12”} 14812   
               
               
                   C 0  = {Products 00000 } 
               
               
                   C 1  = q(//Book,C 0 ,U 1 ) = { } 
               
               
                   Since the candidate set C i  is empty the loop stops at the step i = 1. 
               
               
                   There is no change in the result R 2 . 
               
               
                   
               
             
          
         
       
     
       EXAMPLE 2-2 
       [0108]    
       
         
               
               
             
           
               
                   
                   
               
               
                   
                   
               
             
             
               
                   
                 U 2  = /Products 00000 /Books 00001 /Book 00021 /Seller 00821 /Price 04821 / 
               
               
                   
                 {“5.99”,“6.99”} 14821   
               
               
                   
                 C 0  = {Products 00000 } 
               
               
                   
                 C 1  = q(//Book,C 0 ,U 2 ) = {Book 00021 } 
               
               
                   
                 For each node in C 1 , the following predicate is checked: 
               
               
                   
                 Q 2 .step(1).pred = [ISBN=0316769487] 
               
               
                   
                 Pred 1   before (Book 00021 ) = false (it is NOT in the result path RP 2 ) 
               
               
                   
                 Pred 1   after (Book 00021 ) = false (query to the source) 
               
               
                   
                 Here, there is no direct addition/deletion found at the step i = 1. 
               
               
                   
                 Since C 1 ′ is empty, the loop stops here. There is no change 
               
               
                   
                 in the result set R 2 . 
               
               
                   
                   
               
             
          
         
       
     
       EXAMPLE 2-3 
       [0109]    
       
         
               
             
           
               
                   
               
               
                   
               
             
             
               
                 U 3  = /Products 00000 /Books 00001 /Book 00011 /Seller 00811 /Price 04811 / 
               
               
                 {“6.99”,“5.99”} 14811   
               
               
                 C 0  = {Products 00000 } 
               
               
                 C 1  = q(//Book,C 0 ,U 3 ) = {Book 00011 } 
               
               
                 For each node in C 1 , the following predicate is checked: 
               
               
                 Q 2 .step(1).pred = [ISBN=0316769487] 
               
               
                 Pred 1   before (Book 00011 ) = true (it was in the result path) 
               
               
                 Pred 1   after (Book 00011 ) = true (query to the source) 
               
               
                 There is no direct addition/deletion found at the step 1. Since C 1 ′ = 
               
               
                 {Book 00011 }, the loop proceeds to the step 2: 
               
               
                 C 2  = q(/Seller,{Book 00011 },U 3 ) = { Seller 00811 } 
               
               
                 For each node in C 2 , the following predicate is checked: 
               
               
                 Q 2 .step(2).pred = [Rating &gt; 3] 
               
               
                 Pred 2   before (Seller 00811 ) = true (it was in the result path) 
               
               
                 Pred 2   after (Seller 00811 ) = true (query to the source) 
               
               
                 There is no direct addition/deletion found at the step 2. Since C 2 ′ = 
               
               
                 {Seller 00811 }, the loop proceeds to the step 3: 
               
               
                 C 3  = q(/Price,{ Seller 00811 },U 3 ) = {Price 04811 } 
               
               
                 For each node in C 3 , the predicate check is done (note that there is no 
               
               
                 predicate at the step 3): 
               
               
                 Pred 3   before (Price 04811 ) = true (it was in the result path) 
               
               
                 Pred 3   after (Price 04811 ) = true (no predicate) 
               
               
                 There is no direct addition/deletion found at the step 3. Since C 3 ′ = 
               
               
                 {Price 04811 }, the loop proceeds to the step 4: 
               
               
                 C 4  = q(text( ), {Price 04811 },U 3 ) = {−“6.99” 14811 ,+“5.99” 14811 } 
               
               
                 For each node in C 4 , the predicate check is done: 
               
               
                 Pred 4   before (−“6.99” 14811 ) = true (it was in the result path) 
               
               
                 Pred 4   after (−“6.99” 14811 ) = true (node.update_type = ‘delete’) 
               
               
                 Pred 4   before (+“5.99” 14811 ) = false (it is deleted) 
               
               
                 Pred 4   after (+“5.99” 14811 ) = true (node.update_type = ‘add’) 
               
               
                 Here direct addition and deletion are found: 
               
               
                 Add 4  = {“5.99” 14811 }, Del 4  = {“6.99” 14811 } 
               
               
                 Since this is the last step, 
               
               
                 R +  = {“5.99” 14811 }, R −  = {“6.99” 148111 } 
               
               
                 The result set is updated as: R 2  = {“6.99” 14811 } 
               
               
                   
               
             
          
         
       
     
         [0110]     Although the foregoing has focused on processing the two primitive update operations of adding and deleting leaf nodes, it can be more efficient to handle a complex update, such as adding or deleting subtrees, holistically rather than by decomposing it into the primitive operations. The process for the primitive updates can be extended to handle the complex updates of adding or deleting subtrees. In this case, the U.path becomes a branch that ends with a subtree from the last node, this is the added or deleted subtree. The direct effects can be determined by applying the Axis&amp;Label test and the Predicates test on this branch. Once the direct effects are discovered, the indirect ones can be discovered in the same way as described above.  
         [0111]     Generally, source updates may occur simultaneously with the view maintenance process. Consider this scenario, an update U 1  occurs and is reported to the cache manager, thus, the cache manager initiates a view maintenance process to update the cached views according to U 1 . At this time a new update U 2  occurs at the source before the source query processor processes the queries which the maintenance process of U 1  is using to maintain the views. In this case, processing these queries at the source will include the effects of U 2  as well as those of U 1 . Then when U 2  is reported to the cache manager, a new maintenance process will be initiated to maintain the views according to U 2 . This second maintenance process will typically need to issue queries to the source to maintain the views. However, this second maintenance process could take advantage of the fact that the effect of U 2  has already been incorporated in the answers of the queries that were issued in response to U 1 . If such cases are detected, the view maintenance process could be made more efficient by reducing the number of source queries used to maintain the views. One embodiment to detect such cases is to use time-stamps for all the updates and the query answers received from the source; with that, the cache manager can determine which update effects have been incorporated in which answers. Caching systems normally cache the results of multiple expressions. Upon receiving an update U the presented maintenance algorithm can be run to maintain every expression separately. However, if many of these expressions have significant overlap in their structure, the process can maintain such collections collectively to improve efficiency. For example, efficiency can be gained by evaluating the predicates without source queries.  
         [0112]     The invention has been described in terms of specific examples which are illustrative only and are not to be construed as limiting. The invention may be implemented in digital electronic circuitry or in computer hardware, firmware, software, or in combinations of them. Apparatus of the invention may be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a computer processor; and method steps of the invention may be performed by a computer processor executing a program to perform functions of the invention by operating on input data and generating output. Suitable processors include, by way of example, both general and special purpose microprocessors. Storage devices suitable for tangibly embodying computer program instructions include all forms of non-volatile memory including, but not limited to: semiconductor memory devices such as EPROM, EEPROM, and flash devices; magnetic disks (fixed, floppy, and removable); other magnetic media such as tape; optical media such as CD-ROM disks; and magneto-optic devices. Any of the foregoing may be supplemented by, or incorporated in, specially-designed application-specific integrated circuits (ASICs) or suitably programmed field programmable gate arrays (FPGAs).  
         [0113]     From the foregoing disclosure and certain variations and modifications already disclosed therein for purposes of illustration, it will be evident to one skilled in the relevant art that the present inventive concept can be embodied in forms different from those described and it will be understood that the invention is intended to extend to such further variations. While the preferred forms of the invention have been shown in the drawings and described herein, the invention should not be construed as limited to the specific forms shown and described since variations of the preferred forms will be apparent to those skilled in the art. Thus the scope of the invention is defined by the following claims and their equivalents.