Source: http://www.google.com/patents/US4644471?dq=5636223
Timestamp: 2015-01-31 04:04:05
Document Index: 210968761

Matched Legal Cases: ['art 104', 'art 105', 'art 109', 'art 104', 'art 104', 'art 104', 'art 105', 'art 105', 'arts 603', 'art 109', 'art 105']

Patent US4644471 - Method for processing a data base - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsThe data elements for a column of a table are fetched from irregular address locations in memory and stored as vector data with a regular address increment. Vector designating data is also generated which includes at least the first element address of the stored vector data and the increment of the vector....http://www.google.com/patents/US4644471?utm_source=gb-gplus-sharePatent US4644471 - Method for processing a data baseAdvanced Patent SearchPublication numberUS4644471 APublication typeGrantApplication numberUS 06/684,789Publication dateFeb 17, 1987Filing dateDec 21, 1984Priority dateDec 23, 1983Fee statusPaidAlso published asUS4785400Publication number06684789, 684789, US 4644471 A, US 4644471A, US-A-4644471, US4644471 A, US4644471AInventorsKeiji Kojima, Shunichi ToriiOriginal AssigneeHitachi, Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (1), Referenced by (33), Classifications (14), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetMethod for processing a data baseUS 4644471 AAbstract The data elements for a column of a table are fetched from irregular address locations in memory and stored as vector data with a regular address increment. Vector designating data is also generated which includes at least the first element address of the stored vector data and the increment of the vector. The vector data is processed by a program routine which can perform the processing required by a selected command and which includes vector instructions each designating at least one set of vector data elements to be executed, in such a manner that vector data elements are fetched successively from the data storage device and are supplied successively to a pipelined arithmetic or logical operation unit.
What is claimed is: 1. A method for processing a data base in a computer, which data base comprises a plurality of data tables to be processed, each comprised of a plurality of columns and rows, a plurality of data elements belonging to respective rows of the same column being assigned storage locations within a data storage device whose addresses are not uniformly separated from those for respective data elements in the neighboring rows, the method comprising the steps of:generating a command requesting processing of data elements belonging to selected columns within selected tables; accessing the data elements within the storage device which belong to the selected columns within the selected tables, in response to said command, to fetch and store the accessed data elements so that data elements belonging to each selected columns within each selected table are stored as vector data at locations within said storage device whose addresses are separated by a uniform increment from those for respective rows in the selected table; storing vector designating data for each vector data including at least the first element address and an address increment for each vector data; executing a program routine which can perform the processing requested by the command, and which includes vector instructions each designaing at least one vector data to be executed and the kind of processing to be carried out, said program routine being executed in such a manner that elements of vector data designated by a vector instruction are successively accessed, based upon the vector designating data for the designated vector data and are sent from the storage device to a piplelined arithmetic or logical operation unit in order to effect operation thereon successively. 2. A method according to claim 1, wherein a plurality of data elements belonging to respective rows and to the same column of a selected data table are assigned storage loations within the data storage device whose addresses are defined by a combination of a data page number and a slot number, said data page number designating the start addresses of a corrsponding one of data pages in which the storage locations of the data storage device are divided, and said slot number designating an address of a corresponding one of a plurality of slot pointers in which an address of a storage location on the page for a corresponding data element is stored, wherein said step of accessing data elements belonging to a selecteed column with a selected table includes:accessing the slot pointers for data elements within the selected column within the selected table, based upon the data page number and the slot number, in order to fetch addresses for the data elements to store the fetched addresses as a list vector data in said data storage device; accessing data elements for stored list vector data; and accessing said data storage device, based upon said accessed list vector data, to fetch said data elements from said data storage device successively. 3. A method according to claim 1, wherein said program routine includes a joint routine for finding first data elements from a first vector data each belonging to a selected column of a first selected table and at the same time belonging to a first selected column of a second selected table, and finding second data elements from a second vector data each belonging to a second selected column within the first table and belonging to the same row within the first selected table as one of the first data elements, and finding third data elements from a third vector data each belonging to a second selected column within the second selected table and to the same row within the second selected row as one of the first data elements.
BACKGROUND OF THE INVENTION The present invention relates to a method for processing a data base, especially a relational data base.
SUMMARY OF THE INVENTION Therefore, it is an object of the present invention to provide a method for performing a piplelined processing on a data base which includes data elements spaced at irregular address increments.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a schematic diagram of a data base managing system;
DETAILED EXPLANATION OF A PREFERRED EMBODIMENT (Outline of an operaton of the system) FIG. 1 shows a shematic diagram of a relational data base managing system according to the present invention. In a main storage 101, a search command is issued from an application program 102 and is examined by an interface part 104 of a relational data base managing program 103, which identifies the command as a search command. An analysis part 105 of the program 103 then analyzes the search command to determine the most suitable process sequence for that search command, generates codes which designate the determined process sequence, and stores the process sequence designating codes 107 into a control block 106. An execution part 109 of the program 103 refers to the codes stored in the control block 106 and processes the search command received by the interface part 104 according to the process sequence designated by the codes, to provide results of the processing to the application program 102 by way of the interface part 104.
(An example of a process for the search command) In order to faciltate the understanding of the purpose and operation of the described embodiment of the present invention, an example of a search command and the process required thereby will be explained prior to description of the detailed operation.
(Instruction format and details of the data processor) Before going into a detailed explanation of the processing of the system shown in FIG. 1, a brief explanation of the format of a vector instruction will be provided as well as explanation of the details of the data processor 113.
(Data storage form) The operation explained in conection with table data shown in FIGS. 2A to 2D strongly depends upon how the tables are actually stored, i.e., how easy it is to access the data in the tables. As was explained previously, it is beneficial to store data belonging to a table separately in units of a data page, from the standpoint of easiness of insertion or deletion of data elements. The same storage form is employed in this embodiment. The details of a data storage form will be given hereinafter with reference to FIG. 5. A data page area 114 in the subsidiary storage is divided into a plurality of data pages. A data page 302 includes plural data storage areas 304 referred to as a slot. Each slot 304 includes all entries belonging to one row of a table. For example, in the case of a slot for the first row of the table 202 of FIG. 2B, data "A, 316" is stored in the slot. Each slot has its own slot number. Each data page 302 includes slot pointers 303 each indicating a starting address of a respective one of the slots 304 within the same data page 302. The slot pointers are stored at an area starting from the start address of the data page and according to the order of the corresponding slot numbers.
(Data buffer area 110 and data buffer directory 401) When a data page 302 in a subsidiary storage 112 is to be processed by the relational data base managing program 103, the data in the data page 302 is transferred to a data buffer area 110 within a main storage 101 before the processing.
(Row number transformation) A transformation from a row number comprising a page number i and a slot number j to a corresponding storage address of the data for that row within the main storage is carried out in accordance with the sequence of steps in FIG. 7.
(Generation of process sequence designating codes) A search command, for example, as shown in FIG. 2C, is transferred from an application program 102 by way of the interface part 104 of the managing program. The analysis part 105 responds to this search command by determining a process sequence which is judged to be the best according to a selected standard, and provides the process sequence designating code, as shown in FIG. 8. The method of determining the best process sequence by the analysis part 105 is known, for example, in literature by P. G. Selinger et al, "Access Path Selection in a Rational Database Management System" (Prox. ACM SIGMOD Conf. 1979). The code comprises plural process designating sentences. In FIG. 8, each line forms one process designating sentence. Each process designating sentence includes a key word 601, 602, 606, 610, 613 or 618 each designating the kind of process to be performed, and parameter designating parts 603 to 605, 607 to 609, 611 to 612, 614 to 617 or 619 to 621, relating to a respective process.
(Execution of the process sequence designating code) The execution part 109 of the program 103 includes, as shown in FIG. 9, a CONTROL routine 701, a START-PROCESS routine 702, END-PROCESS routine 703, BUILD-VECTOR routine 704, SORT-VECTOR routine 705, JOIN-VECTOR-BY-NESTED-LOOP routine 706, and so on. Each routine corresonds to a respective one of the key words included in the process sequence designating code 107 generated by the analysis part 105 of the program 103.
At first, a value VTOP (1101) which designates a start address of the non-used region 111B (FIG. 13) is set in the variable VDTA.1 (1204), and a row number "4" in a row number entry of the commodity table definition table 1003 is set in the variable VDTA.2 (1205) (step 1302). An initial value of "1" is set in the variables i (1208) and 1 (1209) (step 1303). In a loop of steps from 1304 to 1306, addresses A1 to A4 in the main storage 101 are obtained sequentially for all rows in a table selected by the first parameter 6, in this example, T#1 related to a key word "BUILD-VECTOR", and each obtained address ai (i=1�4) is stored in a location starting from an address designated by VTOP (1101) (step (1305). By changing VTOP by four each time when one of the four addresses A1 to A4 is obtained (step 1306), a vector can be stored in the vector area 111 which comprises four vector elements of thus obtained addresses A1 to A4. The amount "4" of each increase of VTOP (1101) is predetermined by the bit length of the addresses A1 to A4. The data "4" provided to VDTA.2 (1205) also represents the same length. The method of obtaining the addreses as shown by step 1305 was already explained in connection with FIG. 7.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4497039 *Jun 30, 1982Jan 29, 1985Fujitsu LimitedJoin operation processing system in relational model* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS4769772 *Feb 28, 1985Sep 6, 1988Honeywell Bull, Inc.Automated query optimization method using both global and parallel local optimizations for materialization access planning for distributed databasesUS4791561 *Mar 21, 1988Dec 13, 1988Wang Laboratories, Inc.Interactive construction of means for database maintenanceUS4805099 *Mar 21, 1988Feb 14, 1989Wang Laboratories, Inc.Retrieval of related records from a relational databaseUS4839799 *Jul 24, 1986Jun 13, 1989Hitachi, Ltd.Buffer control method for quickly determining whether a required data block is in the bufferUS4858146 *Aug 13, 1986Aug 15, 1989The Babcock & Wilcox CompanyAutomated design of structures using a finite element databaseUS4884218 *Oct 1, 1987Nov 28, 1989International Business Machines CorporationKnowledge system with improved request processingUS4888690 *Mar 21, 1988Dec 19, 1989Wang Laboratories, Inc.Interactive error handling means in database managementUS4967341 *Oct 6, 1989Oct 30, 1990Hitachi, Ltd.Method and apparatus for processing data baseUS4979109 *Jan 14, 1987Dec 18, 1990Hitachi Ltd.Method of controlling a data dictionary directory system in a data base systemUS5008819 *Jul 19, 1989Apr 16, 1991Gorbatenko George GMemory spaced arrayUS5058000 *Jun 15, 1989Oct 15, 1991Prime Computer, Inc.System for accessing remote heterogeneous database including formatting retrieved data into applications program formatUS5072367 *Apr 16, 1990Dec 10, 1991International Business Machines CorporationSystem using two passes searching to locate record having only parameters and corresponding values of an input recordUS5097408 *Dec 14, 1989Mar 17, 1992Wang Laboratories, Inc.Apparatus for specifying a result relation in a relational database system by selection of rowsUS5123103 *Oct 15, 1987Jun 16, 1992Hitachi, Ltd.Method and system of retrieving program specification and linking the specification by concept to retrieval request for reusing program partsUS5210870 *Mar 27, 1990May 11, 1993International Business MachinesDatabase sort and merge apparatus with multiple memory arrays having alternating accessUS5222235 *Feb 1, 1990Jun 22, 1993Bmc Software, Inc.Databases system for permitting concurrent indexing and reloading of data by early simulating the reload process to determine final locations of the dataUS5247665 *Sep 28, 1989Sep 21, 1993Kabushiki Kaisha ToshibaData base processing apparatus using relational operation processingUS5272628 *Apr 16, 1990Dec 21, 1993Microsoft CorporationMethod and system for aggregating tables having dissimilar formatsUS5276870 *Oct 9, 1990Jan 4, 1994Hewlett-Packard CompanyView composition in a data base management systemUS5287494 *Oct 18, 1990Feb 15, 1994International Business Machines CorporationSorting/merging tree for determining a next tournament champion in each cycle by simultaneously comparing records in a path of the previous tournament championUS5423038 *Oct 14, 1992Jun 6, 1995Davis; MarilynSpecialized data management methodUS5544357 *May 26, 1995Aug 6, 1996Paracom CorporationApparatus for managing a databaseUS5548769 *Dec 18, 1992Aug 20, 1996International Business Machines CorporationDatabase engineUS5619713 *Feb 17, 1995Apr 8, 1997International Business Machines CorporationApparatus for realigning database fields through the use of a crosspoint switchUS5953715 *Nov 3, 1997Sep 14, 1999International Business Machines CorporationUtilizing pseudotables as a method and mechanism providing database monitor informationUS6275822 *Nov 9, 1999Aug 14, 2001Joint Technology, CorporationMaintaining very large indexes supporting efficient relational queryingUS6507846 *Nov 9, 1999Jan 14, 2003Joint Technology CorporationIndexing databases for efficient relational queryingUS6950817Oct 11, 1999Sep 27, 2005Bull, S.A.Implementing table queries in a machine with vectorial capabilitiesUS7103601May 5, 2003Sep 5, 2006Bull S.A.Method for preconditioning and encoding data table, and method for the implementation of table requests on a vectoral processorUS7581084 *May 21, 2004Aug 25, 2009Nintendo Co., Ltd.Method and apparatus for efficient loading and storing of vectorsWO1989003559A1 *Oct 4, 1988Apr 20, 1989George G GorbatenkoMemory spaced array for storing relational dataWO1995012846A1 *Oct 4, 1994May 11, 1995Paracom CorpApparatus for accelerating processing of transactions on computer databasesWO2000060498A1 *Oct 11, 1999Oct 12, 2000Bull SaMethod for preconditioning and encoding a data table and method for the implementation of table requests on a vectoral processor* Cited by examinerClassifications U.S. Classification1/1, 715/236, 715/276, 707/999.003International ClassificationG06F1/00, G06F17/16, G06F12/02, G06F12/00, G06F9/38, G06F7/22, G06F17/30Cooperative ClassificationY10S707/99933, G06F17/30595European ClassificationG06F17/30S8RLegal EventsDateCodeEventDescriptionAug 3, 1998FPAYFee paymentYear of fee payment: 12Jul 1, 1994FPAYFee paymentYear of fee payment: 8Jul 2, 1990FPAYFee paymentYear of fee payment: 4Jul 29, 1986ASAssignmentOwner name: HITACHI, LTD., 6, KANDA SURUGADAI 4-CHOME, CHIYODAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:KOJIMA, KEIJI;TORII, SHUNICHI;REEL/FRAME:004582/0652Effective date: 19841213Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KOJIMA, KEIJI;TORII, SHUNICHI;REEL/FRAME:004582/0652Owner name: HITACHI, LTD.,JAPANRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services