# US 2012/0254245 A1 · Relational database joins for inexact matching

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254245 A1
- Document ID: US20120254245A1
- Status: Published application
- Kind: A1
- Application number: 13/077,918
- Filed: 2011-03-31
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: TIBCO Software Inc.
- Inventors: Fletcher Foti; Bruce Zuidema
- Web page: https://patentgrep.com/patent/US20120254245A1

## CPC

- G06F 16/2456: {Join operations}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 16/24554: {Unary operations; Data partitioning operations}
- G06F 16/24578: {using ranking}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and systems for performing a query over joined tables in the context of inexact matching provide efficient search engine functionality. The systems and methods are used to perform an efficient query on a parent table and joined child tables. Search grams are determined based on the query and parent records and child records are scanned for the search grams. Gram scores are computed based on a degree of matching between the parent and child records and the search grams.

## Claims

### Claim 1

A method for performing an efficient query on a parent table and one or more joined child tables, the method comprising:
determining one or more search grams based on the query;
identifying a parent table having one or more parent table partitions including one or more respective parent records grouped therein;
identifying one or more child table partitions from one or more joined child tables, the one or more child table partitions including one or more respective child records grouped therein, wherein the identified one or more child table partitions are associated with a first of the one or more parent table partitions, and wherein the child records grouped within the identified one or more child table partitions are associated with the one or more parent records of the associated first of the one or more parent table partitions;
scanning parent records in the first of the parent table partitions for the one or more search grams;
scanning child records in the identified one or more child table partitions associated with the first of the parent table partitions for the one or more search grams;
computing parent gram scores for scanned parent records based on a degree of matching with the one or more search grams;
computing child gram scores for scanned child records based on a degree of matching with the one or more search grams;
computing aggregate scores for each parent record and its associated child records based on parent and child gram scores; and
repeating the identifying one or more child tables, scanning parent and child records, and computing parent and child gram scores and aggregate scores for each of the parent table partitions.

### Claim 2 (depends on 1)

The method of claim 1, further comprising inserting a new child record into any of the identified one or more child table partitions associated with an identified parent table partition having a parent record associated with the new child record.

### Claim 3 (depends on 2)

The method of claim 2, wherein inserting the new child record further comprises inserting the new child record into any available row in the identified one or more child table partitions associated with the identified parent table partition.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
generating a mapping structure having parent and child table partition association information and parent and child records association information; and
referencing the mapping structure to determine associations between parent and child table partitions and between parent and child records.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
adding parent records and child records based on aggregate scores to an output heap.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
receiving the query from a user.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
providing query results to the user based on the aggregate scores.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
outputting the aggregate scores into a parent table partition-sized output array.

### Claim 9 (depends on 1)

The method of claim 1, wherein the parent table is joined with multiple child tables.

### Claim 10 (depends on 1)

The method of claim 1, wherein the parent table is joined with a chain of child tables.

### Claim 11 (depends on 1)

The method of claim 1, wherein child records are associated with parent records via a foreign key field.

### Claim 12 (depends on 1)

The method of claim 1, wherein child records are associated with parent records via common unique values.

### Claim 13

A system for performing an efficient query on a parent table and one or more joined child tables, the system comprising:
a processor;
a memory element; and
a communications device, wherein the processor and memory element are in communication via the communications device, and wherein the processor is operable for:
determining one or more search grams based on the query;
identifying a parent table having one or more parent table partitions including one or more respective parent records grouped therein;
identifying one or more child table partitions from one or more joined child tables, the one or more child table partitions including one or more respective child records grouped therein, wherein the identified one or more child table partitions are associated with a first of the one or more parent table partitions, and wherein the child records grouped within the identified one or more child table partitions are associated with the one or more parent records of the associated first of the one or more parent table partitions;
scanning parent records in the first of the parent table partitions for the one or more search grams;
scanning child records in the identified one or more child table partitions associated with the first of the parent table partitions for the one or more search grams;
computing parent gram scores for scanned parent records based on a degree of matching with the one or more search grams;
computing child gram scores for scanned child records based on a degree of matching with the one or more search grams;
computing aggregate scores for each parent record and its associated child records based on parent and child gram scores; and
repeating the identifying one or more child tables, scanning parent and child records, and computing parent and child gram scores and aggregate scores for each of the parent table partitions.

### Claim 14 (depends on 13)

The system of claim 13, wherein the processor is further operable to generate a mapping structure having parent and child table partition association information and parent and child records association information, and wherein the mapping structure is stored in the memory element.

### Claim 15 (depends on 14)

The system of claim 14, wherein the processor is further operable to referencing the mapping structure stored in the memory element to determine associations between parent and child table partitions and between parent and child records.

### Claim 16 (depends on 13)

The system of claim 13, wherein the processor is further operable to add parent records and child records based on aggregate scores to an output heap.

### Claim 17 (depends on 13)

The system of claim 13, further comprising an input element for receiving the query from a user.

### Claim 18 (depends on 13)

The system of claim 13, further comprising a display element for displaying search results to a user.

### Claim 20

Determining one or more search grams based on the query;
identifying a parent table having one or more parent table partitions including one or more respective parent records grouped therein;
identifying one or more child table partitions from one or more joined child tables, the one or more child table partitions including one or more respective child records grouped therein, wherein the identified one or more child table partitions are associated with a first of the one or more parent table partitions, and wherein the child records grouped within the identified one or more child table partitions are associated with the one or more parent records of the associated first of the one or more parent table partitions;
scanning parent records in the first of the parent table partitions for the one or more search grams;
scanning child records in the identified one or more child table partitions associated with the first of the parent table partitions for the one or more search grams;
computing parent gram scores for scanned parent records based on a degree of matching with the one or more search grams;
computing child gram scores for scanned child records based on a degree of matching with the one or more search grams;
computing aggregate scores for each parent record and its associated child records based on parent and child gram scores; and
repeating the identifying one or more child tables, scanning parent and child records, and computing parent and child gram scores and aggregate scores for each of the parent table partitions;
generating a mapping structure having parent and child table partition association information and parent and child records association information; and
referencing the mapping structure to determine associations between parent and child table partitions and between parent and child records.
