Method and structure for template-based data retrieval for hypergraph entity-relation information structures

• US 20040133536A1
• Filed: 12/23/2002
• Published: 07/08/2004
• Est. Priority Date: 12/23/2002
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Uceda-Sosa, Rosario
• Application Number:
  US10/326,375
• Publication Number:
  US 20040133536A1
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/288 Entity relationship models

Abstract

A method (and structure) to retrieve data from information structures based on an entity/relation paradigm and characterized as being a self-similar hypergraph, includes creating a template that matches a self-similar hypergraph format of the information structure. The template contains at least one query unit.

Claims

1. A method to retrieve data from information structures, said method comprising:

generating a template containing at least one query unit,

wherein both of an information structure being queried by said template and said template are based on an entity/relation paradigm and are characterized as having a self-similar hypergraph (“

fractal”

) format, said self-similar hypergraph format representing a graph in said information structure which comprises one or more nodes and each said node selectively comprises an entire subgraph.

2. The method of claim 1, further comprising:

comparing said template against an information unit in said information structure to determine whether said information unit matches said at least one query unit.

3. The method of claim 2, further comprising:

returning data of said information structure matching said at least one query unit.

4. The method of claim 3, wherein said information structure comprises a plurality of information units, each said information unit comprises at least one node and at least one relation in a hypergraph structure, said template comprises a subgraph, and each node in said template subgraph comprises at least one predefined target, said at least one predefined target comprising at least one of a target node and a target relation, and said template subgraph further comprises an anchor node used to start an evaluation of said comparing.

5. The method of claim 4, wherein said comparing comprises, for each said information unit in said information structure:

initially comparing said template anchor node with a node in said information unit; and

if said template anchor node matches a node in said information unit, systematically comparing each element of said template subgraph against any of a corresponding element of said information unit.

6. The method of claim 5, wherein said returning data comprises:

returning all of said at least one predefined target extracted from each said information unit that matches said template subgraph.

7. A middleware module executing a template-based method to retrieve data from information structures, said middleware module comprising:

a template constructor for creating a template that matches a self-similar hypergraph format of said information structure, said template containing at least one query unit, wherein said information structure is based on an entity/relation paradigm and is characterized as having a self-similar hypergraph (“

fractal”

) format, said self-similar hypergraph format representing a graph in said information structure which comprises one or more nodes and each said node selectively comprises an entire subgraph.

8. The middleware module of claim 7, further comprising:

a comparator to compare said template against an information unit in said information structure to determine whether said information unit matches said at least one query unit; and

a data transfer unit to return data in said information structure matching said at least one query unit.

9. The middleware module of claim 8, wherein said information structure comprises a plurality of said information units, each said information unit comprises at least one node and at least one relation in a hypergraph structure, said template comprises a subgraph, and each node in said template subgraph comprises at least one predefined target, said at least one predefined target comprising at least one of a target node and a target relation, and said template subgraph further comprises an anchor node used to start an evaluation.

10. The middleware module of claim 9, wherein said comparator comprises:

a population module including an initial comparison module that initially compares said template anchor node with a node in one of said information unit under evaluation.

11. The middleware module of claim 10, said population module further comprising a subsequent comparison module that, if said template anchor node matches a node in said information unit, systematically compares each element of said template subgraph against any of a corresponding element of said information unit under evaluation.

12. The middleware module of claim 8, wherein said data transfer unit includes:

an extraction module that returns said at least one predefined target extracted from each said information unit that matches said template subgraph.

13. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a template-based method to retrieve data from information structures, said method comprising:

creating a template containing at least one query unit, wherein an information structure being queried by said template and said template are each based on an entity/relation paradigm and are each characterized as having a self-similar hypergraph (“

fractal”

) format, said self-similar hypergraph format representing a graph in said information structure or template which comprises one or more nodes and each said node selectively comprises an entire subgraph.

14. The signal-bearing medium of claim 13, said method further comprising:

comparing said template against an information unit in said information structure to determine whether said information unit matches said at least one query unit.

15. The signal-bearing medium of claim 14, said method farther comprising:

returning data in said information structure matching said at least one query unit.

16. An apparatus executing a template-based method to retrieve data from information structures, said apparatus comprising:

a template constructor for creating a template that matches a self-similar hypergraph format of an information structure, said template containing at least one query unit, wherein said information structure is based on an entity/relation paradigm and is characterized as having a self-similar hypergraph (“

fractal”

) format, said self-similar hypergraph format representing a graph in said information structure which comprises one or more nodes and each said node selectively comprises an entire subgraph.

17. The apparatus of claim 16, further comprising:

a comparator to compare said template against an information unit in said information structure to determine whether said information unit matches said at least one query unit; and

a data transfer unit to return data in said information unit matching said at least one query unit.

18. The apparatus of claim 17, wherein said information structure comprises a plurality of said information units, each said information unit comprises at least one node and at least one relation in a hypergraph structure, said template comprises a subgraph, and each node in said template subgraph comprises at least one predefined target, said at least one predefined target comprising at least one of a target node and a target relation, and said template subgraph further comprises an anchor node used to start an evaluation.

19. A network executing a template-based method to retrieve data from information structures, said network comprising:

a first computer having a middleware module executing a template-based method to retrieve data from information structures based on an entity/relation paradigm and characterized as being a self-similar hypergraph, said middleware module comprising;

a template constructor for creating a template that matches a self-similar hypergraph format of said information structure, said template containing at least one query unit, wherein said information structure is based on an entity/relation paradigm and is characterized as having a self-similar hypergraph (“

fractal”

) format, said self-similar hypergraph format representing a graph in said information structure which comprises one or more nodes and each said node selectively comprises an entire subgraph.

20. The network of claim 19, wherein said middleware module in said first computer further comprises:

a comparator to compare said template against an information unit in said information structure to determine whether said information unit matches said at least one query unit; and

a data transfer unit to return data in said information structure matching said at least one query unit.

21. The network of claim 19, further comprising:

a second computer having stored therein an information structure corresponding to a self-similar hypergraph format matching said template.

22. The network of claim 21, wherein said second computer includes a middleware module comprising:

a comparator to compare a template received from said first computer against an information unit in said information structure to determine whether said information unit matches said at least one query unit; and

a data transfer unit to return data in said information unit matching said at least one query unit, thereby allowing a comparator and a data transfer unit in said middleware module of said second computer to process a query in said received template.

23. A node in a computer system, said node comprising:

a receiver for receiving data retrieved from a query of an information structure, said retrieved data being data that matches a template query, said information structure being based on an entity/relation paradigm and characterized as having a self-similar hypergraph (“

fractal”

) format, said self-similar hypergraph format representing a graph in said information structure which comprises one or more data-unit-nodes, wherein each said data-unit-node selectively comprises an entire subgraph, said matched data resulting from a comparison of a template that matches a self-similar hypergraph format of said information structure, and said template containing at least one query unit.

24. A node in a computer system, said node comprising:

a generator for generating a query template for an information structure having a self-similar hypergraph (“

fractal”

) format, said template containing at least one query unit, said self-similar hypergraph format representing a graph in said information structure which comprises one or more data-unit-nodes, wherein each said data-unit-node selectively comprises an entire subgraph.