Note: Descriptions are shown in the official language in which they were submitted.
CA 02418753 2003-02-12
METHOD AND SYSTEM FOR DATABASE JOIN DISAMBIGUATION
BACKGROUND OF THE INVENTION
This invention is in the field of information processing, and more
particularly in
the field of modelling and database query generation and the disambiguation
of joins.
Currently, information systems use predefined query techniques to hide the
complexity of Structured Query Language (SQL) and relational databases.
This allows users to specify parameters in order to add some conditions:
Typically, members of Management Information System (MIS) staff build a
database solution by creating user-dedicated tables, relational views or
predefined SQL queries which are then made available to users by means of
menus or similar techniques. In these, systems, if end-users want to change
the purpose of a query they ask the MIS staff to program another query.
Alternatively the user may program the SQL query or command themselves.
However, the syntax of non-procedural structured query language (in
particular SQL) is complex, and typically, the data structure is not expressed
in terms of the users' everyday work. Relational databases store information
as well as metadata (data describing the data organisation) such as tables,
columns, keys, indices, and their structure and design. Although suited to the
overall needs of the customer organisation, these databases will likely
contain
much that is not of interest to a particular user. In addition, although a
query
may be syntactically correct, its results may not be what is expected, due to
the inherent complexity of a large scale database. Indeed, the results may be
totally meaningless.
For these and other reasons modeling tools are often used that allow
conceptual modeling of databases in a graphical form. These tools provide a
layer on top of the database, and allow the underlying database to be
accessed in terms that are more relevant to a particular end application. Such
modeling tools include "Impromptu", "Transformer", and "Architect" by Cognos
Incorporated. Within such systems the join operation is used to synthesize a
CA 02418753 2003-02-12
2
'virtual' table from more than one real table. It is common in the design of
databases, and in the queries that run against them, for there to be more than
one way to join tables - this is known as join ambiguity. Because the results
of
a query depend on the join selected, any query must have a way to choose
which of the available joins is to be used - a process often called join
disambiguation.
An example of a simple join ambiguity is shown in Figure 1. Two tables Table
A 100, Table B 110 each comprising two fields, A1 101, A2 102 and B1 111,
B2 112 respectively, and they are associated by two relationships or joins,
Join 1 120, and Join 2 121. if a query identifies A1 101 and B1 111 then the
ambiguity is that it is unclear whether Join 1 120 or Join 2 121 is the
appropriate one to use.
One way of removing the join ambiguity is to require the user to specify the
join explicitly. Another is to present the possibilities to the user, and
require
that one possibility be chosen before the query can be run. Both of these
approaches create problems, because they require the user to be exposed to,
and understand the detail of, data that are typically not directly related to
the
question that the user wants the database to answer.
Typical examples of a solution requiring the user to select from a number of
options are illustrated in US Patents 6,247,008 "Relational database access
system using semantically dynamic objects", Cambot, et al. and 5,555,403
"Relational database access system using semantically dynamic objects'"
Cambot, et al. in which the user may choose from a list of computed contexts.
In case of join ambiguity, the automatic generation of joins by these
inventions
is such that it generates all the elements of an SQL statement automatically,
which defines all the joins and the temporary tables needed to create a
correct statement. These inventions then compute a set of contexts (a
consistent set of joins) or propose a suitable set of contexts to the user. A
context would be given a name that is somewhat meaningful to the user.
Although this approach allows users to work with their own familiar business
CA 02418753 2003-02-12
3
words and terminology and to access relational databases without being
required to possess any knowledge of the structure of the database or the
specific names of its physical elements, it does so at the cost of having to
present the user with alternatives from which to choose in order to resolve
join
ambiguities. Furthermore, making this choice in itself often requires a level
of
detailed knowledge that may not be directly relevant to the user's immediate
problem.
What is needed is a way to choose between ambiguous joins that more
completely transfers the burden of making this choice from the user to the
specialist who creates the application.
BRIEF SUMMARY OF THE INVENTION
The present invention provides a form of join disambiguation that is rule-
driven. Since the specific parameters for the rules are provided by the
modeller and encapsulated as a subject area, and because the subject area is
chosen by the report author, the user is relieved of understanding the details
of how the join disambiguation is being done. A subject area is defined by
that
collection of related tables, which together with their relationships,
comprise a
useful source of information suitable for querying by the user. In general, a
subject area comprises one or more tables, known as query subjects, each
comprising one or more columns, known as query items.
In one aspect the invention provides a method for accessing values in a
database and creating a report comprising the steps of accepting from a user
an indication of the elements required in a report, creating a set of one or
more database queries required to produce the report disambiguating each
database query in the set automatically by creating a model of the necessary
query subjects, with their related query items and relationships thereby
defining a set of transformation rules for the database that permits automatic
disambiguation applying the set of disambiguated database queries to the
database using the transformation rules, and creating the report based on the
results of the set of database queries.
CA 02418753 2003-02-12
4
in a further aspect the invention provides a system for accessing values in a
database and creating a report comprising means for accepting from a user
an indication of the elements required in a report, means for creating a set
of
one or more database queries required to produce the report, means for
disambiguating each database query in the set automatically by creating a
model of the necessary query subjects, with their related query items and
relationships, and defining a set of transformation rules for the database
thereby permitting automatic disambiguation, means for applying the set of
disambiguated database queries to the database using the transformation
rules; and means for creating the report based on the results of the set of
database queries.
Other aspects, features, and advantages of the present invention will become
apparent from the following detailed description when taken in conjunction
with the accompanying drawings.
BRIEF DESCRIPTION OF DRAWLNGS
Embodiments of the invention will be described with reference to the following
figures:
Figure 1 shows a typical situation where there is potential for ambiguity in
which an embodiment of the present invention may be practised.
Figure 2 represents a database consisting of query subjects and relationships,
including an intermediate query subject.
Figure 3 is used in describing the concept of folders that contain the
relationships between objects.
Figure 4 represents a typical relationship containment rule.
Figure 5 illustrates unambiguous relationship alternatives using copies of
data
and copies of relationships.
CA 02418753 2003-02-12
.' 5
Figure 6 shows unambiguous relationship alternatives using references to
data and references to relationships.
Figure 7 is a flowchart illustrating operation of the invention.
DETAILED DESCRIPTION OF THE INVENTION
We now describe preferred embodiments of the present invention. All such
embodiments may conveniently be implemented on any general purpose
computing platform, including one incorporated in a clientlserver or networked
environment.
For purposes of these descriptions, we assume that the data being queried is
0 in tabular form, as in conventional relational databases. Generally such
"tables" may be thought of as consisting of "rows" and "columns". Two or
more such tables can be joined by criteria on the row values of selected
columns, to produce what is effectively a wider table. Note that the present
invention is not limited to relational databases, but may be applied to any
system that embraces these concepts.
In this discussion, a query subject QS represents a "table", a query item QI
represents a "column", and a relationship R represents a "join". A
relationship
path is a set of one or more relationships that connects two query subjects,
possibly via one or more intermediate query subjects. This is clearly
illustrated
in Figure 2 that shows a model with an intermediate table. This case, is
analogous to the simple schema shown in Figure 1 and described in the
background section, but with the addition of the third query subject and
related relationships. The same numbers are used in the figures to denote the
same (or equivalent) entities. As before, there are two tables or query
subjects Table A 100, and Table B 110, each comprising two fields, or query
items, A1 101, A2 102 and B1 111, B1 112, respectively. Again, the tables are
associated, but in this case only one relationship is direct, Join 2 121. The
other relationship is achieved through a further third query subject Table C
230, comprising a single field or query item C1 231. Query subject Table A
CA 02418753 2003-02-12
6
100 and query subject Table C 230 are associated or related through Join 3
221 between A1 101 in Table A 100 and C1 231 in Table C 230. Similarly,
query subjects Table B 110 and Table C 230 are associated or related
through Join 4 222 between C1 231 in query subject Table C 230 and B1 111
in query subject Table B 110.
In the present embodiment, the model allows the query subjects (or tables)
and the relationships between them to be organized into subject area
groupings called folders. At query time, the transformation or disambiguation
rule is to "choose the relationship that is contained in the folder thafis the
root
of the smallest common sub-tree that contains the tv~o query subjects being
joined". This is illustrated in Figure 3 which shows in outline the same three
query subjects Table A 100, Table B 110, Table C 230 as in Figure 2, and
their relationships defined by Join 2 121, Join 3 221, and Join 4 222. In this
case, the additional information given is that the Tables A and Table B are
part of the same Folder N 340. This extra grouping allows the resolving of
many ambiguities transparently and without intervention by the user.
It is crucial that the inverse of this transformation or disambiguation rule
is
also enforced: namely that "every relationship is contained by the folder that
is
the root of the smallest common sub-free that confains the two query subjects
that are its end points". Note that this enforcement must take account of any
changes in folder organisation.
We refer next to Figure 4, which again shows in outline the same three query
subjects Table A 100, Table B 110, Table C 230 as described in relation to
Figure 2, and their relationships Join 2 121, Join 3 221, Join 4 222. The
Folder N 340, as described earlier is shown, and in addition two other folders
are defined: Folder M 442 which encompasses the three query subjects Table
A 100, Table B 110, Table C 230 and their relationships Join 2 120, Join 3
221, Join 4 223; and Folder L 444 which encompasses only query subject
Table B 110. The assignment of these folders allows the relationship
containment rule to be defined such that the relationship Join 2 121, defined
CA 02418753 2003-02-12
within Folder N 340 is used, not the relationships defined within the
additional
Folders M 442 or L 444.
To implement the invention as described thus far requires the creation of
copies of some of the required query subjects and some of the relationships
for each subject area. This is clearly shown in Figure 5 where 'copy of QSA'
500, 'copy of QSB' 510, and 'copy of QSC' 530 of all the query subjects QSA
100, QSB 110, and QSC 230 are required to be created. As before, there are
relationships between the query subjects, or in some cases between query
subjects and copies of query subjects: R2 121 between QSA 100 and QSB
110, R3 512 between 'copy of QSA' 500 and QSC 230, and R4 514 between
QSC 230 and 'copy of QSB' 510. In addition a 'copy of the (join) relationship
R4' 522 is required between 'copy of QSC' 530 and QSB 110.
This embodiment, while solving the join ambiguity problem, creates a
maintenance problem in the model, because changes to any of the model
elements must be propagated to each of their copies. In general this must be
done by manual means
In a further preferred embodiment of the invention, to overcome this
maintenance problem, copies of the data and relationships used in
formulating and defining the relationships are replaced by proxy references;
often called shortcuts. To fully attain this goal shortcuts are used not just
for
query subjects, but also for the relationships themselves. Figure 6 shows an
embodiment of the invention wherein these shortcuts are used in place of
copies of the data.
A direct comparison of Figure 6 with Figure 5 shows that where previously
copies of QSA, QSB and QSC and R3 were required to be created, this
embodiment requires the creation of shortcuts or proxy references. Therefore,
the relationships are defined in terms of a 'reference to QSA' 600, a
'reference
to QSB' 610, and a 'reference to QSC' 630 as well as to the query subjects
QSA 100, QSB 110, and QSC 230. As before, there are relationships
between the query subjects, or in some cases between query subjects and
CA 02418753 2003-02-12
references to query subjects: R2 121 between QSA 100 and QSB 110, R3
612 between 'reference to GtSA' 600 and QSC 230, and R4 614 between
QSC 230 and 'reference to QSB' 610. In addition a 'reference to relationship
R3' 622 is required between the 'reference to QSC' 630 and QSB 110. During
access, the same actions are performed as before, but this time using the
shortcuts or proxy references where appropriate.
The utility of these embodiments is most easily seen in the following
simplified
description of the custom report operation, as perceived by the user.
initially, the user selects from a variety of previously defined reports or
report
templates 705 to be run against tables that are to be joined in the process of
producing the report. These report templates are to some extent incomplete,
being intended to be somewhat customised by the user, so that not all of the
possible elements in the tables or report templates are included in the
resulting reports, but rather only those of interest to that user and any
related
audience. Once the user has performed the necessary selection of elements
710, a reporting tool produces a high level query specifying what model
objects are to be included in the report. This high-level query specification
is
passed to the Query Engine (QE) that then examines it, and the related
metadata in the model, and generates the (SQL) query 715 that goes to the
underlying database server(s). In addition to constructing the queries
required
to produce the report, the QElreporting tool (or bath) examines the required
relationships, thereby determining any potential ambiguities 720, in the join
paths, and performs any disambiguation 725 repeating the query generation
and examination for ambiguity as required. Each disambiguation follows the
rules, as previously described with reference to Figure 3, in that the query
engine ensures that the selected relationship is that which is contained in
the
folder that is the root of the smallest common sub-free that contains the two
query subjects being joined. Once a fully unambiguous set of queries have
been assembled, the report is constructed as normal by applying the queries
to the database 730, formatting the response, and finally presenting the
report
CA 02418753 2003-02-12
9
735 to,the user, for example on the screen of a personal computer (client) or
in printed form.
The invention may be conveniently embodied in an executable or loadable
software package, which may be transmitted over data links, or stored on a
computer readable medium, for ease of installation on appropriately
configured computers.
While the invention is described in conjunction with these preferred
embodiments, it will be understood that they are not intended to limit the
invention to those embodiments. On the contrary, the invention is intended to
cover alternatives, modifications and equivalents, which may be included
within the spirit and scope of the invention as defined by the appended
claims.
