End user query facility including a query connectivity driver

• US 5,749,079 A
• Filed: 01/26/1995
• Issued: 05/05/1998
• Est. Priority Date: 03/04/1992
• Status: Expired due to Fees

• Current Assignee: D2K, Inc.
• Original Assignee: Singapore Computer Systems Limited (Singapore Telecommunications Limited)
• Inventors: Yo, Christopher Leng-Hong, Cheng, Viktor Choong-Hung, Yong, Dennis, Lim, Liat
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): CORRIELUS, JEAN M
• Application Number:
  US08/378,744
• Time in Patent Office: 1,195 Days
• Field of Search: 395/600, 395/50, 395/54, 395/52, 395/63, 395/77, 395/51
• 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 707/99933 Query processing, i.e. searching

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 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 application, which supports end-user query, to obtain from a user a designation of the information to be extracted from said database;

a query facility connectivity driver for connecting said application to said query facility, and for connecting said query facility to said database through a database connectivity driver;

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.

2. An end-user query facility as in claim 1 wherein said inference engine comprises:

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

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.

3. An end-user query facility as in claim 2 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 said basic knowledge threads.

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

5. An end-user query facility as in claim 1 wherein said semantics extractor further comprises means for reading source code of application programs that access said database, extracting the semantics of said application programs and storing in said knowledge base said set of linkages.

11. An end-user query facility as in claims 1, 6 or 7 wherein both said application and said query facility connectivity driver have the same data access interface that conforms to a data access interface standard.

12. An end user query facility as in claims 1, 6 or 7 wherein both said query facility connectivity driver and said database connectivity driver have the same data access interface that conforms to a data access interface standard.

13. An end user query facility as in claims 11 or 12 wherein said data access interface standard is Microsoft Corporation'"'"'s Open Database Connectivity (ODBC) standard.

14. An end user query facility as in claim 11 or 12 wherein said data access interface standard is Apple Computer'"'"'s Data Access Language (DAL) standard.

15. An end user query facility as in claims 1 or 10 wherein said semantics extractor comprises means for deriving basic knowledge threads comprising a set of linkages of said database model and storing said knowledge threads in said knowledge base.

16. An end-user query facility as in claim 15 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 serially 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.

17. An end-user query facility as in claim 15 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.

20. An end user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said application comprises:

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

means for obtaining from a user a user supplied key word 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.

43. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 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.

44. An end-user query facility as in claim 43 wherein said keys comprise unique or repeating keys.

45. An end-user query facility as in claim 43 wherein said keys comprise primary or foreign keys.

46. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 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.

47. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 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 file(s).

48. An end-user query facility as in claims 46 or 47 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.

49. An end-user query facility as in claim 43, 46 or 47 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.

50. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 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.

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

item securing 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.

52. An end user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said program comprises a source code program.

53. An end user query facility as in claim 52 which further comprises a compiler for compiling said source code program.

54. An end user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said application 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.

58. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said knowledge base comprises pre-created knowledge base.

59. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said knowledge base comprises a run-time created knowledge base.

60. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said knowledge base comprises a persistent knowledge base.

61. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said knowledge base comprises a transient knowledge base.

62. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said knowledge base is implemented in data dictionary of said database.

63. An end-user query facility as in claims 1, 6, 7, 10, 18 or 19 wherein said knowledge base is implemented in system catalog of said database.

6. 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 application, which supports end-user query, to obtain from an user choices based on said classes as a designation of the information to be extracted from said database;

a query facility connectivity driver for connecting said application to said query facility, and for connecting said query facility to said database through a database connectivity driver;

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.

7. 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 application, which supports end-user query, to obtain from a user a designation of the information to be extracted from said database;

a query facility connectivity driver for connecting said application to said query facility, and for connecting said query facility to said database through a database connectivity driver;

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 linkage(s) 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.

8. An end-user query facility as in claim 7 wherein a said simple query result 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.

9. An end-user query facility as in claim 7 wherein a said simple query result 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.

10. 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;

a keyword library which stores a set of keywords of said database model;

an application, which supports end-user query, to obtain from a user a designation of the information to be extracted from said database using said keyword library;

a first connectivity driver for connecting said application to said keyword library;

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 first e-mail agent for said first connectivity driver 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;

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;

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

55. An end-user query facility as in claims 6, 7, 10, 18 or 19 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.

56. An end-user query facility as in claim 55 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.

57. An end-user query facility as in claims 56 wherein said thread head is a first file on a said basic knowledge thread.

64. An end-user query facility as in claims 10, 18 or 19 which further comprises a second connectivity driver for connecting said program generator to said database through a database connectivity driver.

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

18. 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;

a keyword library which stores a set of keywords of said set of classes including the names of said classes and their attributes;

an application, which supports end-user query, to obtain from a user a designation of the information to be extracted from said database using said keyword library;

a first connectivity driver for connecting said application to said keyword library;

an inference engine which, based upon said designation of information to be extracted form 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 first e-mail agent for said first connectivity driver 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;

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; 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.

21. An end user query facility as in claims 6, 7, 18 or 19 wherein each said class comprises a data model of a subset of database files of said database model, the said data model comprising a tree.

22. An end user query facility as in claim 21 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.

23. An end-user query facility as in claim 22 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.

24. An end-user query facility as in claim 23 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.

25. An end-user query facility as in claim 23 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.

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

27. An end user query facility as in claim 26 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.

28. An end user query facility as in claim 27 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.

29. An end user query facility as in claim 27 herein 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.

30. An end user query facility as in claim 27 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.

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

32. An end user query facility as in claim 26 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.

33. An end user query facility as in claim 26 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.

34. An end user query facility as in claim 26 wherein said "has_-- subtype" binary relationship is one 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.

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

36. An end-user query facility as in claim 23 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.

37. An end-user query facility extractor as in claim 36 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.

38. An end-user query facility extractor as in claims 37 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.

39. An end-user query facility ads in claim 22 wherein said class further comprise 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.

40. An end-user query facility as in claim 39 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.

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

42. An end-user query facility as in claim 6, 7, 18 or 19 wherein said application 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.

66. An end-user query facility as in claims 18 or 19 which further comprises a second connectivity driver for connecting said program generator to said database through a database connectivity driver.

67. An end user query facility as in claim 66 wherein both said second connectivity driver and said database connectivity driver have the same data access interface that conforms to a data access interface standard.

68. An end user query facility as in claims 70 or 67 wherein said data access interface standard is Microsoft Corporation'"'"'s Open Database Connectivity (ODBC) standard.

69. An end user query facility as in claims 70 or 67 wherein said data access interface standard is Apple Computer Incorporated'"'"'s Data Access Language (DAL) standard.

70. An end-user query facility as in claims 18 or 19 wherein both said application and said first connectivity driver have the same data access interface that conforms to a data access interface standard.

19. 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;

a keyword library which stores a set of keywords of said set of classes including the names of said classes and their attributes;

an application, which supports end-user query, to obtain from a user a designation of the information to be extracted from said database using said keyword library;

a first connectivity driver for connecting said application to said keyword library;

an inference engine which, based upon said designation of information to be extracted form 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 first e-mail agent for said first connectivity driver 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;

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;

a knowledge thread analyzer receiving as its input said linkage(s) 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.

71. 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 application for interfacing with a user to obtain from said user choices based on said entity-relationship model as a designation of the 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 that accesses said linkages obtained by said inference engine and generates a program to extract said desired information from said database; and

a query facility connectivity driver that comprises;

a first connectivity interface coupled to said application that conforms to Microsoft open database connectivity (ODBC) standard to interface with said inference engine and said knowledge base; and

a second connectivity interface coupled to said inference engine and said knowledge base to interface with said existing database using Microsoft open database connectivity (ODBC) driver.

72. An end user query facility as in claim 71 wherein said binary relationships further comprises:

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.

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

74. An end-user query facility as in claim 71 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 said database files.

75. An end-user query facility as in claim 71 which further comprises 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.

76. An end-user query facility as in claim 71 which further comprises 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 one or more of said new items, one or more of said new keys, or one or more of said new files.

77. An end-user query facility as in claims 75 or 76 wherein said program generator comprises means to generate a 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.

78. An end-user query facility as in claim 71 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 existing database.

79. An end-user query facility as in claim 78 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.

80. An end user query facility as in claim 71 wherein said program comprises a source code program.

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

82. An end-user query facility as in claim 71 which further comprises a means for a user to modify relationship names in the said set of entity-relationship models.