Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-03-26
2004-05-04
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06732107
ABSTRACT:
BACKGROUND
Relational databases are used for storage and retrieval of information. The information is structured in the database as two-dimensional tables of rows and columns. A column heading designates the type of data stored in each column. The information is stored in a non-volatile medium such as a disk array.
Users may access the database information typically by using database management software. The database storage media and management software together comprise a database management system, or DBMS. DBMSs may be implemented on a centralized mainframe system, or may be distributed in a client-server network, as examples.
The database management software includes specialized commands for accessing the database information. For example, a common command for accessing data is a Structured Query Language (SQL) “select” query. Using the select query, one or more rows from one or more tables of the database may be retrieved.
The database data typically includes numbers and strings. An employee phone list, for example, may be included in a database system. More recently, spatial data, such as images, are stored along with the more traditional data. Spatial data is typically more unwieldy to manage in a database than are numbers and strings.
Traditionally, DBMSs processed queries in batch mode. In other words, a user wanting to extract information from the database would submit a query, wait a long time during which no feedback is provided, and then receive a precise answer.
One alternative to batch query processing is known as adaptive query processing. Adaptive query processing involves an iterative feedback process in which the DBMS receives information from its environment and uses the information to adapt the behavior of the query. Rather than receiving a precise answer after a long wait, an approximate answer may be received almost immediately upon submitting a query.
Database queries often invoke join operations to produce query results. Upon receiving the multi-table query, tuples, or rows, from one table are joined with tuples from a second table, to produce a result. When the tuples contain spatial data, the join operation may be prohibitively slow, in some environments.
SUMMARY
In accordance with the embodiments described herein, a method is disclosed in which first tuples are stored in a first table and second tuples are stored in a second table in a system, the first and second tuples are partitioned into plural portions and joined based on the partitioned portions.
REFERENCES:
patent: 5701467 (1997-12-01), Freeston
patent: 5761652 (1998-06-01), Wu et al.
patent: 5884320 (1999-03-01), Agrawal et al.
patent: 5963956 (1999-10-01), Smartt
patent: 6003036 (1999-12-01), Martin
patent: 6014614 (2000-01-01), Herring et al.
patent: 6092061 (2000-07-01), Choy
patent: 6148295 (2000-11-01), Megiddo et al.
patent: 6185557 (2001-02-01), Liu
patent: 6282570 (2001-08-01), Leung et al.
patent: 6353832 (2002-03-01), Acharya et al.
patent: 6446060 (2002-09-01), Bergman et al.
patent: 6449606 (2002-09-01), Witkowski
A. Aiken et al., “The Tioga-2 Database Visualization Environment”, ICDE 1996, pp. 208-217.
N. Beckmann et al., “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles”, SIGMOD Conf. 1990, pp.. 322-331.
T. Brinkhoff et al., “Parallel Processing of Spatial Joins Using R-Trees”, ICDE 1996, pp. 258-265.
T. Brinkhoff et al., “Efficient Processing of Spatial Joins Using R-trees”, SIGMOD Conf. 1993, pp. 237-246.
M. Carey et al., “The BUCKY Objection-Relational Benchmark”, SIGMOD Conf. 1997, pp. 135-146.
D. DeWitt et al., “Client-Server Paradise”, VLDB 1994, pp. 558-569.
V. Gaede et al., “Multidimensional Access Methods”, Computing Surveys 30(2), 1998, pp. 170-231.
G. Graefe, “Query Evaluation Techniques for Large Databases” , ACM Comput. Surveys, 25(2):73-170, Jun. 1993.
A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching”, SIGMOD Conf. 1984, pp. 47-57.
P. Haas et al., “Join Algorithms for Online Aggregation”, IBM Research Report RJ10126, 1998.
P. Haas, “Techniques for Online Exploration of Large Object-Relational Dataeets”, Proc. 11thIntl. Conf. Scientific and Statistical Database Management, 1999, pp. 4-12.
J. Hellerstein et al., “Interactive Data Analysis: The Control Project”, IEEE Computer, 32, Aug. 1999, pp. 51-59.
J. Hellerstein et al., “Informix under CONTROL: Online Query Processing”, Data Mining and Knowledge Discovery, 2000.
J. Hellerstein, “Online Processing Redux”, IEEE Data Engineering Bulletin, Sep. 1997.
J. Hellerstein, “Looking Forward to Interactive Queries”, Database Programming and Design, Aug. 1998.
J. Hellerstein et al., “Adaptive Query Processing: Technology in Evolution”, IEEE Data Engineering Bulletin, Jun. 2000.
P. Haas et al., “Ripple Joins for Online Aggregation”, SIGMOD Conf. 1999, pp. 287-298.
J. Hellerstein et al., “Online Aggregation”, SIGMOD Conf. 1997, pp. 171-182.
Z. Ives et al., “An Adaptive Query Execution System for Data Integration”, SIGMOD Conf. 1999, pp. 299-310.
I. Kamel et al., “Parallel R-trees”, SIGMOD Conf. 1992, pp. 195-204.
M. Lo et al., “Spatial Joins Using Seeded Trees”, SIGMOD Conf. 1994, pp. 209-220.
M. Lo et al., “Spatial Hash-Joins”, SIGMOD Conf. 1996.
M. Livny et al., “DEVise: Integrated Querying and Visual Exploration of Large Datasets”, SIGMOD Conf. 1997, pp. 301-312.
F. Olken, “Random Sampling from Databases”, Ph.D. Dissertation, UC Berkeley, Apr. 1993, available as Tech. Report LBL-32883, Lawrence Berkeley Laboratories.
H. Pang et al., “Partially Preemptible Hash Joins”, SIGMOD Conf. 1993, pp. 59-68.
H. Pang et al., “Memory-Adaptive External Sorting”, VLDB 1993, pp. 618-629.
J. Patel et al., “Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation”, SIGMOD Conf. 1997, pp. 336-347.
J. Patel et al., “Clone Join and Shadow Join: Two Parallel Algorithms for Executing Spatial Join Operations”, Technical Report, University of Wisconsin, CS-TR-99-1403, Aug. 1999.
J. Patel et al., “Partition Based Spatial-Merge Join”, SIGMOD Conf. 1996, pp. 259-270.
M. Stonebraker et al., “The Sequoia 2000 Storage Benchmark”, SIGMOD Conf. 1993, pp. 632-645.
J. Shanmugasundaram et al., “Relational Databases for Querying XML Documents: Limitations and Opportunities”, VLDB 1999, 302-314.
K. Tan et al., “Online Feedback for Nested Aggregate Queries with Multi-Threading”, VLDB 1999, pp. 18-29.
T. Urhan et al., “XJoin: Getting Fast Answers from Slow and Bursty Networks”, Technical Report, CS-TR-3994, UMIACS-TR-99-13, Feb. 1999, pp. 1-21.
Ellmann Curt J.
Luo Gang
Naughton Jeffrey F.
Le Miranda
NCR Corporation
Robinson Greta
Trop Pruner & Hu P.C.
LandOfFree
Spatial join method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spatial join method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spatial join method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3217902