Document database management system and document database retrieving method

• US 5,875,441 A
• Filed: 05/06/1997
• Issued: 02/23/1999
• Est. Priority Date: 05/07/1996
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Nakatsuyama, Hisashi
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US08/851,892
• Time in Patent Office: 658 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/10, 707/9, 707/5, 707/101, 707/102, 707/506, 707/6, 707/513, 707/514, 707/200, 707/104, 707/532, 707/501, 707/500, 707/900, 707/907, 707/100, 707/103, 707/90 2, 1/1, 395/200.36, 395/200.33, 395/683, 395/710, 395/500, 395/200.48
• US Class Current: 1/1
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

This invention provides a document database management system that reduces time to retrieve a structured document and improves precision of a result of the retrieving. Query input unit inputs a query including structural elements and a relationship between them. Document type retriever retrieves at least one document type that matches to the structural elements and the relationships between them included in the inputted query. Document type display displays the at least one retrieved document type on the screen of the display device. Document type input unit selects a document type from the at least one document type displayed on the screen. Document retriever retrieves a document satisfying the inputted query from prospective documents, each of which is created according to the document type inputted by the document type input unit.

Claims

1. A document database management system comprising:

a document type storage for storing a plurality of document types, each of which defines structural elements of a structured document and which defines a relationship between the structural elements;

a document storage for storing a first number of documents, each of which is created according to one of the plurality of document types stored in the document type storage;

a query input unit for inputting a query that includes the structural elements and the relationship between the structural elements;

a document type retriever for retrieving at least one document type from the plurality of document types in the document type storage, at least part of the structural elements and the relationship therebetween defined by the document type matching the structural elements and the relationship between the structural elements included in the inputted query, wherein the retrieved at least one document type identifies a subset of a second number of prospective documents from the plurality of documents stored in the document storage, the second number of prospective documents being less than the first number of documents; and

a document retriever for retrieving a document satisfying the inputted query from the subset of prospective documents, each of the prospective documents being created according to the at least one document type retrieved by the document type retriever.

2. The document database management system as set forth in claim 1, further comprising:

a document type designator for designating at least one document type from the at least one document type retrieved by the document type retriever, wherein

each of the prospective documents is created according to the at least one document type designated by the document type designator.

3. The document database management system as set forth in claim 2, wherein the document type designator includes:

a document type display for displaying the at least one document type retrieved by the document type retriever; and

a document type input unit for selecting at least one document type from the at least one document type displayed on the document type display.

4. The document database management system of claim 1, wherein

each of the plurality of document types defines a super-subordinate relationship between structural elements, and

the query includes a super-subordinate relationship between structural elements,

the system further comprising:

correspondence storage for storing a corresponding relationship for each of the document types stored in the document type storage, the corresponding relationship associates each of the structural elements in the document type with a structural element that descends from each of the structural elements, wherein

the document type retriever retrieves at least one document type from the document storage, at least part of the structural elements and the super-subordinate relationship therebetween defined by the document type matching the structural elements and the super-subordinate relationship therebetween included in the query, with reference to the corresponding relationship stored in the correspondence storage.

5. The document database management system of claim 4, wherein

the document type retriever checks whether each of the structural elements in the inputted query is associated with a structural element that descends from each of the structural elements, by the corresponding relationships for a document type in the corresponding storage, and

if every structural element in the query is associated with a structural element that descends therefrom by the corresponding relationship for the document type, the document type retriever determines that at least part of the structural elements and the super-subordinate relationship therebetween defined by the document type matches the structural elements and the super-subordinate relationship included in the query.

6. The document database management system of claim 4, further comprising:

document type register for registering a new document type into the document type storage; and

corresponding relationship creator for creating a new corresponding relationship that associates each structural element defined by the new document type with a structural element that descends from the structural element, and for registering the created corresponding relationship into the correspondence storage.

7. The document database management system of claim 6, wherein the new document type is registered into the document type storage as a directed graph including nodes that indicate element types and constructors, and wherein the corresponding relationship creator performs a correspondence table creation process to thereby create a correspondence table for the new document type, the correspondence table creation process comprising:

identifying a root node of the new document type;

collecting all element type nodes that can be reached from the root node;

selecting one node from one of the root node and the element type nodes;

obtaining a set of adjacent element type nodes that are adjacent to the selected node;

obtaining a set of reachable element type nodes that are reachable from the selected node;

constructing the correspondence table by establishing the selected node as a starting node, the set of adjacent element type nodes as adjacent nodes and the reachable element type nodes as reachable nodes.

8. The document database management system of claim 4, wherein the correspondence storage includes a plurality of correspondence tables corresponding to each of the plurality of document types, each correspondence table comprising:

a starting element that is an element in the document type;

at least one adjacent element that is a child element of the starting element; and

at least one reachable element that is an element that is a descendant of the starting element.

9. The document database management system of claim 8, wherein the document type retriever further comprises a comparing unit that performs a node comparing process on the inputted query and the plurality of document types, and wherein the document retriever retrieves the at least one document type based on the result of the node comparing process.

10. The document database management system of claim 9, wherein the inputted query includes an inputted node and at least one neighbor node, and wherein the node comparing process includes:

identifying the correspondence tables whose starting element corresponds to the inputted node;

determining the correspondence tables from the identified correspondence tables that include the at least one neighbor node as either an adjacent node or a reachable node; and

retrieving the document types of the determined correspondence tables.

11. The document database management system of claim 10, wherein the determining the correspondence tables further includes:

determining if the at least one neighbor node is an adjacent node in the identified correspondence tables when the neighbor node is a child node; and

determining if the at least one neighbor node is a reachable node in the identified correspondence tables when the neighbor node is a descendant node.

12. A method for retrieving a document from a document database that stores a first number of a plurality of structured documents, comprising the steps of:

inputting a query that includes structural elements of a structured document and a relationship therebetween;

retrieving at least one document type, which defines structural elements of a structured document and a relationship therebetween, at least part of the structural elements and the relationship therebetween defined by the one document type matching the structural elements and the relationship therebetween included in the inputted query, wherein the retrieved at least one document type identifies a subset of a second number of prospective documents from the plurality of structured documents stored in the document database, the second number of prospective documents being less than the first number of documents; and

retrieving a document satisfying the inputted query from the subset of prospective documents, each of the prospective documents being created according to the retrieved at least one document type.

13. The method for retrieving a document from a document database as set forth in claim 12, further comprising the steps of:

selecting a document type from the at least one retrieved document type;

retrieving a document satisfying the inputted query from the subset of prospective documents stored in the document database, each of the prospective documents being created according to the selected document type.

14. The method for retrieving a document from a document database as set forth in claim 12, wherein

the at least one document type defines a super-subordinate relationship between structural elements, and

the query includes a super-subordinate relationship between structural elements,

the step for retrieving at least one document type comprises the substeps of:

checking whether each of the structural elements in the inputted query is associated with a structural element that descends from each of the structural elements by a corresponding relationship for the document type, the corresponding relationship being prepared in advance for the at least one document type and associating each of the structural elements in the at least one document type with a structural element that descends therefrom; and

if every structural element in the query is associated with a structural element that descends therefrom by the corresponding relationship for the at least one document type, determining that at least part of the structural elements and the super-subordinate relationship therebetween defined by the document type matches the structural elements and the super-subordinate relationship included in the query.

15. The method of claim 14, wherein the at least one document type further comprises at least one correspondence table comprising:

a starting element;

at least one adjacent element that is a child element of the starting element; and

at least one reachable element that is an element that is a descendant of the starting element.

16. The method of claim 15, wherein the step of retrieving at least one document type further comprises:

performing a node comparing process on the query and the at least one document type, and wherein the document retriever retrieves the at least one document type based on the result of the node comparing process.

17. The method of claim 16, wherein the query includes an inputted node and at least one neighbor node, and wherein the node comparing process includes:

determining if the at least one correspondence table includes the inputted node as a starting element;

determining if the at least one correspondence table includes the at least one neighbor node as either an adjacent node or a reachable node; and

retrieving the document type when the correspondence table includes both the inputted node and the at least one neighbor node.

18. The method of claim 17, wherein the step of determining if the at least one correspondence table includes that at least one neighbor node further comprises:

determining if the at least one neighbor node is an adjacent node in the correspondence table when the neighbor node is a child node; and

determining if the at least one neighbor node is a reachable node in the correspondence table when the neighbor node is a descendant node.

19. The method of claim 12, further comprising:

displaying the retrieved at least one document type; and

selecting a document type from the displayed at least one document type.