Source: http://www.google.de/patents/US5241648
Timestamp: 2013-05-18 23:00:24
Document Index: 225421708

Matched Legal Cases: ['Application No. 61', 'Application No. 61', 'Application No. 58', 'Application No. 58', 'Application No. 58', 'Application No. 58', 'Application No. 59', 'Application No. 59', 'Application No. 59', 'Application No. 59']

Patent US5241648 - Hybrid technique for joining tables - Google PatenteSuche Bilder Maps Play YouTube News Gmail Drive Mehr » Erweiterte Patentsuche | Webprotokoll | Anmelden Erweiterte Patentsuche PatenteResults of a relational data base management system are joined in a process requiring, first, existence of an index on the join columns of the inner table, and, second, ordering on the join column of the first table. First, the index on the inner table's join column is scanned for rows of the inner table...http://www.google.de/patents/US5241648?utm_source=gb-gplus-sharePatent US5241648 - Hybrid technique for joining tables Ver�ffentlichungsnummerUS5241648 APublikationstypErteilung Anmeldenummer07/479,523 Ver�ffentlichungsdatum31. Aug. 1993Eingetragen13. Febr. 1990 Priorit�tsdatum13. Febr. 1990Auch ver�ffentlicht unterEP0442684A2 ErfinderJosephine M. ChengDonald J. HaderleRichard W. HedgesBalakrishna R. IyerChandrasekaran MohanYun WangUrspr�nglich Bevollm�chtigterInternational Business Machines Corporation US-Klassifikation1/1715/255707/999.7Internationale KlassifikationG06F12/00G06F17/30 UnternehmensklassifikationG06F17/30498G06F17/30595 Europ�ische KlassifikationG06F17/30S4P4P3JG06F17/30S8RReferenzenPatentzitate (8)Nichtpatentzitate (30) Referenziert von (87)Externe LinksUSPTO USPTO-Zuordnung EspacenetHybrid technique for joining tablesUS 5241648 A Zusammenfassung Results of a relational data base management system are joined in a process requiring, first, existence of an index on the join columns of the inner table, and, second, ordering on the join column of the first table. First, the index on the inner table's join column is scanned for rows of the inner table having join column values matching such values of rows in the outer table. This is done in a single pass through the outer table. Next, a temporary work table containing the identifiers of inner table rows having join column values matching those of the outer table is produced by concatenating the row identifiers to their matching outer table rows. Following this, the temporary work table is ordered by the identifiers. Last, the identifier list of inner table rows is used to retrieve the corresponding rows of the inner table. All predicates local to the inner table are applied to the retrieved rows, and those satisfying these local predicates are combined with their matching outer table rows and returned to the user.
We claim: 1. A machine-executed method for joining first and second tables of a relational database system, the system including an index on a join column of the second table, the method comprising the relational database system-performed steps of: (a) comparing the rows of the first table with a local predicate; (b) retrieving rows of the first table which satisfy the local predicate and entering the rows into a sort table; (c) ordering the rows of the sort table by join column values; (d) retrieving, from the index, identifiers of rows of the second table having join column values satisfying a join predicate and entering the identifiers in a row index (RID) list; (e) retrieving, from the second table, rows matching the identifiers of step (d); and (f) combining the rows of the sort table with the rows retrieved in step (e) to produce composite rows and entering the composite rows in an intermediate result table.
3. The method of claim 1, wherein further including the following steps performed after step (d) and prior to step (e): combining the identifiers retrieved from the index with fields of respective matching sort table rows to produce intermediate rows; and ordering the intermediate rows by the identifiers in an intermediate table.
4. The method of claim 1, wherein the index includes an index tree, the index tree including a plurality of nodes, certain nodes of the plurality of nodes being children of other nodes in the plurality of nodes, certain of the children being leaves, wherein in step (c) includes: (c1) maintaining in each child node in the tree a pointer to the child node's parent; (c2) maintaining in each node a set of data structures, each data structure including a pointer to a child of the node and a maximum identifier value contained in a leaf of a subtree reached through the child; (c3) locating the leaf containing the lowest identifier value of a set of identifier values and recording the values; (c4) if a next higher identifier value of the set of identifier values is not on the leaf, following the parent pointer from the leaf to the node containing a child pointer to a node which is the root of a subtree containing the next higher identifier value; (c5) following child pointers from the node of step (c4) to the leaf containing the next higher identifier value in recording the value; and (c6) recursively performing steps (c4) and (c5) until all values in the set of identifier values have been recorded.
5. A machine-executable method for joining first and second tables in a relational database system, the system providing a prefetch facility and including an index on a join column of the second table, comprising the relational database system-performed steps of: (a) retrieving rows of the first table which satisfy a first local predicate and placing the rows into a sort table in an order determined by join column values; (b) identifying rows in the second table having join column values matching join column values of the rows of the sort table of step (a); (c) obtaining from the index row identifiers of the second table rows identified in step (b), each row identifier including a value which identifies a respective row of the second table; (d) combining the identifiers obtained in step (c) with sort table rows to form intermediate rows and placing the intermediate rows in an intermediate result table, wherein each intermediate row includes a row identifier of a row of the second table, a join column value matching the corresponding join column value of the second table row identified by the row identifier and the corresponding join column value of a row of the sort table, and a value corresponding to the first local predicate; (e) if the row identifiers are not in order, ordering the intermediate rows by row identifier values; (f) retrieving from the second table rows matching the row identifiers of step (e) in the prefetch facility; (g) combining second table rows retrieved in step (f) and satisfying a second local predicate with intermediate rows to form result rows, each result row including a join column value of a second table row and a join column value of an intermediate row including the row identifier of the second table row; and (h) placing the result rows in a result table.
Patentzitate Zitiertes PatentEingetragen Ver�ffentlichungsdatum Antragsteller TitelUS449703930. Juni 198229. Jan. 1985Fujitsu LimitedJoin operation processing system in relational modelUS476977228. Febr. 19856. Sept. 1988Honeywell Bull, Inc.Automated query optimization method using both global and parallel local optimizations for materialization access planning for distributed databasesUS477919221. Dez. 198418. Okt. 1988Hitachi, Ltd.Vector processor with a synchronously controlled operand fetch circuitsUS48112076. M�rz 19867. M�rz 1989Oki Electric Industry Company, Ltd.Join operation processing system in distributed data base management systemUS481703615. M�rz 198528. M�rz 1989Brigham Young UniversityComputer system and method for data base indexing and information retrievalUS490122921. Jan. 198613. Febr. 1990Kawashima; KazuhiroParallelized rules processing system using associative memory for pipelined execution of plural join operations and concurrent condition comparingUS504387215. Juli 198827. Aug. 1991International Business Machines CorporationAccess path optimization using degrees of clusteringUS51214945. Okt. 19899. Juni 1992Ibm CorporationJoining two database relations on a common field in a parallel relational database fieldNichtpatentzitateReferenz1Blasgen et al, "Storage and Access in Relational Data Bases", IBM Systems Journal, vol. 16, No. 4, 1977, pp. 363-377.2Blasgen et al, Storage and Access in Relational Data Bases , IBM Systems Journal, vol. 16, No. 4, 1977, pp. 363 377.3Chang, P. V. et al., "Interpretive Database Merge Join Operation," IBM TDB vol. 31 No. 5, Oct. 1988, pp. 301-303.4Chang, P. V. et al., Interpretive Database Merge Join Operation, IBM TDB vol. 31 No. 5, Oct. 1988, pp. 301 303.5Chang, P. V., et al., "Interpretive Database Nested Loop Operation," IBM vol. 31 No. 3, Aug. 1988, pp. 143-145.6Chang, P. V., et al., Interpretive Database Nested Loop Operation, IBM vol. 31 No. 3, Aug. 1988, pp. 143 145.7Copenhaver, M. A. et al., "Interpretive Database Sort Algorithm," IBM TDB vol. 31 No. 3, Aug. 1988, pp. 124-126.8Copenhaver, M. A. et al., Interpretive Database Sort Algorithm, IBM TDB vol. 31 No. 3, Aug. 1988, pp. 124 126.9Ishizuka, Tadatsugu, Translated Summary of Japanese Published Application No. 61 145661, Assignment Management System of Main Storage Area, Jul. 3, 1986.10Ishizuka, Tadatsugu, Translated Summary of Japanese Published Application No. 61-145661, "Assignment Management System of Main Storage Area," Jul. 3, 1986.11Kim, Won, "A New Way to Compute the Product and Join of Relations," University of Illinois, 1980 ACM, pp. 179-187.12Kim, Won, A New Way to Compute the Product and Join of Relations, University of Illinois, 1980 ACM, pp. 179 187.13Kitagami, Hajime et al., Translated Summary of Japanese Published Application No. 58 3031, Join Operation Processing System of Relational Model, Aug. 1, 1983.14Kitagami, Hajime et al., Translated Summary of Japanese Published Application No. 58 3069, Correlation Operation Executing and Processing System, Aug. 1, 1983.15Kitagami, Hajime et al., Translated Summary of Japanese Published Application No. 58-3031, "Join Operation Processing System of Relational Model," Aug. 1, 1983.16Kitagami, Hajime et al., Translated Summary of Japanese Published Application No. 58-3069, "Correlation Operation Executing and Processing System," Aug. 1, 1983.17Krieg, G. J., "Fast Table Joining in Relational Databases and Fast Row Retrieval," IBM TDB vol. 30 No. 2, Jul. 1987, pp. 750-757.18Krieg, G. J., Fast Table Joining in Relational Databases and Fast Row Retrieval, IBM TDB vol. 30 No. 2, Jul. 1987, pp. 750 757.19Lohman, G. M., "Heuristic Method for Joining Relational Database Tables," IBM TDB vol. 30 No. 9, Feb. 1988, pp. 8-10.20Lohman, G. M., Heuristic Method for Joining Relational Database Tables, IBM TDB vol. 30 No. 9, Feb. 1988, pp. 8 10.21Pfister, G., "Parallel Equi-Join Algorithm for Large Relational Database Operations," IBM TDB vol. 30 No. 5, Oct. 1987, pp. 361-365.22Pfister, G., Parallel Equi Join Algorithm for Large Relational Database Operations, IBM TDB vol. 30 No. 5, Oct. 1987, pp. 361 365.23Satou, Kazuhiro, Translated Summary of Japanese Published Application No. 59 117636, Method and Device for Data Processing, Jul. 7, 1984.24Satou, Kazuhiro, Translated Summary of Japanese Published Application No. 59-117636, "Method and Device for Data Processing," Jul. 7, 1984.25Tezuka, Masayoshi et al., Translated Summary of Japanese Published Application No. 59 125461, Outer Joining Operation System of Relational Data Base, Jul. 19, 1984.26Tezuka, Masayoshi et al., Translated Summary of Japanese Published Application No. 59-125461, "Outer Joining Operation System of Relational Data Base," Jul. 19, 1984.27Valduriez et al, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Trans. on Database Systems, vol. 9, No. 1, Mar. 1984, pp. 133 161.28Valduriez et al, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Trans. on Database Systems, vol. 9, No. 1, Mar. 1984, pp. 133-161.29Valduriez, Join Indices, ACM Trans. on Database Systems, vol. 12, No. 2, Jun. 1987, pp. 218 246.30Valduriez, Join Indices, ACM Trans. on Database Systems, vol. 12, No. 2, Jun. 1987, pp. 218-246. Referenziert von Zitiert von PatentEingetragen Ver�ffentlichungsdatum Antragsteller TitelUS544688612. M�rz 199329. Aug. 1995Ricoh Company, Ltd.System from optimizing query processing of multi-attribute distributed relations using local relation tuple numbers to choose semijoinsUS544872730. Apr. 19915. Sept. 1995Hewlett-Packard CompanyDomain based partitioning and reclustering of relations in object-oriented relational database management systemsUS553758930. Juni 199416. Juli 1996Microsoft CorporationMethod and system for efficiently performing database table aggregation using an aggregation indexUS553762214. Okt. 199416. Juli 1996International Business Machines CorporationDatabase engineUS554875517. Febr. 199520. Aug. 1996International Business Machines CorporationSystem for optimizing correlated SQL queries in a relational database using magic decorrelationUS555321819. Apr. 19953. Sept. 1996International Business Machines CorporationGraphical user interface for relating key index properties to database table columnsUS559489825. M�rz 199414. Jan. 1997Microsoft CorporationMethod and system for joining database tables using compact row mapping structuresUS561969217. Febr. 19958. Apr. 1997International Business Machines CorporationSemantic optimization of query order requirements using order detection by normalization in a query compiler systemUS566417219. Juli 19942. Sept. 1997Oracle CorporationRange-based query optimizerUS566652521. Sept. 19959. Sept. 1997The Trustees Of Columbia University In The City Of New YorkSystem and method for performing an efficient join operation on large tables with a small main memoryUS566652616. Mai 19969. Sept. 1997Microsoft Corp.Method and system for supporting scrollable, updatable database queriesUS567140330. Dez. 199423. Sept. 1997International Business Machines CorporationIterative dynamic programming system for query optimization with bounded complexityUS576500526. Mai 19939. Juni 1998Hitachi Software Engineering Co., Ltd.Method for preparing formUS57746925. Okt. 199530. Juni 1998International Business Machines CorporationOuter quantifiers in object-oriented queries and views of database systemsUS578189623. Apr. 199614. Juli 1998Microsoft CorporationMethod and system for efficiently performing database table aggregation using an aggregation indexUS57971365. Okt. 199518. Aug. 1998International Business Machines CorporationOptional quantifiers in relational and object-oriented views of database systemsUS580235716. Apr. 19961. Sept. 1998The Trustees Of Columbia University In The City Of New YorkSystem and method for performing an efficient join operationUS581582919. Juli 199529. Sept. 1998Axium International, Inc.Job cost accounting data compression and indexing system and methods for doing the sameUS58192682. Mai 19976. Okt. 1998International Business Machines CorporationMethod and system for testing for equality/difference in multiple tables of a databaseUS582626222. M�rz 199620. Okt. 1998International Business Machines CorporationParallel bottom-up construction of radix treesUS590389315. Sept. 199711. Mai 1999International Business Machines CorporationMethod and apparatus for optimizing a merge-join operation across heterogeneous databasesUS597879311. Febr. 19992. Nov. 1999Informix Software, Inc.Processing records from a databaseUS59832158. Mai 19979. Nov. 1999The Trustees Of Columbia University In The City Of New YorkSystem and method for performing joins and self-joins in a database systemUS602916015. Aug. 199722. Febr. 2000International Business Machines CorporationMethod and means for linking a database system with a system for filing dataUS606499915. Apr. 199816. Mai 2000Microsoft CorporationMethod and system for efficiently performing database table aggregation using a bitmask-based indexUS613454211. Okt. 199617. Okt. 2000Rustige; HaynoDatabase management system and data transmission methodUS61673995. Mai 199826. Dez. 2000Ncr CorporationJoin index for relational databasesUS618901010. Juni 199813. Febr. 2001Platinum Technology, Inc.Method for repairing constraint violations in a database management systemUS622663922. Sept. 19981. Mai 2001International Business Machines CorporationSystem and method for hybrid hash join using over-partitioning to respond to database queryUS62531976. Okt. 199826. Juni 2001International Business Machines CorporationSystem and method for hash loops join of data using outer join and early-out joinUS637423224. Juni 199816. Apr. 2002Oracle Corp.Method and mechanism for retrieving values from a databaseUS642166314. Juni 199916. Juli 2002International Business Machines CorporationOptimization of joined table expressions by extended access path selectionUS643978316. Jan. 199727. Aug. 2002Oracle CorporationRange-based query optimizerUS64533253. Febr. 199717. Sept. 2002International Business Machines CorporationMethod and means for backup and restoration of a database system linked to a system for filing dataUS650518815. Juni 20007. Jan. 2003Ncr CorporationVirtual join index for relational databasesUS650518915. Juni 20007. Jan. 2003Ncr CorporationAggregate join index for relational databasesUS65980417. Sept. 200022. Juli 2003International Business Machines CorporationMethod, system, and program for processing modifications to data in tables in a database systemUS660409726. Juli 20015. Aug. 2003International Business Machines CorporationMethod, system, and program for using control data structures when performing operations with respect to a databaseUS661872015. Juni 20009. Sept. 2003Ncr CorporationCommon spool files for maintaining join indexesUS664022110. Juli 200028. Okt. 2003Sas Institute Inc.System and method for configuring, sequencing and viewing joins in a queryUS66436365. Juni 20014. Nov. 2003Ncr CorporationOptimizing a query using a non-covering join indexUS664363726. Juli 20014. Nov. 2003International Business Machines CorporationMethod, system, and program for using a fetch request to make data available to an application programUS664364930. Jan. 20014. Nov. 2003International Business Machines CorporationUtility for cross platform database queryUS666567828. Dez. 200016. Dez. 2003International Business Machines CorporationMethod, system, and program for optimistic concurrency control for scrollable cursors in a databaseUS669430526. Juli 200117. Febr. 2004International Business Machines CorporationMethod, system, and program for processing modifications to data in tables in a database systemUS67115635. M�rz 200123. M�rz 2004Lafayette Software Inc.Methods of organizing data and processing queries in a database system, and database system and software product for implementing such methodsUS672173126. Juli 200113. Apr. 2004International Business Machines CorporationMethod, system, and program for processing a fetch request for a target row at an absolute position from a first entry in a tableUS673560528. Febr. 200111. Mai 2004International Business Machines CorporationMethod and apparatus for synchronizing not-logged application temporary tables in a multi-node relational database management systemUS675465326. Juli 200122. Juni 2004International Business Machines CorporationMethod, system, and program for processing a fetch request for a target row in a table that precedes as current rowUS685699630. M�rz 200115. Febr. 2005International Business Machines CorporationMethod, system, and program for accessing rows in one or more tables satisfying a search criteriaUS694463310. Dez. 200313. Sept. 2005Ncr CorporationPerforming a join in a partitioned database systemUS697345710. Mai 20026. Dez. 2005Oracle International CorporationMethod and system for scrollable cursorsUS702069919. Dez. 200128. M�rz 2006Sun Microsystems, Inc.Test result analyzer in a distributed processing framework system and methods for implementing the sameUS708933129. Febr. 20008. Aug. 2006Oracle International CorporationMethod and mechanism for reducing client-side memory footprint of transmitted dataUS709295510. Mai 200215. Aug. 2006International Business Machines CorporationSchema for SQL statementsUS710359024. Aug. 20015. Sept. 2006Oracle International CorporationMethod and system for pipelined database table functionsUS710360328. M�rz 20035. Sept. 2006International Business Machines CorporationMethod, apparatus, and system for improved duplicate record processing in a sort utilityUS711102530. Apr. 200319. Sept. 2006International Business Machines CorporationInformation retrieval system and method using index ANDing for improving performanceUS713684731. Aug. 200114. Nov. 2006International Business Machines CorporationMethod and system for dynamically changing cursor attributes in an embedded SQL applicationUS733085910. Sept. 200312. Febr. 2008International Business Machines CorporationDatabase backup system using data and user-defined routines replicators for maintaining a copy of database on a secondary serverUS735971428. Febr. 200615. Apr. 2008Microsoft CorporationContext-aware and location-aware cellular phones and methodsUS736335715. Okt. 200422. Apr. 2008Microsoft CorporationContext-aware systems and methods, location-aware systems and methods, context-aware vehicles and methods of operating the same, and location-aware vehicles and methods of operating the sameUS738329331. Okt. 20073. Juni 2008International Business Machines CorporationDatabase backup system using data and user-defined routines replicators for maintaining a copy of database on a secondary serverUS738928410. Mai 200217. Juni 2008Oracle International CorporationMethod and mechanism for efficient processing of remote-mapped queriesUS74477865. Mai 20064. Nov. 2008Oracle International CorporationEfficient locking of shared data that is accessed for reads in a cluster databaseUS747220229. Nov. 200430. Dez. 2008Microsoft CorporationContext-aware systems and methods, location-aware systems and methods, context-aware vehicles and methods of operating the same, and location-aware vehicles and methods of operating the sameUS748394429. Nov. 200427. Jan. 2009Microsoft CorporationContext aware computing devices and methodsUS752985415. Okt. 20045. Mai 2009Microsoft CorporationContext-aware systems and methods location-aware systems and methods context-aware vehicles and methods of operating the same and location-aware vehicles and methods of operating the sameUS761035110. Mai 200227. Okt. 2009Oracle International CorporationMethod and mechanism for pipelined prefetchingUS762065624. Jan. 200517. Nov. 2009Microsoft CorporationMethods and systems for synchronizing visualizations with audio streamsUS76402447. Juni 200429. Dez. 2009Teredata Us, Inc.Dynamic partition enhanced joining using a value-count indexUS766081421. Dez. 20059. Febr. 2010Teradata Us, Inc.Techniques for mapping a physical table to multiple virtual tablesUS766893129. Nov. 200423. Febr. 2010Microsoft CorporationContext-aware systems and methods, location-aware systems and methods, context-aware vehicles and methods of operating the same, and location-aware vehicles and methods of operating the sameUS769828322. Juli 200213. Apr. 2010Primentia, Inc.System and method for organizing dataUS77254238. Febr. 200125. Mai 2010Teradata Us, Inc.Analyzing associations in the order of transactionsUS774770423. M�rz 200729. Juni 2010Microsoft CorporationContext aware computing devices and methodsUS775194415. Okt. 20046. Juli 2010Microsoft CorporationContext-aware and location-aware systems, methods, and vehicles, and method of operating the sameUS784907318. Dez. 20067. Dez. 2010Ianywhere Solutions, Inc.Load balancing for complex database query plansUS78701139. Sept. 200511. Jan. 2011Primentia, Inc.System and method for organizing dataUS78736297. Juni 200418. Jan. 2011Teradata Us, Inc.Dynamic partition enhanced inequality joining using a value-count indexUS797522915. Okt. 20045. Juli 2011Microsoft CorporationContext-aware systems and methods location-aware systems and methods context-aware vehicles and methods of operating the same and location-aware vehicles and methods of operating the sameCN100412900C9. Mai 200320. Aug. 2008Ricoh KkMethod and management computer for manufacturing rated value labelCN100552677C30. Aug. 200521. Okt. 2009Microsoft CorpMethod, system, and computer-readable medium for merging data from multiple data sources for use in an electronic documentEP1349081A128. M�rz 20021. Okt. 2003LION Bioscience AGMethod and apparatus for querying relational databasesWO1997011432A119. Sept. 199627. M�rz 1997The Trustees Of Columbia University In The City OfAn efficient join operation performed on large tablesWO1997011433A119. Sept. 199627. M�rz 1997The Trustees Of Columbia University In The City OfPerforming efficient join operations on large tablesWO2003083713A128. M�rz 20039. Okt. 2003Etzold, ThureMethod and apparatus for querying relational databasesDrehenOriginalbildGoogle-Startseite - Sitemap - USPTO-Bulk-Downloads - Datenschutzerkl�rung - Nutzungsbedingungen - �ber Google Patente - Feedback gebenDaten bereitgestellt von IFI CLAIMS Patent Services.© 2012 Google