Talk:Merge algorithm: Difference between revisions

Revision as of 05:15, 8 December 2005

Revision as of 05:30, 8 December 2005

Line 39:

----

Pablo may be correct; perhaps mergingupdating a listsorted ofmaster updatesfile withfrom a mastersorted filelist of updates is not a common meaning for the term "merge", and perhapsbut the [[Sort-term "merge" join]]does inseem Oracleto andbe otherused RDBMSs'for queryit evaluation isn't a common meaning forin the termwild either([http://richardbowles.tripod.com/durham/fileproc.htm] says:

Batch Processing

Certainly when Knuth mentions "the idea of merging" on page 385 of volume 3 2ed, he's talking about merging two sorted lists to get a sorted list containing all the items of both lists. -- KragenSitaker

Batch processing occurs when files are processed off-line, i.e. they are saved until some convenient time (e.g. at night) when the computer system is not otherwise being used.

Updating files: the updates, i.e. the changed records, are "batched" together, i.e. saved, and sorted into key order. Then the master file is read, one record at a time, until a record with the same key as the first transaction is found. This master file record is then updated and then the process is repeated.

The updating is done as follows:

* For magnetic tape. Put the updates in a separate file and merge the master and the update to give a new master.

* For a disk, the easiest method is to associate a pointer with each record leading to the next one (linked list). Individual records can be scrubbed and replaced by reseting pointers.

In general, if only one master file is available, it is not altered, but a new master is produced by merging.

Clearly in this context the new master file should not contain both the record from the old master file and the record from the update file, which would be the necessary consequence of interpreting "merge" as "produce multiset union".)

And perhaps the [[Sort-merge join]] in Oracle and other RDBMSs' query evaluation isn't a common meaning for the term either; but certainly the merge in that case isn't concerned with producing a multiset union, but a subset of the multiset cartesian product.

Certainly when Knuth mentions "the idea of merging" on page 385 of volume 3 2ed, he's talking about merging two sorted listssequences (of punched cards) to get a sorted listsequence containing all the items of both lists.sequences --- KragenSitakera sorted multiset union. Pages 197-207 also appear to be talking about producing the multiset union.

In any case, each of these things I called "merge algorithms" when I wrote this page can be conceptualized as the composition of some other function over sequences and the ordinary sorting merge, the one that produces a multiset union.

-- KragenSitaker