Apparatus and method for end user queries

• US 5,701,466 A
• Filed: 11/29/1994
• Issued: 12/23/1997
• Est. Priority Date: 03/04/1992
• Status: Expired due to Fees

• Current Assignee: Century Oasis Limited
• Original Assignee: Singapore Computer Systems Limited (Singapore Telecommunications Limited)
• Inventors: Cheng, Viktor Choong-Hung, Tay, Siew Choon, Yong, Dennis, Lim, Liat
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/346,507
• Time in Patent Office: 1,120 Days
• Field of Search: 395/50, 395/54, 395/52, 395/63, 395/77, 395/51, 395/600, 395/611-614
• US Class Current: 1/1
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 706/934 Information retrieval or Information management
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An end user query technology is taught which is capable of automatically understanding the database model and guiding the user to scout for the desired information, thereby increasing productivity and ease of information access. The user is freed from the need to understanding the database model, with the end user query facility of this invention quickly guiding the user to acquire the information. This is made possible by the end user query facility of this invention first recapturing the application semantics from the existing database model to provide a set of derived semantics. The derived semantics are then used by the end user query facility to intelligently guide the user to scout for the desired information in the database. In addition, the derived semantics can be easily updated by the end user query facility when the database model is changed.

Claims

1. An end user query facility for accessing a database having a plurality of database files formed using a database model, comprising:

a knowledge base which stores a set of classes and a set of linkages of the database model, each said class representing a hierarchical grouping of a subset of said database files, each said linkage representing a relation between two of said database files in which a first file has a key that references an equivalent key of a second file;

a class generator for reading said database model and generating said set of classes and said set of linkages of the database model and which stores in said knowledge base said set of classes and said set of linkages;

an information scout for interfacing with a user to obtain from the user choices based on said classes as a designation of the information to be extracted from said database;

an inference engine which, based upon said designation of information to be extracted from said database, identifies one or more of said database files which contain the desired information and searches said knowledge base to determine the linkage(s) connecting said one or more identified files; and

a program generator which accesses the linkages obtained by said inference engine and generates a program to extract said desired information from said database.

4. An end-user query facility as in claim 1 or 2 which further comprises:

a first e-mail agent for said information scout to interface with an e-mail system, the sail first e-mail agent being used to post said designation of information to be extracted from said database to the mailbox of said inference engine;

a second e-mail agent for the said inference engine to interface with said e-mail system, the said second e-mail agent being used to access said mailbox of said inference engine to obtain said designation of information to be extracted from said database.

5. An end-user query facility as in claims 1, 2, or 3 wherein said knowledge base comprises pre-created knowledge base.

6. An end user query facility as in claims 1, 2, or 3 wherein said program comprises a source code program.

7. An end user query facility as in claim 1 wherein said tree of said class has a root comprising a database file of kernel entity type and a plurality of branches each comprising a linkage of one or more database files from said subset of database files.

8. An end-user query facility as in claims 1, 2, or 3 which further comprises a model purifier for a user to alter said database model by defining new item(s), new key(s) or new file(s) using items of database files of said database model.

9. An end user query facility as in claims 1, 2, or 3 wherein said information scout comprises:

means for obtaining from a user a user supplied keyword indicative of the data desired to be extracted from said database;

means for determining all keywords in said database model having a predefined relationship with said user supplied keyword; and

means for causing a user to select one or more of said keywords having a predefined relationship, said one or more keywords thus selected serving as said designation of the information to be extracted from said database.

10. An end-user query facility as in claims 1, 2, or 3 wherein said inference engine comprises:

means for inferring new acquired knowledge threads and storing said new acquired knowledge threads in said knowledge base; and

means for determining an access path to said database using either said basic knowledge threads or said acquired knowledge threads as required to meet the user query.

11. An end-user query facility as in claim 1 or 2 wherein said information scout comprises an interface that displays all or selected said classes and that allows a user to formulate a query by picking the desired class attributes from said class as a designation of the information to be extracted from said database.

12. An end-user query facility as in claims 1, 2, or 3 which further comprises a program analyzer for analyzing and deriving new item(s), new key(s) or new file(s) from source code of applications that access said database model, and for altering said database model using said new item(s), new key(s) or new files.

13. An end-user query facility as in claims 1, 2, or 3 which further comprises a security model specifier to allow a user to input a security model which specifies restrictions on the information a user can obtain from said database.

14. An end-user query facility as in claims 1, 2, or 3 wherein said knowledge base comprises a run-time created knowledge base.

15. An end-user query facility as in claims 1, 2, or 3 wherein said knowledge base comprises a persistent knowledge base.

16. An end-user query facility as in claims 1, 2, or 3 wherein said knowledge base comprises a transient knowledge base.

17. An end-user query facility as in claims 1, 2, or 3 wherein said knowledge base is implemented in data dictionary of said database.

18. An end-user query facility as in claims 1, 2, or 3 wherein said knowledge base is implemented in system catalog of said database.

20. An end-user query facility as in claim 6 which further comprises a compiler to compile said source code program.

21. An end-user query facility as in claim 17 wherein said class further comprises a set of relationship names each of which specifies the nature of the relationship between two adjacent database files in each branch of said tree of said class.

22. An end-user query facility as in claim 7 wherein said class generator comprises:

a semantics extractor to derive a set of binary relationships and to derive the entity type of each database file of said database model;

a means to derive said set of classes using said set of binary relationships and said entity type of each database file of said database model.

23. An end-user query facility as in claims 8 or 12 wherein said program generator comprises means to generate source program that produce data from said new items of said new files and wherein said end-user query facility further comprises a compiler for compiling said source program.

24. An end-user query facility as in claims 1, 2, or 3 which further comprises a model purifier for a user to alter said database model by defining new keys for database files or by altering existing keys of database files of said database model.

25. An end-user query facility as in claim 10 wherein said acquired knowledge thread is derived through a combination in parallel of two or more of said basic knowledge threads such that one of the said basic knowledge threads has one or more of its consecutive files in common with the corresponding number of consecutive files starting from the thread head of another of said basic knowledge threads.

26. An end-user query facility as in claim 13 wherein said security model comprises:

item security which specifies a set of database files and items selected from said database which a user or class of users can access; and

value security which specifies a set of conditions to restrict said user or class of users to a certain range(s) of values of said database.

27. An end-user query facility as in claim 21 wherein said class generator comprises:

a semantics extractor to derive a set of binary relationships and to identify the entity type of each database file of said database model;

a means to derive said set of classes and their said set of relationship names using said set of binary relationships and said entity type of each database file of said database model.

28. An end-user query facility as in claim 22 wherein said entity type is selected from a set of entity types which comprise a kernel entity type, a subtype entity type, a characteristic entity type, an associative entity type or a pure lookup entity type.

29. An end-user query facility as in claim 22 wherein said semantics extractor further comprises means for deriving basic knowledge threads comprising a set of linkages of said database model and storing said basic knowledge threads in said knowledge base.

30. An end-user query facility as in claim 25 wherein said thread head is a first file on a said basic knowledge thread.

31. An end-user query facility as in claim 27 wherein said class generator further comprises a means for a user to modify said relationship names in the said set of classes.

32. An end-user query facility as in claim 28 wherein said binary relationship comprises a linkage between two files in said database model in which one file has a repeating or foreign key that references the unique or primary key of the other file.

33. An end-user query facility extractor as in claim 29 wherein each said basic knowledge thread comprises a set of two or more of said database files serially linked together such that one file is linked to the next file through an item that has the same domain as the item in the next file and that this same item is a unique or repeating key of the next file.

34. An end-user query facility extractor as in claim 29 wherein each said basic knowledge thread comprises a set of two or more of said database files serially linked together such that one file has a repeating or foreign key that references the unique or primary key of the next file.

35. An end user query facility as in claim 4 wherein said set of binary relationships comprises "has_-- children", "has_-- wards", "inverse_-- of_-- pure_-- lookup" or "has_-- subtype" binary relationships.

36. An end user query facility as in claim 35 wherein said set of binary relationships further comprises "inverse_-- of_-- "has_-- children", "inverse_-- of_-- has_-- wards", "pure_-- lookup" or "inverse_-- of_-- has_-- subtype" binary relationships.

37. An end user query facility as in claim 35 wherein said "has_-- subtype" binary relationship is one in which its source file has a one-to-one relationship with its target file and the target file is a subtype entity of the source file.

38. An end user query facility as in claim 35 wherein said "has_-- children" binary relationship is one in which the source file is not a pure lookup entity type and has a one-to-many relationship with the target file, and the target file does not have its own independent unique or primary key.

39. An end user query facility as in claim 35 wherein said "has_-- wards" binary relationship is one in which its source file is not a pure lookup entity type and has a one-to-many relationship with its target file, and its target file has its own independent unique key or primary key.

40. An end-user query facility as in claim 35 wherein said "inverse_-- of_-- pure_-- lookup" binary relationship is a binary relationship whose source file is a pure_-- lookup entity.

41. An end-user query facility as in claim 36 wherein said "pure_-- lookup" binary relationship is a binary relationship whose target file is a pure lookup entity.

42. An end user query facility as in claim 36 wherein said "inverse_-- of_-- has_-- children" binary relationship is one in which the target file is not a pure_-- lookup entity type and has a one-to-many relationship with the source file, and the source file does not have its own independent unique or primary key.

43. An end user query facility as in claim 36 wherein said "inverse_-- of_-- has_-- wards" binary relationship is one which the target file is not a pure lookup entity type and has a one-to-many relationship with the source file, and the source file has its own independent unique or primary key.

44. An end user query facility as in claim 36 wherein said "inverse_-- of_-- has_-- subtype" binary relationship is one in which its target file has a one-to-one relationship with its source file and the source file is a subtype entity of the target file.

47. An end-user query facility as in claim 24, 8, or 12 wherein said class generator further comprises a means to read said altered database model to regenerate said set of classes and said set of linkages.

48. An end-user query facility as in claim 24 or 8 wherein said keys comprise unique or repeating keys.

49. An end-user query facility as in claim 24 or 8 wherein said keys comprise primary or foreign keys.

2. An end user query facility for accessing a database having a plurality of database files formed using a database model, comprising:

a knowledge base which stores a set of classes and a set of linkages of the database model, each said class represents a hierarchical grouping of a subset of said database files, each said linkage representing a relation between two of said database files in which a first file has a key that references an equivalent key of a second file;

a class generator for reading said database model and generating said set of classes and said set of linkages of the database model and which stores in said knowledge base said set of classes and said set of linkages;

an information scout for interfacing with a user to obtain from the user choices based on said classes as a designation of the information to be extracted from said database;

an inference engine which, based upon said designation of information to be extracted from said database, identifies one or more of said database files which contain the desired information and searches said knowledge base to determine the linkage(s) connecting said one or more identified files;

a knowledge thread analyzer receiving as its input said linkages determined by said inference engine, and which breaks down said linkage(s) into simple linkage(s); and

a program generator which accesses said simple linkages obtained by said knowledge analyzer and generates programs, one for each said simple linkage, to extract said desired information from said database as a plurality of simple query results, one for each generated program.

45. An end-user query facility as in claim 2 wherein a said simple query results is one that does not contain repeated numeric values in any of the column(s) that corresponds to a non-key numeric item of said database.

46. An end-user query facility as in claim 2 wherein a said simple query results is one that does not contain two or more columns belonging to items whose database files are multi-valued dependencies of another database file in said database.

3. An end user query facility for accessing a database having a plurality of database files formed using a database model, comprising:

a knowledge base which stores a set of linkages of the database model, each said linkage representing a relation between two of said database files in which a first file has a key that references an equivalent key of a second file;

a semantics extractor for reading said database model and extracting the semantics of said database model, and which stores in said knowledge base said set of linkages,

an information scout for interfacing with a user to obtain from the user a designation of the information to be extracted from said database,

an inference engine which, based upon said designation of information to be extracted from said database, identifies one or more of said database files which contain the desired information and searches said knowledge base to determine the linkage(s) connecting said one or more identified files;

a program generator which accesses the linkages obtained by said inference engine and generates a program to extract said desired information from said database;

a first e-mail agent for said information scout to interface with an e-mail system, said first e-mail agent being used to post said designation of information to be extracted from said database to the mailbox of said inference engine; and

a second e-mail agent for the said inference engine to interface with said e-mail system, said second e-mail agent being used to access said mailbox of said inference engine to obtain said designation of information to be extracted from said database.

19. An end-user query facility as in claims 3 or 4 wherein said second e-mail agent further comprises means to post said desired information extracted from said database to the user mailbox.

50. An end user query facility for accessing a database having a plurality of database files formed using a database model, comprising:

an entity relationship (ER) model generator for reading said databases and deriving a plurality of entity-relationship models, said ER model generator comprising;

an entity type classifier for classifying each said database file into one of a plurality of entity types, said entity types including a "kernel" entity type, a "subtype" entity type, a "characteristic" entity type, an "associative" entity type, and a "pure lookup" entity type;

a binary relationship generator for generating a plurality of binary relationships between said database files, each said binary relationship associated with a linkage representing a relation between a first file having a key that references an equivalent key of a second file, said binary relationships including;

a "has_-- children" type that represents a first database file that is not classified as a "pure lookup" entity type and has a one-to-many relationship with a second database file, and said second database file does not have a unique key;

a "has_-- wards" type that represents a first database file that is not of a "pure lookup" entity type and has a one-to-many relationship with a second database file having a unique key;

a "has_-- subtype" type that represents a first database file having a one-to-one relationship with a second database file and said second database file is classified as a "subtype" entity type; and

an "inverse_-- of_-- pure_-- lookup" that represents a first database file is classified as a "pure_-- lookup" entity type;

a model constructor for constructing said entity-relationship models, each said entity-relationship model representing a tree having a root and a plurality of branches, said root associated with one of said database files classified as a "kernel" entity type, said model constructor utilizing said entity types and said binary relationships to associate one or more branches with each said entity-relationship model;

a knowledge base that stores said ER models;

an information scout for interfacing with a user to obtain from the user choices based on said entity-relationship models as a designation of information to be extracted from said database;

an inference engine that, based upon said designation of information to be extracted from said database, identifies one or more of said database files that contain the desired information and searches said knowledge base to determine one or more linkages connecting said identified files; and

a program generator that accesses said linkages obtained by said inference engine and generates a program to extract said desired information from said database.

53. An end-user query facility as in claim 50, 51 or 52 further comprising a modifier for use by a user to modify relationship names in said entity-relationship models.

54. An end user query facility as in claims 50, 51, or 52 wherein said information scout comprises:

input extractor for obtaining from a user a user-supplied keyword indicative of data desired to be extracted from said database;

keyword generator for determining all keywords in said database model having a predefined relationship with said user-supplied keyword; and

keyword selector for causing a user to select one or more of said keywords having a predefined relationship, said selected keywords serving as said designation of information to be extracted from said database.

55. An end user query facility as in claims 50, 51 or 52 wherein said program comprises a source code program.

56. An end-user query facility as in claims 50, 51, or 52 further comprising a model purifier for a user to alter said database model by defining new keys for said database files or by altering existing keys of said database files.

57. An end user query facility as in claim 50, 51 or 52 wherein said binary relationships further comprise:

an "inverse_-- of_-- has_-- children" type that represents a second database file that is not classified as a "pure_-- lookup" entity type and has a one-to-many relationship with a first database file having a unique key;

an "inverse_-- of_-- has_-- wards" type that represents a first database file that is not classified as a "pure lookup" entity type and has a one-to-many relationship with a second database file having a unique key;

a "pure_-- lookup" type wherein said second database file is classified as a "pure lookup" entity type; and

an "inverse_-- of_-- has_-- subtype" type wherein said second database file has a one-to-one relationship with said first database file, and said first database file is classified as a "subtype" entity type.

58. An end-user query facility as in claims 50, 51, or 52 further comprising a model purifier for a user to alter said database model by defining one or more new items, one or more new keys, or one or more new files using items of said database files.

59. An end-user query facility as in claims 50, 51, or 52 further comprising a program analyzer for analyzing and deriving one or more new items, one or more new keys, or one or more new files from source code of applications that access said database model, and for altering said database model using said new items, said new keys or said new files.

60. An end-user query facility as in claim 50 or 51 wherein said information scout comprises an interface that displays all or selected portions of said entity-relationship models and that allows a user to formulate a query by picking desired attributes from one of said entity-relationship model as a designation of information to be extracted from said database.

61. An end-user query facility as in claims 50, 51, or 52 further comprising a security model specifier to allow a user to input a security model that specifies restrictions on information a user can obtain from said database.

62. An end-user query facility as in claim 55 further comprising a compiler to compile said source code program.

63. An end-user query facility as in claims 56 or 58 wherein said keys comprise unique or repeating keys.

64. An end-user query facility as in claims 56 or 58 wherein said keys comprise primary or foreign keys.

65. An end-user query facility as in claims 58 or 59 wherein:

said program generator comprises a source program generator to generate a source program that produces data from said new items of said new files; and

said end-user query facility further comprises a compiler for compiling said source program.

66. An end-user query facility as in claim 61 wherein said security model comprises:

item security which specifies a set of database files and items selected from said database which a user or class of users can access; and

value security which specifies a set of conditions to restrict said user or class of users to one or more ranges of values of said database.

51. An end user query facility for accessing an existing database having a plurality of database files formed using a database model, comprising:

an entity relationship (ER) model generator for reading said databases and deriving a plurality of entity-relationship models, said ER model generator comprising;

an entity type classifier for classifying each said database file into one of a plurality of entity types, said entity types including a "kernel" entity type, a "subtype" entity type, a "characteristic" entity type, an "associative" entity type, and a "pure lookup" entity type;

a binary relationship generator for generating a plurality of binary relationships between said database files, each said binary relationship associated with a complex linkage representing a relation between a first file having a key that references an equivalent key of a second file, said binary relationships including;

a "has_-- children" type that represents a first database file that is not classified as a "pure lookup" entity type and has a one-to-many relationship with a second database file, and said second database file does not have a unique key;

a "has_-- wards" type that represents a first database file that is not of a "pure lookup" entity type and has a one-to-many relationship with a second database file having a unique key;

a "has_-- subtype" type that represents a first database file having a one-to-one relationship with a second database file and said second database file is classified as a "subtype" entity type; and

an "inverse_-- of_-- pure_-- lookup" that represents a first database file is classified as a "pure_-- lookup" entity type;

a model constructor for constructing said entity-relationship models, each said entity-relationship model representing a tree having a root and a plurality of branches, said root associated with one of said database files classified as a "kernel" entity type, said model constructor utilizing said entity types and binary relationships to associate one or more branches with each said entity-relationship model;

a knowledge base that stores said ER models;

an information scout for interfacing with a user to obtain from the user choices based on said entity-relationship models as a designation of information to be extracted from said database;

an inference engine that, based upon said designation of information to be extracted from said database, identifies one or more of said database files that contain the desired information and searches said knowledge base to determine one or more complex linkages connecting said identified files;

a knowledge thread analyzer receiving one or more of said complex linkages determined by said inference engine, and which breaks down each said complex linkage into one or more simple linkages, each said simple linkage including a subset of said complex linkages; and

a program generator which accesses said simple linkages obtained by said knowledge analyzer and generates programs, one for each said simple linkage, to extract said desired information from said database as a plurality of simple query results, one for each generated program.

67. An end-user query facility as in claim 51 wherein said simple query result does not include repeated numeric values in any column that corresponds to a non-key numeric item of said database.

68. An end-user query facility as in claim 51 wherein said simple query result does not include two or more columns belonging to items whose database files are multi-valued dependencies of another database file in said database.

52. An end user query facility for accessing an existing database having a plurality of database files formed using a database model, comprising:

an entity relationship (ER) model generator for reading said databases and deriving a plurality of entity-relationship models, said ER model generator comprising;

an entity type classifier for classifying each said database file into one of a plurality of entity types, said entity types including a "kernel" entity type, a "subtype" entity type, a "characteristic" entity type, an "associative" entity type, and a "pure lookup" entity type;

a binary relationship generator for generating a plurality of binary relationships between said database files, each said binary relationship associated with a linkage representing a relation between a first file having a key that references an equivalent key of a second file, said binary relationships including;

a "has_-- children" type that represents a first database file that is not classified as a "pure lookup" entity type and has a one-to-many relationship with a second database file, and said second database file does not have a unique key;

a "has_-- wards" type that represents a first database file that is not of a "pure lookup" entity type and has a one-to-many relationship with a second database file having a unique key;

a "has_-- subtype" type that represents a first database file having a one-to-one relationship with a second database file and said second database file is classified as a "subtype" entity type; and

an "inverse_-- of_-- pure_-- lookup" that represents a first database file is classified as a "pure_-- lookup" entity type;

a model constructor for constructing said entity-relationship models, each said entity-relationship model representing a tree having a root and a plurality of branches, said root associated with one of said database files classified as a "kernel" entity type, said model constructor utilizing said entity types and said binary relationships to associate one or more branches with each said entity-relationship model;

a knowledge base that stores said ER models;

an information scout for interfacing with a user to obtain from the user choices based on said entity-relationship models as a designation of information to be extracted from said database;

an inference engine that, based upon said designation of information to be extracted from said database, identifies one or more of said database files that contain the desired information and searches said knowledge base to determine one or more linkages connecting said identified files;

a program generator which accesses the linkages obtained by said inference engine and generates a program to extract said desired information from said database;

a first e-mail agent for said information scout to interface with an e-mail system, said first e-mail agent being used to post said designation of information to be extracted from said database to the mailbox of said inference engine; and

a second e-mail agent for the said inference engine to interface with said e-mail system, said second e-mail agent being used to access said mailbox of said inference engine to obtain said designation of information to be extracted from said existing database and to post said desired information extracted from said existing database to the user mailbox.