Method and apparatus for searching a hierarchical database and an unstructured database with a single search query

• US 8,046,353 B2
• Filed: 11/02/2007
• Issued: 10/25/2011
• Est. Priority Date: 11/02/2007
• Status: Active Grant

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Citrix Online LLC (Cloud Software Group)
• Inventors: Waters, Christopher
• Primary Examiner(s): Perveen; Rehana
• Assistant Examiner(s): HERSHLEY, MARK E
• Application Number:
  US11/982,699
• Publication Number:
  US 20090119257A1
• Time in Patent Office: 1,453 Days
• Field of Search: 707/4, 707/713, 707/715, 707/718, 707/721
• US Class Current: 707/715
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Techniques for searching a hierarchical database and an unstructured database with a single search query are described herein. In one embodiment, a single search query is received that has syntax identifying an unstructured search string within a structured search query to automatically cause a search of the inverted index and use of the result to automatically search the hierarchical database. The unstructured search string is extracted from the single search query and an inverted index is searched according to the unstructured search string, wherein the inverted index includes virtual documents created from data stored in the hierarchical database, wherein each virtual document includes a unique identifier from the hierarchical database used to designate the data in the hierarchical database from which that virtual document was created, wherein a result of the inverted index search includes the unique identifiers of the virtual documents that meet the search. For each of the unique identifiers in the result, a separate search query is generated from the single search query by replacing the unstructured search string in the structured search query with that unique identifier and the hierarchical database is searched according to the separate search query. Other methods and apparatuses are also described.

Claims

1. A method of searching a hierarchical database and an inverted index, comprising:

receiving a single search query that has syntax identifying an unstructured search string within a structured search query to automatically cause a search of the inverted index and use of the result to automatically search the hierarchical database;

extracting the unstructured search string from the single search query;

searching the inverted index according to the unstructured search string, wherein the inverted index includes virtual documents created from data stored in the hierarchical database, wherein each virtual document includes a unique identifier from the hierarchical database used to designate the data in the hierarchical database from which that virtual document was created, wherein a result of the inverted index search includes the unique identifiers of the virtual documents that meet the search; and

generating, for each of the unique identifiers in the result, a separate search query from the single search query by replacing the unstructured search string in the structured search query with that unique identifier,

searching the hierarchical database according to the separate search query;

wherein the hierarchical database includes one or more sub-trees branching from a tree root node, wherein each sub-tree includes one or more nodes starting at a sub-tree root node, and wherein each node has a unique identifier, and wherein creating the virtual documents includes selectively generating the virtual documents from the one or more sub-trees, wherein each of the virtual documents corresponds to one of the one or more sub-trees and includes all nodes of that sub-tree; and

wherein the syntax for the single search query includes a SELECT clause and a FROM clause, wherein the SELECT clause includes syntax to identify a path in the hierarchical database starting at the tree root node, and wherein the FROM clause includes the unstructured search string.

2. The method of claim 1, wherein at least one unique identifier in the result corresponds to a virtual document that is associated to a first type of data in the hierarchical database, wherein the first type of data belongs to a first data domain, and wherein at least one other unique identifier in the result corresponds to a different virtual document that is associated to a second type of data in the hierarchical database, wherein the second type of data belongs to a different second data domain.

3. The method of claim 1, wherein the hierarchical database has a tree structure and the unique identifiers in the result correspond to identifiers of nodes of the tree.

4. The method of claim 1, wherein the hierarchical database includes collected information from across disparate information sources stored in a plurality of devices of a single LAN, wherein the collected information is organized by items of interest, and wherein the hierarchical database is not organized by documents located on the plurality of devices of the LAN.

5. The method of claim 1 wherein the single search query is formed in response to a selection of at least one item returned as a result from a previous unstructured search, wherein the structured search query includes the item selected, and the unstructured search string within the structured search query corresponds to the previous unstructured search string query.

6. The method of claim 1 wherein the hierarchical database having stored therein information regarding:

substantially all devices within a LAN,

a list of software installed on those devices, and

a list of users authorized to use those devices.

7. The method of claim 1 further comprising:

receiving data to be merged in the hierarchical database; and

merging the received data with the data stored in the hierarchical database upon receiving a single merge query that has syntax for inserting the received data into the hierarchical database and updating the data in the hierarchical database with the received data, wherein the received data is updated upon determining that the received data changes values of the data already stored in the hierarchical database.

8. The method of claim 1, wherein each node existing directly below the tree root node represents a private sub-tree, wherein values and node information in the private sub-tree are private to an organization.

9. The method of claim 1, wherein each of the unique identifiers corresponds to one of the one or more sub-tree root nodes, and wherein each virtual document includes path information starting at one of the one or more sub-tree root nodes and ending with a value.

10. The method of claim 9 wherein a result of each of the separate search queries is formatted in a hierarchical manner starting from the sub-tree root node corresponding to the unique identifier.

11. A search database system, comprising:

a hierarchical database to store a set of data in a hierarchical manner, wherein each of a plurality of points in the hierarchy has a unique identifier;

a hierarchical database engine coupled with the hierarchical database, the hierarchical database engine to search the set of data stored in the hierarchical database;

a document generator coupled with the hierarchical database engine, the document generator to create a different document from the data stored under each of the plurality of points in the hierarchical database;

an inverted index;

an inverted index engine coupled with the document generator, the inverted index engine to index each document and the associated unique identifiers in the inverted index, and search the inverted index;

a search server user interface, coupled with the hierarchical database engine and the inverted index engine, the search server user interface to receive a single search query that has syntax identifying an unstructured search string within a structured search query to automatically cause a search of the inverted index and use of the result to automatically search the hierarchical database, the search server user interface including;

a parser to extract the unstructured search string from the single search query and forward the extracted unstructured search string to the inverted index engine to cause a search of the inverted index;

a structured query generator to receive a result of the inverted index search that includes the one or more unique identifiers of the documents that meet the search, and for each of the unique identifiers in the result, to

generate a separate search query from the single search query by replacing the unstructured search string in the structured search query with that unique identifier, and

forward the separate search query to the hierarchical database engine to cause a search of the hierarchical database according to the separate search query;

wherein the hierarchical database includes one or more sub-trees branching from a tree root node, wherein each sub-tree includes one or more nodes starting at a sub-tree root node and includes at least one value, and wherein the unique identifier associated with each of the plurality of documents corresponds to the sub-tree root node;

wherein each node existing directly below the tree root node represents a private sub-tree, wherein values and node information in the private sub-tree are private to an organization; and

wherein the syntax for the single search query includes a SELECT clause and a FROM clause, wherein the SELECT clause includes syntax to identify a path in the hierarchical database starting at the tree root node, and wherein the FROM clause includes the unstructured search string.

12. The search database system of claim 11, wherein the result of the inverted index search includes a plurality of unique identifiers, where at least one unique identifier in the result corresponds to a virtual document that is associated to a first type of data in the hierarchical database, wherein the first type of data belongs to a first data domain, and where at least one other unique identifier in the result corresponds to a different virtual document that is associated to a second type of data in the hierarchical database, wherein the second type of data belongs to a different second data domain.

13. The search database system of claim 11, wherein the hierarchical database has a tree structure and the unique identifiers in the result correspond to identifiers of nodes of the tree.

14. The search database system of claim 11, wherein the document generator creating the plurality of documents includes selectively generating documents from the one or more sub-trees, wherein each document includes path information starting at the root node of the sub-tree and ending at a value of the sub-tree, and wherein each document is associated with the unique identifier of the root node of the sub-tree.

15. The search database system of claim 11, wherein the data stored in the hierarchical database includes collected information from across disparate information sources stored in a plurality of devices of a single LAN, wherein the collected information is organized by items of interest, and wherein the hierarchical database is not organized by documents located on the plurality of devices of the LAN.

16. The search database system of claim 11, wherein the single search query is formed in response to a selection of at least one item returned as a result from a previous unstructured search, wherein the structured search query includes the item selected, and the unstructured search string within the structured search query corresponds to the previous unstructured search string query.

17. The search database system of claim 11 wherein the set of data stored in the hierarchical manner includes information regarding:

substantially all devices within a LAN,

a list of software installed on those devices, and

a list of users authorized to use those devices.

18. The search database system of claim 11, further comprising:

a data receiving module coupled with the hierarchical database engine, the data receiving module to receive data that is to be merged into the hierarchical database and forward the received data to the hierarchical database engine to allow the received data to be merged into the hierarchical database.

19. The search database system of claim 11, further comprising:

a hierarchical search results module to receive a result for each of the separate search queries and to format the results in a hierarchical manner starting from the sub-tree root node corresponding to the unique identifier.

20. The search database system of claim 18, wherein the data receiving module is to merge data upon receipt of a single merge query that has syntax configured to insert the received data into the hierarchical database and update the data in the hierarchical database with the received data, wherein the received data is updated upon determining that the received data changes values of the data stored in the hierarchical database.