Abstract:
A system and method are described for filtering certain rows of a table while at the same time maintaining rows illustrating the ancestry of the filtered rows. For example, a computer-implemented method according to one embodiment of the invention comprises: receiving user-specified filtering criteria from a client comprising a value or range of values for filtering the rows of a table; filtering the table rows as indicated by the user-specified filtering criteria to generate a set of filtered rows; and generating a table containing the filtered rows and other rows which are ancestor rows to the filtered rows, notwithstanding the fact that one or more of the ancestor rows are not part of the set of filtered rows based on the user-specified filtering criteria, and excluding all other rows from the table.

Description:
BACKGROUND 
       [0001]    1. Field of the Invention 
         [0002]    This invention relates generally to the field of data processing systems. More particularly, the invention relates to a system and method for implementing a non-destructive tree filter. 
         [0003]    2. Description of the Related Art 
       Multi-Tiered Enterprise Computing Systems 
       [0004]    Traditional client-server systems employed a two-tiered architecture such as that illustrated in  FIG. 1   a . Applications  102  executed on the client side  100  of the two-tiered architecture are comprised of a monolithic set of program code including a graphical user interface component, presentation logic, business logic and a network interface that enables the client  100  to communicate over a network  103  with one or more servers  101 . A database  104  maintained on the server  101  provides non-volatile or “persistent” storage for the data accessed and/or processed by the application  102 . 
         [0005]    The “business logic” component of the application represents the core program code of the application, i.e., the rules governing the underlying business process (or other functionality) provided by the application. The “presentation logic” describes the specific manner in which the results of the business logic are formatted for display on the user interface. The “database”  104  includes data access logic used by the business logic to store and retrieve data. 
         [0006]    The limitations of the two-tiered architecture illustrated in  FIG. 1   a  become apparent when employed within a large enterprise. For example, installing and maintaining up-to-date client-side applications on a large number of different clients is a difficult task, even with the aid of automated administration tools. Moreover, a tight coupling of business logic, presentation logic and the user interface logic makes the client-side code very brittle. Changing the client-side user interface of such applications is extremely hard without breaking the business logic, and vice versa. This problem is aggravated by the fact that, in a dynamic enterprise environment, the business logic may be changed frequently in response to changing business rules. Accordingly, the two-tiered architecture is an inefficient solution for enterprise systems. 
         [0007]    In response to limitations associated with the two-tiered client-server architecture, a multi-tiered architecture has been developed, as illustrated in  FIG. 1   b . In the multi-tiered system, the presentation logic  121 , business logic  122  and database  123  are logically separated from the user interface  120  of the application. These layers are moved off of the client  125  to one or more dedicated servers on the network  103 . For example, the presentation logic  121 , the business logic  122 , and the database  123  may each be maintained on separate servers,  126 ,  127  and  128 , respectively. 
         [0008]    This separation of logical components and the user interface provides a more flexible and scalable architecture compared to that provided by the two-tier model. For example, the separation ensures that all clients  125  share a single implementation of business logic  122 . If business rules change, changing the current implementation of business logic  122  to a new version may not require updating any client-side program code. In addition, presentation logic  121  may be provided which generates code for a variety of different user interfaces  120 , which may be standard browsers such as Internet Explorer® or Netscape Navigator®. 
         [0009]    The multi-tiered architecture illustrated in  FIG. 1   b  may be implemented using a variety of different application technologies at each of the layers of the multi-tier architecture, including those based on the Java 2 Enterprise Edition™ (“J2EE”) standard, the Microsoft .NET standard and/or the Advanced Business Application Programming (“ABAP”) standard developed by SAP AG. For example, as described below, in a J2EE environment, the business layer  122 , which handles the core business logic of the application, is comprised of Enterprise Java Bean (“EJB”) components with support for EJB containers. Within a J2EE environment, the presentation layer  121  is responsible for generating servlets and Java Server Pages (“JSP”) interpretable by different types of browsers at the user interface layer  120 . 
       J2EE Application Server Architecture 
       [0010]      FIG. 1   c  illustrates a typical J2EE application server  200  in which the presentation layer is implemented by a “Web container”  211  and the business layer is implemented by an Enterprise Java Bean (“EJB”) container  201 . Containers are runtime environments which provide standard common services  219 ,  209  to runtime components. For example, the Java Naming and Directory Interface (“JNDI”) is a service that provides application components with methods for performing standard naming and directory services. Containers also provide unified access to enterprise information systems  217  such as relational databases through the Java Database Connectivity (“JDBC”) service, and legacy computer systems through the J2EE Connector Architecture (“JCA”) service. In addition, containers provide a declarative mechanism for configuring application components at deployment time through the use of deployment descriptors. 
         [0011]    As illustrated in  FIG. 1   c , each layer of the J2EE architecture includes multiple containers. The Web container  211 , for example, is itself comprised of a servlet container  215  for processing servlets and a Java Server Pages (“JSP”) container  216  for processing Java server pages. The EJB container  201  includes three different containers for supporting three different types of enterprise Java beans: a session bean container  205  for session beans, a entity bean container  206  for entity beans, and a message driven bean container  207  for message driven beans. A more detailed description of J2EE containers and J2EE services can be found in R AGAE  G HALY AND  K RISHNA  K OTHAPALLI , SAMS T EACH  Y OURSELF  EJB  IN  21 D AYS  (2003) (see, e.g., pages 353-376). 
       SUMMARY 
       [0012]    A system and method are described for filtering certain rows of a table while at the same time maintaining rows illustrating the ancestry of the filtered rows. For example, a computer-implemented method according to one embodiment of the invention comprises: receiving user-specified filtering criteria from a client comprising a value or range of values for filtering the rows of a table; filtering the table rows as indicated by the user-specified filtering criteria to generate a set of filtered rows; and generating a table containing the filtered rows and other rows which are ancestor rows to the filtered rows, notwithstanding the fact that one or more of the ancestor rows are not part of the set of filtered rows based on the user-specified filtering criteria, and excluding all other rows from the table. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]    A better understanding of the present invention can be obtained from the following detailed description in conjunction with the following drawings, in which: 
           [0014]      FIG. 1   a  illustrates a traditional two-tier client-server architecture. 
           [0015]      FIG. 1   b  illustrates a prior art multi-tier client-server architecture. 
           [0016]      FIG. 1   c  illustrates a multi-tiered application server architecture according to the Java 2 Enterprise Edition (“J2EE”) standard. 
           [0017]      FIG. 2  illustrates a model view controller (“MVC”) architecture implemented in accordance with one embodiment of the invention. 
           [0018]      FIG. 3  illustrates a filtering operation within an exemplary table. 
           [0019]      FIG. 4  illustrates an exemplary hierarchical tree and tree table. 
           [0020]      FIG. 5  illustrates a context including a recursive context not and associated attributes, some of which are displayed within the table in  FIG. 4 . 
           [0021]      FIG. 6  illustrates an exemplary table prior to the execution of a filtering operation. 
           [0022]      FIG. 7  illustrates filtering performed without maintaining ancestor rows of the filtered rows. 
           [0023]      FIG. 8   a  illustrates a system architecture according to one embodiment of the invention. 
           [0024]      FIG. 8   b  illustrates a computer-implemented method according to one embodiment of the invention. 
           [0025]      FIG. 9  illustrates a table filtered in accordance with one embodiment of the invention. 
           [0026]      FIG. 10  illustrates the results of the table from  FIG. 9  filtered a second time in accordance with one embodiment of the invention. 
           [0027]      FIG. 11  illustrates a table filtered in accordance with another embodiment of the invention in which text is displayed within ancestor rows. 
           [0028]      FIG. 12  illustrates an application server architecture on which embodiments of the invention may be implemented. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0029]    Described below is a system and method for performing filtering operations on hierarchical tables while maintaining hierarchical relationships for the results of the filtering operations. Throughout the description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and devices are shown in block diagram form to avoid obscuring the underlying principles of the present invention. 
         [0030]    The display of data records in tables and forms, and the associated editing of the tables and forms (e.g., selecting, deleting, sorting, etc) by clients are central functions in Web-based applications. Thus, various techniques are provided within the J2EE architecture for creating and working with tables in response to client requests. In particular, under a model-view-controller (“MVC”) architecture, illustrated in  FIG. 2 , Web-based content using tables may be created within the Web Container  211  using “controllers”  240  and “views”  251 - 252  that operate in conjunction with “models”  260  within the EJB container  201 . A detailed description of the MVC architecture is beyond the scope of the present application but, briefly, the controller  240  manages the underlying table structure and data, referred to in  FIG. 2  as a table node  250 . The table structure is presented to Web clients  220  in the form of one or more “views”  251 - 252  which indicate, for example, how the table is presented within a Web page. Controllers may be implemented by servlets and views by Java server pages. The model  260  within the EJB container  201  provides an interface between the controller  240  and the underlying table data stored within the database  123 . See, e.g., G HALY  and K OTHAPALLI  mentioned above for additional detail on the MVC architecture at pages 148-152. 
         [0031]    A context node  250  may be filtered and/or otherwise modified in response to requests from Web clients. For example, as part of a search request a Web client may designate a filtering operation such as “only display client records in the table beginning with the letters DE” or “only display client records with a value of 1000.” As a result the table node will be filtered and the results provided to the client in the form of a filtered table. 
         [0032]    Various existing application server platforms employ a Model View Controller architecture to generate views for requesting clients. For example, “Web Dynpro” is a programming paradigm developed by SAP AG (the assignee of the present application) which implements a Model View Controller architecture for generating and displaying views (e.g., tables) to end users. While certain embodiments of the invention are described herein within the context of Web Dynpro, it should be noted that the underlying principles of the invention are not limited to any particular programming paradigm. 
         [0033]    As illustrated in  FIG. 3 , a Web Dynpro table  300  represents a two-dimensional data set arranged in rows  301 ,  303  and columns  302 . The table  302  represents data from the view context and receives its data from a multi-element context node, represented by node  250  in  FIG. 2 . At runtime, each element of the multi-element context node is represented as a table row. The number of table rows is therefore equal to the number of node elements. The table columns correspond to the node attributes. 
         [0034]    The controller  240  within the Model View Controller architecture implements a table filter which filters table rows based on user-specified filtering criteria. In the exemplary table  300  shown in  FIG. 3 , the filtering row is the first row  301 . In the illustrated example, the column labeled “Structure Element Description” has been filtered for a value of 1000 and the filter has been applied to all rows of the table, resulting in two rows  303  being displayed which correspond to the value of 1000. 
         [0035]    As illustrated in  FIG. 4 , within programming environments such as Web Dynpro, a “Tree”  400   a  or “Table Tree”  400   b  may be used to represent hierarchical structures. In a table tree  400   b , table rows are presented in a specific order to indicate parent-child relationships.  FIG. 4  illustrates an exemplary hierarchical table tree in which row  401  is a parent to rows  402 - 403 ; row  403  is a parent to row  404 ; row  404  is a parent to row  405 ; and row  405  is a parent to rows  406 . As illustrated in the figure, the position and graphical features associated with each element within a particular column  410  identify the position that the element occupies within the hierarchy. 
         [0036]    In a model-view controller architecture such as the one shown in  FIG. 2 , a context, implemented as context node  250 , provides data to the user interface elements within a view  252 ,  251 . For a Tree  400   a  or Table Tree  400   b , context data may be embodied in “recursive” context nodes with each hierarchical level represented by a different recursive node. In  FIG. 4 , the table  400   b  indicates five levels starting from 0. Consequently, the table has a four recursive node context. 
         [0037]      FIG. 5  illustrates an exemplary context  500  having a node called Loop  501  and its recursive nodes represented by the recursive node called Repeater  502 . The dual arrows within the folder icon identifies the Repeater node as a recursive node, i.e., a node with sub-nodes which are not visually displayed. Thus, for simplicity, recursive nodes are represented as only a single node even though they have sub-nodes. The number of recursive sub-nodes depends on the number of levels in the hierarchy and the number of dependent sub-sub-node elements. 
         [0038]    Each recursive node  502  has attributes  503  which may be displayed within a view for the user. An attribute corresponds to a column in a table tree. For example, the attributes “id” and “level” are displayed within columns  411  and  412  of tree table  400   b . A recursive node element corresponds to a row on the table. Because the table  400   b  illustrates 18 rows, the context node Repeater has 18 elements. 
         [0039]    Each sub-node is attached to an element of its parent element and so on. A node or an element cannot exist independently; it has to be attached to a parent element. In other words, a sub-node element can only be created from its parent element and can also be accessed only from its parent element. 
         [0040]    One problem which exists is related to how different elements in the hierarchy are displayed in response to a table filtering operation. If the same rules as those applied to filtering a flat table are used, i.e., the filtered rows that do not match the filter criteria are not shown, the hierarchy may become inaccurate. 
         [0041]    This is illustrated in  FIGS. 6 and 7 . In  FIG. 6 , under the column Name, Node  3  in row  603  has Node  2  in row  602  for a parent, Node  13  in row  605  has Node  9  in row  604  for a parent, Node  23  in row  607  has Node  21  in row  606  for a parent, and Node  30  in row  609  has Node  28  in row  608  for a parent. If the column Name is filtered for a string value of “3” using a classical flat table representation of a filtered table (i.e., showing only the rows that meet the filtering criteria), the resulting table  700  is illustrated in  FIG. 7 . The problem with this representation is that the Node  23  and Node  30  seem to both have Node  13  as a parent node. In addition, Node  3  and Node  13  also appear to have the same parent node. In other words, the last leaf node of a tree branch may meet the filtering criteria, but not its parent nodes. So, the classical presentation of a filtered flat table shows the leaf node as a child of a grand-parent node. Consequently, this representation may be confusing to the end user. 
         [0042]    One embodiment of the invention solves this problem by allowing hierarchical rows to be filtered without destroying the visual depiction of the hierarchy. The filtered rows having passed the filtering criteria are shown from the root node with all parent nodes expanded. The data within the filtered rows may be highlighted (e.g., bolded, colored) to distinguish the filtered data. The rows which have not passed the filter&#39;s criteria may show no data, or data in a non-highlighted format (e.g., relatively small, un-bolded, and/or uncolored characters). 
         [0043]    An architecture according to this embodiment of the invention is illustrated in  FIG. 8   a  which shows a controller  810  within a model view controller architecture generating a table view  802  in response to user requests. The controller  810  of this embodiment includes a non-destructive hierarchical tree filter  801  for filtering table data within a node  803  (e.g., a multi-element context node) while still maintaining the visual representation of the hierarchy between table rows. In one embodiment, the user specifies filtering criteria through the client  220  (e.g., by entering the criteria via a Web browser) and the non-destructive table row filter responsively filters the model data  260  to generate a filtered table such as the one illustrated in  FIG. 9 . In one embodiment, the client sends request and receives responses using the Hypertext Transport Protocol (HTTP). However, the underlying principles of the invention are not limited to any particular protocol. 
         [0044]    A method implemented by the non-destructive hierarchical tree filter  801  is illustrated in  FIG. 8   b . At  850  the non-destructive hierarchical tree filter  801  applies the filtering criteria specified by the end user to filter the table rows. At  851 , the non-destructive hierarchical tree filter  801  identifies the ancestor rows/nodes of the filtered rows/nodes. Finally, at  852 , the non-destructive hierarchical tree filter  801  generates a table view which maintains the hierarchical relationship between the filtered rows and the ancestor rows. As described below, the non-destructive hierarchical tree filter  801  highlights or provides some other graphical and/or textual indication to contrast the filtered rows and the ancestor rows. 
         [0045]      FIG. 9  illustrates an exemplary table generated in response to a filtering operation in which the hierarchy associated with each of the filtered rows is preserved. In this embodiment, the rows  901  that do not meet the user-specified filtering criteria have no data. In contrast to the table illustrated in  FIG. 7 , the table in  FIG. 9  clearly shows that the Node  23  and Node  30  do not share the same parent node and that Node  3  and Node  13  do not share same parent node. The data for all the rows meeting the filtering criteria are shown and the full path to the ancestor rows is displayed (e.g., parent nodes, grand-parent nodes, etc). 
         [0046]    As illustrated in  FIG. 10 , the user may specify additional filtering criteria to filer the table rows a second time. In  FIG. 10 , for example, the Cost attribute has been filtered using the value 6,002. The only row that meets both sets of filtering criteria (i.e., Name=3 and Cost=6002) is row  605 . As such, row  605  is displayed along with the ancestor rows  901  of row  605  to maintain the hierarchy. As illustrated in  FIGS. 9-10 , any rows which are not an a filtered row or an ancestor to a filtered row are excluded from the resulting table. 
         [0047]    In the above representations, the nodes that do not match the criteria have no data. In another embodiment, the data of the filtered rows is distinguished form the other data using highlighting. For example, the data of the filtered rows may be shown in bold, and the data in the remaining rows may be shown in normal text and/or in a relatively smaller font. Various other techniques for distinguishing the rows which meet the filtering criteria may be employed while still complying with the underlying principles of the invention (e.g., using color, font, size, etc). 
         [0048]    An exemplary table according to this embodiment is illustrated in  FIG. 11 , which shows one row  1101  that meets the filtering criteria. The data of the filtered row  1101  is in bold and the data within the remaining rows  1102  is displayed in smaller, normal text. Thus, the user can easily identify the rows which meet the filtering criteria as well as the ancestor rows associated with the filtered rows. 
         [0049]    Although the embodiments of the invention are described herein within the context of a table tree  400   b , the same general principles also apply to tree  400   a . If the filter table is a java Class it can be implemented as a common class without any additional coding for the developer. 
         [0050]    In summary, a system and method to filter and present filtered hierarchical rows in a tree table or tree has been described. The filtered rows are presented without destroying the hierarchical representation so the user is not confused about the location of the filtered rows within the hierarchy. The rows that do not meet the filter criteria show no data, or data in a different format (e.g., a small font), but they are still displayed so the hierarchy is not destroyed. In one embodiment, the non-destructive hierarchical tree filter is implemented as a common Java Class without the need for additional coding by the developer. 
         [0051]    A system architecture on which embodiments of the invention may be implemented is illustrated in  FIG. 12 . The architecture includes a plurality of application server “instances”  1201  and  1202 . The application server instances  1201  and  1202  each include a group of worker nodes  1212 - 1214  and  1215 - 1216  (also sometimes referred to herein as “server nodes”), respectively, and a dispatcher  1211  and  1212 , respectively. The application server instances  1201 ,  1202  communicate through a central services instance  1200  using message passing. In one embodiment, the central services instance  1200  includes a locking service and a messaging service (described below). The combination of all of the application server instances  1201  and  1202  and the central services instance  1200  is referred to herein as a “cluster.” Although the following description will focus solely on instance  1201  for the purpose of explanation, the same principles apply to other instances within the cluster. 
         [0052]    The worker/server nodes  1212 - 1214  within instance  1201  provide the business and presentation logic for the network applications supported by the system including, for example, the model-video controller architecture described herein. Each of the worker nodes  1212 - 1214  within a particular instance may be configured with a redundant set of programming logic and associated data, represented as virtual machines  1221 - 1223  in  FIG. 12 . In one embodiment, the dispatcher  1211  distributes service requests from clients to one or more of the worker nodes  1212 - 1214  based on the load on each of the servers. For example, in one embodiment, the dispatcher maintains separate queues for each of the  1212 - 1214  in a shared memory  1240 . The dispatcher  1211  fills the queues with client requests and the worker nodes  1212 - 1214  consume the requests from each of their respective queues. The client requests may be from external clients (e.g., browser requests) or from other components/objects within the instance  1201  or cluster. 
         [0053]    In one embodiment, the worker nodes  1212 - 1214  may be Java 2 Enterprise Edition (“J2EE”) worker nodes which support Enterprise Java Bean (“EJB”) components and EJB containers (at the business layer) and Servlets and Java Server Pages (“JSP”) (at the presentation layer). In one embodiment, JSPs are used to implement the different views  1012  described above, and servlets are used to implement the controllers  1010 . In this embodiment, the virtual machines  1221 - 1225  implement the J2EE standard (as well as the additional non-standard features described herein). It should be noted, however, that certain high-level features described herein may be implemented in the context of different software platforms including, by way of example, Microsoft .NET platforms and/or the Advanced Business Application Programming (“ABAP”) platforms developed by SAP AG, the assignee of the present application. 
         [0054]    In one embodiment, communication and synchronization between each of the instances  1201 ,  1202  is enabled via the central services instance  1200 . As mentioned above, the central services instance  1200  includes a messaging service and a locking service. The message service allows each of the servers within each of the instances to communicate with one another via a message passing protocol. For example, messages from one server may be broadcast to all other servers within the cluster via the messaging service (e.g., such as the cache configuration messages described below). Alternatively, messages may be addressed directly to specific servers within the cluster (i.e., rather than being broadcast to all servers). In one embodiment, the locking service disables access to (i.e., locks) certain specified portions of configuration data and/or program code stored within a central database  1245 . The locking service locks data on behalf of various system components which need to synchronize access to specific types of data and program code. In one embodiment, the central services instance  1200  is the same central services instance as implemented within the Web Application Server version 6.3 and/or 6.4 developed by SAP AG. However, the underlying principles of the invention are not limited to any particular type of central services instance. 
         [0055]    In addition, unlike prior systems, one embodiment of the invention shares objects across virtual machines  1221 - 1225 . Specifically, in one embodiment, objects such as session objects which are identified as “shareable” are stored within a shared memory region  1240 ,  1241  and are made accessible to multiple virtual machines  1221 - 1225 . Creating new object instances from scratch in response to client requests can be a costly process, consuming processing power and network bandwidth. As such, sharing objects between virtual machines as described herein improves the overall response time of the system and reduces server load. 
         [0056]    In a shared memory implementation, a shared memory area  1240 ,  1241  or “heap” is used to store data objects that can be accessed by multiple virtual machines  1221 - 1225 . The data objects in a shared memory heap should generally not have any pointers or references into any private heap (e.g., the private memory regions/heaps of the individual virtual machines). This is because if an object in the shared memory heap had a member variable with a reference to a private object in one particular virtual machine, that reference would be invalid for all the other virtual machines that use that shared object. 
         [0057]    More formally, this restriction can be thought of as follows: For every shared object, the transitive closure of the objects referenced by the initial object should only contain shared objects at all times. Accordingly, in one implementation of the invention, objects are not put into the shared memory heap by themselves—rather, objects (such as the session objects described herein) are put into the shared memory heap in groups known as “shared closures.” A shared closure is an initial object plus the transitive closure of all the objects referenced by the initial object. 
         [0058]    Embodiments of the invention may include various steps as set forth above. The steps may be embodied in machine-executable instructions which cause a general-purpose or special-purpose processor to perform certain steps. Alternatively, these steps may be performed by specific hardware components that contain hardwired logic for performing the steps, or by any combination of programmed computer components and custom hardware components. 
         [0059]    Elements of the present invention may also be provided as a machine-readable medium for storing the machine-executable instructions. The machine-readable medium may include, but is not limited to, flash memory, optical disks, CD-ROMs, DVD ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, propagation media or other type of machine-readable media suitable for storing electronic instructions. For example, the present invention may be downloaded as a computer program which may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection). 
         [0060]    Throughout the foregoing description, for the purposes of explanation, numerous specific details were set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the invention may be practiced without some of these specific details. For example, although many of the embodiments set forth above relate to a Web Dynpro, Java or J2EE implementation, the underlying principles of the invention may be implemented in virtually any client-server environment. Moreover, although some of the embodiments set forth above are implemented within a shared memory environment, the underlying principles of the invention are equally applicable to a non-shared memory environment. Finally, it should be noted that the terms “client” and “server” are used broadly to refer to any applications, components or objects which interact over a network. 
         [0061]    Accordingly, the scope and spirit of the invention should be judged in terms of the claims which follow.