Method for Presenting Information on Display Devices of Varying Sizes

1. Field of the Invention

The present invention relates generally to computer databases and more particularly to presenting information on display devices of varying sizes.

2. Discussion

Traditionally, display devices for computer systems have been of the same approximate size. For example, the usual display device consists of a monitor whose overall dimensions are similar to those of consumer-oriented television sets. The size of standard monitor screens (about 13 to 19 inches diagonally) has been assumed (implicitly or explicitly) by most interface designers. The result of this is that much of the previous work on interfaces (in particular interfaces to information systems) does not scale well to displays of smaller than usual size.

Examples of where this is true are mobile computers, pen computers, and PDAs. The current small display sizes of these machines give rise to the problem of trying to display large amounts of data in a very limited area, and doing so without sacrificing clarity and coherence. Clearly, one solution is to simply show all the data on the screen and have the user navigate (using scrollbars, for instance) through all the information. Anyone who has had to scroll through large amounts of data in this fashion knows how frustrating this process can become. Furthermore, this approach has the effect of very quickly confusing the user, especially in situations where the information items displayed contiguously on the screen are not logically related to each other.

In the area of hypertext, the relevant research issues are more in the nature of helping the user keep track of their place while reading the hypertext information. In that context the use of Overview Diagrams has been suggested (see for example, J. Nielsen, The art of navigating through hypertext, Communications of the ACM, 33(3), March 1990). This is a technique for providing a high-level view of the information. However, overview diagrams are not generated automatically, they provide information about the entire document, and are not dependent on any database-related information.

In the area of database interfaces, the main emphasis has been the creation of easy-to-use interfaces. For example, the PICASSO graphical interface provided a tool for inexperienced users to graphically enter database queries and receive information about the semantics of their query (Please see, H.-J. Kim, H. F. Korth, and A. Silberschatz, PICASSO: a graphical query language, Software Practice and Experience, 18(3):169-203, March 1988).

The designer of QBE (Query by Example) provided an interface allowing users to visually query a database by providing an example of the type of answer they were looking for (see, M. M. Zloof. OBE/QBE: A language for office and business automation, IEEE Computer, pages 13-22, May 1981).

Other systems such as OdeView do make use of semantic links to offer the user possible query paths (Please see, R. Agrawal, N. H. Gehani, and J. Srinivasan, Odeview: The graphical interface to Ode, Proceedings of ACM-SIGMOD 1990 International Conference on Management of Data, Atlantic City, N.J., pages 34-43, May 1990). However, these systems present the user with all possible paths, and do not limit the paths to the relevant ones. They do not use a threshold to determine relevancy either. This is also true for other systems such as ISIS (Please see, P. C. Kanellakis, K. J. Goldman, S. A. Goldman and S. B. Zdonik, Isis: Interface for a semantic information system, Proceedings of ACM-SIGMOD 1986 International Conference on Management of Data, Austin, 1985).

It is therefore an important object of the present invention to overcome one or more disadvantages and limitations of the prior art.

It is a primary object of the present invention to automate how information is optimally displayed on a small computer display.

It is another object of the present invention to display information about a related subset of all the data at any one time.

It is another object of the present invention to prioritize related subsets of data to determine how to display the information.

The present invention is a method for presenting information on display devices of varying sizes. In particular, the approach allows a user to make use of very small display surfaces, such as those found on mobile computers and personal digital assistants (PDAs). The usefulness of this method is that it determines which information the user is likely to want to examine at the same time, hence reducing the amount of data that needs to be presented at any one time. The approach can be tuned to any combination of screen size and information granularity (i.e., the size of data items).

Large schemata (consisting of numerous tables) should be split up into subsets each of which contains a smaller number of tables. Of course, each subset needs to be small enough so that it can be conveniently displayed on a small screen. A feature of the approach is that each subset contains tables that are logically related to each other in some fashion. The actual nature of the "relationship" can depend on many factors, but it is currently based on a set of queries that the user has declared to be "most likely" queries.

Summarily, the present invention is a method for sending data from a database to a computer output device where the database includes a plurality of tables for holding the data. The database has a schema indicative of relationships between the tables. The tables have attributes which contain the data. The method comprises the step of processing a query of the database where the query contains query tables. Another step is to determine weights for each of the query table pairs where the weights are indicative of the occurrence of these query tables together in previous queries. Also the method performs the step of determining sets of the query tables based on the weights, and sending to the computer output device one of the sets.

Additional advantages and features of the present invention will become apparent from the subsequent description and the appended claims, taken in conjunction with the accompanying drawings, in which:

FIG. 1 is functional flow block diagram showing the top-level functions for performing the method for presenting information on display devices of varying sizes;

FIG. 2 is an entity relationship diagram showing a database schema as an example of how to determine Table Connected Schema Subcomponents (TCSSs);

FIG. 3 is a flowchart showing how a set of tables is chosen in determining the TCSSs;

FIG. 4 is a flowchart showing the procedure of making a table the focus of a query;

FIG. 5 is a flowchart showing the procedure of removing focus from a table;

FIG. 6 is an entity relationship diagram showing a database schema with sample relationship and attribute values;

FIG. 7 is a PDA display serving as an example of the output of the present invention; and

FIG. 8 is a network diagram showing tables placed in separate databases across the network which is connected to a printer and the Internet.

As shown in FIG. 1, the method consists of performing the following steps.

1. Represent the schema in the form of a weighted graph G. This step is performed at block 20.

2. Use join queries, if any, from the set of frequently executed queries to generate edges belonging to the graph G. This step is performed at block 30.

3. Find a threshold value, t, such that after pruning the graph by dropping edges with weights lower than t, the largest connected sub-schemata that are obtained from the pruned graph can be displayed on the screen completely. This is an iterative process. This step is performed at block 40.

4. Individual tables can be made the focus which adds emphasis to relationships with respect to a given table. This step is performed at block 50.

5. Eventually, focus can also be removed from tables which were initially made foci. Block 60 performs this step.

Block 50 and block 60 are optional steps for the present invention. They can be added to increase the functionality of the present invention, but even when added, they may not always be performed. The material below describes each of the steps in greater detail.

Suppose a set of queries that a user executes often on the database is accessible. Typically, many of these queries would involve join operations between multiple tables. Consider representing the database schema by a weighted graph, G, consisting of nodes, {N} and edges {E}. Each column in each table of the schema (i.e., each attribute) is represented by a node in this graph. Any binary join operation involving a pair of attributes can be represented by an edge (of weight 1) between the attributes (i.e. nodes in the graph) in the join. As more queries are considered, if there is already an edge between two attributes, the weight of the edge is increased by one.

The pseudocode for this procedure of creating a weighted graph, G, is as follows:

The graph thus constructed represents the strength of relationships between columns of tables in the database schema.

Once this graph is constructed, the graph is then pruned by dropping all edges whose weight is below some selected threshold value. The threshold value is chosen in an iterative manner so that the largest resulting subset of tables still fits in the available screen space.

The resulting graph is processed to choose sets of tables which are connected to each other by at least one edge whose weight exceeds the threshold value. Each set of such connected tables forms what is termed a Table Connected Schema Sub-component (TCSS) of the graph, or simple connected schema sub-component. Notice that the notion of connected sub-components in the graph is not the same as the traditional meaning of the term in graph theory. Here, the fact that individual nodes of the graph belong to a parent table is exploited. Two tables are connected if there is an edge between any of their component nodes (i.e., columns).

The mechanism to obtain Table Connected Schema Sub-components is described in the following pseudocode:

An example is shown in FIG. 2. The schema contains 6 tables and each table (R.sub.1 100, R.sub.2 102, R.sub.3 104, R.sub.4 106, R.sub.5 108, R.sub.6 110) contains columns as shown (a.sub.1, a.sub.2 etc.). The columns with edges drawn between them (both solid as well as dotted) correspond to the join paths derived from a set of SQL queries against these tables. For example, there is a join path 114 between R.sub.1 -a.sub.1 and R.sub.2 -a.sub.1. The number above each edge indicates the weight of the edge. For example, join path 112 has weight 114 of "3". The graph corresponding to this schema contains 17 nodes (one for each column in every table in the schema), and 6 edges as drawn in FIG. 2. Given a threshold value of 3, the only three edges which have at least this value are shown as solid lines in the FIG. 2: join path 112, join path 116, and join path 118. The edges with dotted lines are those whose weights are lower than the threshold value. Such a graph yields three connected sub-components: S.sub.1 containing tables R.sub.1 100, R.sub.2 102 and R.sub.4 106; S.sub.2 containing tables R.sub.3 104 and R.sub.5 108; and S.sub.3 containing just table R.sub.6 110.

It should be understood that the present invention is not limited to the situation where the database resides solely on one computer, but also encompasses the situation where the database and its tables may be distributed across several computers. Also, the present invention is not limited to where tables to be queried are contained only in one database, but may be found in several databases.

By choosing the threshold value appropriately (depending on the weights of the edges and connectivity of nodes in the original graph, as well as the display size), a set of connected schema sub-components can be constructed such that each set of tables fits in one display screen. Notice that these tables are logically connected to each other since they are derived from frequently occurring join paths between them. Considering that the join paths were themselves obtained from a suite of frequently used queries, it is expected that these table groupings represent the information that a user would like to see together. If the initial threshold chosen is too high, there may be many sub-components which contain very few tables together. Therefore the threshold value is reduced until a suitable value is found.

Notice also that if no join information is available, there are many sub-components each of which contains just one individual table, i.e. there will be as many TCSSs as tables in the schema. This corresponds to the situation where the preprocessing has been unable to yield natural groupings of tables in the schema. The user may choose to either view the tables one by one or view all the tables together and use traditional methods of navigation (such as scroll bars).

FIG. 3 shows how the correct set of tables to be displayed is chosen. The start block 200 indicates that processing begins at block 210. Block 210 sets the threshold to the highest edge weight. Block 220 gets all the TCSS from graph G. Decision block 230 inquires whether the largest TCSS can fit within the size of the computer output display. If it cannot, then block 240 reduces the threshold by 1. Decision block 250 inquires whether the threshold is 0. If it is, processing continues at block 260; else processing returns to block 220.

If decision block 230 determines that the largest TCSS can fit within the size of the computer output display, then block 260 displays the tables that are in the TCSS. Processing for this aspect of the present invention then terminates at stop block 270.

For each of the tables displayed, only those columns that participate in joins between the various tables are displayed on the screen. Once a group of related tables is presented to the user, there is an option of making a specific table the focus. Making a table a focus involves displaying all the columns of the given table, and in addition, all other columns (belonging to other tables) that share an edge with columns belonging to the table in focus. This results in displaying all the tables which have columns sharing edges with the columns of the table in focus. The additional tables that are now displayed are those which share edges with the columns of the table in focus--regardless of the weight of the edge involved.

In this fashion, a user could navigate the entire schema by making different tables the focus. Of course, if when a particular table is made the focus and too many other associated tables are to be shown, there can be scrolling through the screen or having a second threshold value to prune the number of items being displayed. The idea of making a table the focus is to indicate interest in all other tables that are logically related to this focused table.

For example, referring back to FIG. 2, while displaying sub-component S.sub.2 only tables R.sub.3 104 and R.sub.5 108 are shown on the screen. If, now, R.sub.3 104 is made the focus, the additional tables that are displayed alongside the original two tables are R.sub.4 106, R.sub.6 110 and R.sub.1 100, since all these tables have edges in common with columns in R.sub.3 104.

FIG. 4 shows this procedure of making table T the focus. The start block 300 indicates that processing begins at block 310. Block 310 gets the graph G. Decision block 320 determines if there are more edges in the graph. If there are no more, then block 330 adds table T to the set of focus tables and processing for this aspect of the invention terminates at stop block 340.

If Decision block 320 determines that there are more edges in the graph, then block 350 gets edge E. Next, decision block 360 determines if that edge E involves table T. If it does not, then processing returns to decision block 320. If decision block 360 does determine that edge E involves table T, then block 370 obtains the other table T1 involved in edge E. Processing continues at decision block 380.

If Decision block 380 determines that T1 is displayed, then processing returns to decision block 320. If it is not, then block 390 displays T1 and adds T1 to the list as introduced by T.

When a table is removed as the focus, all the tables containing edges of weights lower than the threshold value that the table of focus introduced into the display are removed. Since there is no guarantee that the user will remove tables as focus in the reverse order that they were made foci, the order in which tables were made foci is maintained so that they can be undone in the reverse order. This is somewhat similar to hypertext navigation systems, i.e. navigation of a schema in this fashion is akin to a stack of traversals.

The first degree neighbors of a table, T, is defined to be all other tables whose columns share an edge with columns from T. This is a schema wherein making a table the focus involves displaying all first degree neighbors of this table. One could extend this notion and display nth order neighbors where n is a tunable parameter.

FIG. 5 shows this procedure of removing focus from table T. The start block 400 indicates that processing begins at decision block 410. If decision block 410 determines that the focus-tables do not contain table T, then processing branches to block 450 which will be discussed below. If decision block 410 determines that the focus-tables do contain table T, then processing continues at block 420 which gets the next table T1 from the focus-tables.

Decision block 430 determines if table T is the same as table T1. If they are, then processing branches to block 450. If T is not the same as T1, then for each table T2, block 440 removes table T2 from the list of tables being displayed. Block 450 displays the list of tables and processing terminates for this aspect of the invention at the stop block 460.

The following example uses tables R1 510, R2 512, R3 514, R4 516 with the relationships shown in FIG. 6 (these relationships are similar to the ones shown in FIG. 2).

Table R1 may assume the following values:

Table R2 may assume the following values:

Table R3 may assume the following values:

Table R4 may assume the following values:

A user may request that data from the tables R1, R2, R3, and R4 be sent to the user's PDA screen by specifying the following query:

SELECT DISTINCTROW R1.›Employee Grade!, R1.›Employee Id!, R2.Salary, R4.›Employee Name!, R4.›Work Phone Number!, R3.›County of Residence!, R3.›Employee Home Address!, R3.›Home Phone Number!, *

FROM ((R1 INNER JOIN R2 ON R1.›Employee Grade!=R2.›Employee Grade!) INNER JOIN R3 ON R1.›Employee Id!=R3.›Employee Id!) INNER JOIN R4 ON (R4.›Employee Id!=R3.›Employee Id!) AND (R1.›Employee Id!=R4.›Employee Id!)

ORDER BY R1.›Employee Grade!;

The query shown above results in the following four paths each of weight one being generated:

(R1.Employee Grade, R2.Employee Grade)

(R1.Employee Id, R3.Employee Id)

(R3. Employee Id, R4. Employee Id)

(R1.Employee Id, R4.Employee Id)

The present invention processes the query in accordance with the method disclosed above to display results 580 that will fit within the screen 590 of the PDA 600 as shown in FIG. 7.

The preferred embodiment has a SQL parser that, given, a set of queries (Select queries) produces join path sets of the form R.sub.i.A.sub.j,R.sub.k.A.sub.l . . . Each such set contains attributes that occur together in a single query and contribute one edge for every pair in the set. Using the above sets of generated join path information and a schema's metadata (i.e. names of tables and their columns), another program generates the graph describing the path information. Given a threshold (currently an integer value), this program then generates the various sub-components of the graph with table grouping information. There is also a command line interface which allows different tables to be the focus (and subsequently remove them). All the code mentioned above runs on Unix, but the present invention is not limited to this specific software.

For example, another embodiment can run on Windows 3.1. Given a schema and a threshold value, the program determines the largest connected sub-component and displays it on the screen. Using mouse interactions, different tables can be made foci (and, later, removed as foci as well) in the manner discussed earlier.

FIG. 8 shows another embodiment of the invention. FIG. 8 is a network diagram showing tables placed in separate databases across a local network which is connected to a printer and the Internet. A user on computer 650 may query for information contained in tables contained in database 660 on computer 662 and database 670 on computer 672. This embodiment can use the present invention to prioritize information that is to be sent across a network (such as the Internet 680). In this situation, the present invention can send information to the user on computer 650 which the user is more likely to primarily wish to view. The present invention can also direct the output to a printer 690 located on a local network 700.

The embodiments which have been set forth above were for the purpose of illustration and were not intended to limit the invention. It will be appreciated by those skilled in the art that various changes and modifications may be made to the embodiments described in this specification without departing from the spirit and scope of the invention as defined by the appended claims.