# US 8,751,526 B1 · Efficient range unions in SQL

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

- Number: US 8,751,526 B1
- Document ID: US8751526B1
- Status: Granted
- Kind: B1
- Application number: 13/598,053
- Filed: 2012-08-29
- Granted: 2014-06-10
- Earliest claimed: 2012-08-29
- Assignees: Bentley Systems, Incorporated
- Applicants: Keith A. Bentley; Raymond B. Bentley
- Inventors: Keith A. Bentley; Raymond B. Bentley
- Web page: https://patentgrep.com/patent/US8751526B1

## CPC

- G06F 16/244: {Grouping and aggregation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In one embodiment, a union of the bounding boxes is computed of entities in a relational database indexed by a spatial index, filtered according to some criteria. For each of a set of targets to be considered, a bounding box of the target is tested against a current range union result. If the bounding box is completely contained in the current range union result, the target is excluded from further consideration. Otherwise, the target is processed. When the target is an entity, it is determined whether the entity meets the entity filtering criteria. If so a union is computed and the current range union result updated. When each of the targets to be considered in the spatial index has been subject to test or excluded, the current range union result is returned as a final range union result.

## Claims

### Claim 1

A method for computing a union of bounding boxes of entities in a relational database indexed by a spatial index, filtered according to an entity filtering criteria, the method comprising:
receiving, by a relational database system executing on an electronic device, a query statement requesting the union of the bounding boxes of entities in the relational database filtered according to the entity filtering criteria;
for each of a set of targets to be considered in the spatial index, testing a bounding box of the target against a current range union result, and
if the bounding box of the target subject to test is completely contained in the current range union result, excluding the target subject to test from further consideration and when the target subject to test is an internal node excluding any lower level nodes or entities in the spatial index pointed to from the internal node from further consideration, and
if the bounding box of the target subject to test is not completely contained in the current range union result, when the target subject to test is an entity, determining if the entity meets the entity filtering criteria, and if so, computing a union of a bounding box of the entity and the current range union result, and storing the union as the current range union result; and
when each of the targets to be considered in the spatial index has been subject to test or excluded, returning the current range union result as a final range union result.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
creating a backchannel object that maintains the current range union result.

### Claim 3 (depends on 2)

The method of claim 2, wherein the backchannel object also maintains an indication of a most recent bounding box tested.

### Claim 4 (depends on 1)

The method of claim 1, wherein the testing is performed by a spatial testing function, the spatial testing function being an extension function implemented by the relational database system executing on the electronic device.

### Claim 5 (depends on 1)

The method of claim 1, wherein the returning is performed by an aggregate function, the aggregate function being an extension function implemented by the relational database system executing on the electronic device.

### Claim 6 (depends on 1)

The method of claim 1, wherein the relational database system is a SQL relational database system.

### Claim 7 (depends on 6)

The method of claim 6, wherein the query statement is a SQL SELECT statement, and the entity filtering criteria are WHERE criteria.

### Claim 8 (depends on 1)

The method of claim 1, wherein the spatial index is an R-tree.

### Claim 9 (depends on 1)

The method of claim 1, wherein the relational database stores three-dimensional (3-D) spatial data.

### Claim 10 (depends on 1)

The method of claim 1, wherein the relational database system is a SQL embedded database system of a client application executing on the electronic device.

### Claim 11 (depends on 10)

The method of claim 10, wherein the client application is a computer aided design (CAD) viewing application, and each entity corresponds to an element of a model used by the CAD viewing application.

### Claim 12 (depends on 1)

The method of claim 1, wherein the electronic device is a tablet computer.

### Claim 13

A non-transitory computer-readable medium containing executable instructions, the executable instructions, when executed by one or more processors, operable to:
process a query statement requesting a union of bounding boxes of entities in a relational database that includes spatial data filtered according to an entity filtering criteria, wherein the entities in the relational database are indexed by a spatial index;
for each of a set of targets to be considered in the spatial index, test a bounding box of the target against a current range union result, and
if the bounding box of the target subject to test is completely contained in the current range union result, exclude the target subject to test from further consideration and when the target subject to test is an internal node exclude any lower level nodes or entities in the spatial index pointed to from the internal node from further consideration, and
if the bounding box of the target subject to test is not completely contained in the current range union result, when the target subject to test is an entity, determine if the entity meets the entity filtering criteria, and if so, compute a union of a bounding box of the entity and the current range union result, and store the union as the current range union result; and
when each of the targets to be considered in the spatial index has been subject to test or excluded, return the current range union result as a final range union result.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the executable instructions, when executed by the one or more processors, are further operable to:
create a backchannel object that maintains the current range union result.

### Claim 15 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the backchannel object also maintains an indication of a most recent bounding box tested.

### Claim 16 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the executable instructions comprise a spatial testing function, the spatial testing function being an extension function that tests of the bounding box of the target against the current range union result.

### Claim 17 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the executable instructions comprise an aggregate function, the aggregate function being an extension function that returns the final range union result.

### Claim 18

An electronic device configured to compute a union of bounding boxes of entities in a relational database indexed by a spatial index, filtered according to an entity filtering criteria, the electronic device comprising:
a display screen;
a processor configured to execute executable instructions; and
a memory configured to store executable instructions and data, the executable instructions and data including:
a relational database having entities indexed by the spatial index,
a client application configured to request a union of bounding boxes of entities in the relational database filtered according to an entity filtering criteria, and
a relational database system configured to,
for each of a set of targets to be considered in the spatial index, test a bounding box of the target against a current range union result, and
if the bounding box of the target subject to test is completely contained in the current range union result, exclude the target subject to test from further consideration and when the target subject to test is an internal node exclude any lower level nodes or entities in the spatial index pointed to from the internal node from further consideration, and
if the bounding box of the target subject to test is not completely contained in the current range union result, when the target subject to test is an entity, determine if the entity meets the entity filtering criteria, and if so, compute a union of a bounding box of the entity and the current range union result, and store the union as the current range union result,
when each of the targets to be considered in the spatial index has been subject to test or excluded, return the current range union result as a final range union result.

### Claim 19 (depends on 18)

The electronic device of claim 18, wherein the electronic device is a tablet computer.