[특허]Joining two database relations on a common field in a parallel relational database field

Joining two database relations on a common field in a parallel relational database field 원문보기

IPC분류정보
국가/구분	United States(US) Patent 등록
국제특허분류(IPC7판)	G06F-015/40
출원번호	US-0417366 (1989-10-05)
발명자 / 주소	Dias Daniel M. (Mahopac NY) Wolf Joel L. (Goldens Bridge NY) Yu Philip S. (Chappaqua NY)
출원인 / 주소	IBM Corporation (Armonk NY 02)
인용정보	피인용 횟수 : 52 인용 특허 : 0

초록 ▼

A technique for performing joins in parallel on a multiple processor database system effectively deals with data skew. The join operation is performed in three stages with an optional fourth stage. The first stage is a preparatory stage, the detail of which depends on the underlying join algorithm used. This preparatory stage provides pre-processing the results of which are used in the following stage as the basis for defining subtasks for the final join operation. The data provided in the first stage is used in the second stage to both define subtasks and to optimally allocate these subtasks to different processors in such a manner that the processors are close to equally loaded in the final join operation, even in the presence of data skew. This second stage is an assignment stage the details of which depend on the underlying join algorithm. Once the second stage has completed its processing of the subtasks, the subtasks are shipped to their assigned processors for processing and the final join of the two relations in the third stage. The method used in the final join operation depends on the underlying join algorithm used. Optionally, during the actual join as performed in the third stage, there could be a dynamic re-assignment of the subtasks should the join operation become unbalanced.

대표청구항 ▼

In a multi-processor database machine having P parallel processors linked via an interconnect network, said P processors having storage means for storing database relations to be joined, a method performed by said database machine of joining first and second database relations stored on said storage means on a common field, said method comprising the steps of: (a) partitioning the first relation into a multiplicity of partitions and the second relation into a corresponding multiplicity of partitions such that each individual value in the common field corresponds uniquely to one of the partitions of the first relation and uniquely to the corresponding one of the partitions of the second relation to define a current set of jobs, each consisting of a task of joining a partition of the first relation with a corresponding partition of the second relation; (b) scheduling a current set of jobs among said P processors using a minimum makespan optimization technique that schedules said jobs such that a maximum running time on any processor is minimized; (c) estimating the amount of completion time skew which would result if P processors were to perform the current set of jobs as scheduled in step (b); (d) comparing the estimated amount of skew with a skew standard; and (e) if the estimated skew meets the skew standard, executing the current set of jobs as last scheduled using P processors, thereby joining said two database relations on a common field with minimum completion time skew.

이 특허를 인용한 특허 (52)

Fraley Brad James ; Schneider Ira H., Adaptive, predictive progress indicator.
상세보기
Kashyap Anurag ; Gerber Robert H. ; Davison Diane L. ; Atal Sanket ; Spintzik Hannes A. ; Nelson Mark T., Applying distinct hash-join distributions of operators to both even and uneven database records.
상세보기
Larimore, Stefan; Petriuc, Mihai, Batching document identifiers for result trimming.
상세보기
Forster Michael, Caching optimization with disk and/or memory cache management.
상세보기
Benayoun, Alain; Fieschi, Jacques; Michel, Patrick; Le Pennec, Jean-Francois, Compression and encryption protocol for controlling data flow in a network.
상세보기
Forster, Michael; Spratt, Lindsay, Data exploration system and method.
상세보기
Choy David Mun-Hien, Data partitioning by co-locating referenced and referencing records.
상세보기
Al-Omari, Awny K.; Chen, QiFan; Battas, Gregory S.; Siddiqui, Kashif A.; Hanlon, Michael J., Data skew insensitive parallel join scheme.
상세보기
Al-Omari, Awny K.; Chen, QiFan; Battas, Gregory S.; Siddiqui, Kashif A.; Hanlon, Michael J., Data skew insensitive parallel join scheme.
상세보기
Andrei, Mihnea, Database system with methodology for generating bushy nested loop join trees.
상세보기
Cohen, Ben, Database system with multiple processing nodes.
상세보기
Bourbonnais, Serge; Kutsch, Marcel; Li, Xiao; Wierenga, Jonathan, Database table comparison.
상세보기
Raz Yoav ; Scherr Allan L., Dynamic load balancing.
상세보기
Hardwick Jonathan C.,GBX, Dynamic load balancing among processors in a parallel computer.
상세보기
Ruellan, Hervé, Method and device for generating reference patterns from a document written in markup language and associated coding and decoding methods and devices.
상세보기
Agrawal Rakesh ; Shafer John Christopher, Method and system for performing proximity joins on high-dimensional data points in parallel.
상세보기
Haller, Michael; Mitchell, Joan L.; Rijavec, Nenad; Smith, II, James T., Method and system for task mapping to iteratively improve task assignment in a heterogeneous computing system.
상세보기
Hackett Thomas Paul, Method and system for testing for equality/difference in multiple tables of a database.
상세보기
Alain Benayoun FR; Jean-Francois Le Pennec FR; Patrick Michel FR; Claude Pin FR, Method for comparison between a pattern sequence and a variable length key.
상세보기
Jhingran Anant D. ; Kollar Lubor J.,CAX ; Malkemus Timothy R. ; Padmanabhan Sriram K., Method for localizing execution of subqueries and determining collocation of execution of subqueries in a parallel data.
상세보기
Jhingran, Anant D.; Kollar, Lubor J.; Malkemus, Timothy R.; Padmanabhan, Sriram K., Method for localizing execution or subqueries and determining collocation of execution of subqueries in a parallel database.
상세보기
Venn John L. (New Barnet GB2), Method for performing joins between different record types in a database system.
상세보기
Alain Benayoun FR; Jean-Francois Le Pennec FR; Patrick Michel FR; Claude Pin FR, Method for selection on a pattern sequence.
상세보기
Bhattacharya Partha Pratim ; Chung Jen-Yao ; Pirahesh Mir Hamid ; Selinger Patricia G. ; Viveros Marisa S. ; Wang Yun ; Zaino Lawrence Peter, Method of performing a parallel relational database query in a multiprocessor environment.
상세보기
Wolf Joel Leonard ; Yu Philip Shi-lung ; Turek John Joseph Edward, Method of performing a parallel relational database query in a multiprocessor environment.
상세보기
Hardwick Jonathan C.,GBX, Nested parallel language preprocessor for converting parallel language programs into sequential code.
상세보기
Molini, Stephen, Optimization technique for dealing with data skew on foreign key joins.
상세보기
Boyer Philip L. ; Kiernan Gerald G., Optional quantifiers in relational and object-oriented views of database systems.
상세보기
Boyer Philip L. ; Kiernan Gerald G., Outer quantifiers in object-oriented queries and views of database systems.
상세보기
Ogi Yoshifumi,JPX, Parallel processor apparatus in which data is divided in sequential stages.
상세보기
Akaboshi Naoki (Kawasaki JPX) Noguchi Yasuo (Kawasaki JPX) Take Riichiro (Kawasaki JPX) Yokota Haruo (Nomi-gun JPX), Parallel sorting system to reduce the amount of communication between processing devices.
상세보기
Sinclair,Paul L.; Pederson,Donald; Cohen,Steven Bart, Partitioned database system.
상세보기
Kashyap Anurag ; Gerber Robert H. ; Davison Diane L. ; Atal Sanket ; Spintzik Hannes A. ; Nelson Mark T., Processing records from a database.
상세보기
Huang Daniel T. ; Lin Eileen Tien ; Wang Yun, Program product for optimizing parallel processing of database queries.
상세보기
Annapragada, Mrithyunjaya; Rousseau, Benjamin, Redistribution reduction in EPRDBMS.
상세보기
Sinclair,Paul L.; Chiang,Kuorong, Reorganization of database records using partition merging.
상세보기
Sinclair,Paul L., Row hash match scan in a partitioned database system.
상세보기
Arai, Kazufumi; Nonomura, Tatsuhiko; Ogura, Makoto, SYSTEM AND METHOD FOR USER INPUT SEARCH CONDITIONS TO RETRIEVE INTEGRATED SUBSTANCES PHYSICAL PROPERTY DATA, AND RETRIEVE SYSTEMATICALLY CLOSE SUBSTANCES TO SPECIFIED RECORDS BASED UPON DETERMINED SY.
상세보기
Hildrum, Kirsten W.; Khandekar, Rohit M.; Kumar, Vibhore; Parekh, Sujay S.; Rajan, Deepak; Wolf, Joel L.; Wu, Kun-Lung, Scheduling parallel data tasks.
상세보기
Teletia, Nikhil; Halverson, Alan Dale; Shankar, Srinath; Naughton, Jeffrey, Skew-aware storage and query execution on distributed database systems.
상세보기
Cheng, Xun; Schneider, Peter, Splitting of a join operation to allow parallelization.
상세보기
Cheng, Xun; Schneider, Peter, Star and snowflake join query performance.
상세보기
Levine, Fred; Giles, Steven; Boozer, John Forrest, System and method for configuring, sequencing and viewing joins in a query.
상세보기
Lindsay Bruce Gilbert ; Shekita Eugene Jon, System and method for hash loops join of data using outer join and early-out join.
상세보기
Lindsay Bruce Gilbert ; Rajagopalan Sridhar ; Shekita Eugene Jon, System and method for hybrid hash join using over-partitioning to respond to database query.
상세보기
Lyons Kenneth Brent, System and method for multirecord compression in a relational database.
상세보기
Li Zhe ; Ross Kenneth A., System and method for performing an efficient join operation.
상세보기
Ross Kenneth A. ; Lei Hui, System and method for performing joins and self-joins in a database system.
상세보기
Xu, Yu, System, method and computer-readable medium for optimization of multiple-parallel join operations on skewed data.
상세보기
Weber, Thomas P.; Levine, Frederick J.; Kelley, James P., System, method, and data structure for automatically generating database queries which are data model independent and cardinality independent.
상세보기
Weber, Thomas P.; Levine, Frederick J.; Kelley, James P., System, method, and data structure for automatically generating database queries which are data model independent and cardinality independent.
상세보기
Xu, Yu; Ghazal, Ahmad Said, Techniques for optimizing outer joins.
상세보기

IPC	Description
A	생활필수품
A62	인명구조; 소방(사다리 E06C)
A62B	인명구조용의 기구, 장치 또는 방법(특히 의료용에 사용되는 밸브 A61M 39/00; 특히 물에서 쓰이는 인명구조 장치 또는 방법 B63C 9/00; 잠수장비 B63C 11/00; 특히 항공기에 쓰는 것, 예. 낙하산, 투출좌석 B64D; 특히 광산에서 쓰이는 구조장치 E21F 11/00)
A62B-1/08	.. 윈치 또는 풀리에 제동기구가 있는 것

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 국가코드, 자료구분, 상태, 출원번호, 출원일자, 공개번호, 공개일자, 등록번호, 등록일자, 발명명칭(한글), 발명명칭(영문), 출원인(한글), 출원인(영문), 출원인코드, 대표IPC 관리번호, 국가코드, 자료구분, 상태, 출원번호, 출원일자, 공개번호, 공개일자, 공고번호, 공고일자, 등록번호, 등록일자, 발명명칭(한글), 발명명칭(영문), 출원인(한글), 출원인(영문), 출원인코드, 대표출원인, 출원인국적, 출원인주소, 발명자, 발명자E, 발명자코드, 발명자주소, 발명자 우편번호, 발명자국적, 대표IPC, IPC코드, 요약, 미국특허분류, 대리인주소, 대리인코드, 대리인(한글), 대리인(영문), 국제공개일자, 국제공개번호, 국제출원일자, 국제출원번호, 우선권, 우선권주장일, 우선권국가, 우선권출원번호, 원출원일자, 원출원번호, 지정국, Citing Patents, Cited Patents
저장형식	Text(ASCII format) Excel format PIAS분석(.xls)
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

Joining two database relations on a common field in a parallel relational database field 원문보기

초록 ▼

대표청구항 ▼

연구과제 타임라인

이 특허를 인용한 특허 (52)

관련 콘텐츠

특허 원문 보기

IPC 상위 출원인

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

Joining two database relations on a common field in a parallel relational database field 원문보기

초록 ▼

대표청구항 ▼

연구과제 타임라인

전체(0) 논문(0) 특허(0) 보고서(0)

전체(0) 논문(0) 특허(0) 보고서(0)

이 특허를 인용한 특허 (52)

관련 콘텐츠

특허 원문 보기

IPC 상위 출원인

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트