Automatic Data Restructuring

Seymour Ginsburg (Computer Science Department, University of Southern California, USA)

Nan C. Shu (BM Los Angeles Scientific Center, USA)

Dan A. Simovici (University of Massachusetts at Boston, Department of Mathematics and Computer Science, USA)

Abstract: Data restructuring is often an integral but non-trivial part of information processing, especially when the data structures are fairly complicated. This paper describes the underpinnings of a program, called the Restructurer, that relieves the user of the "thinking and coding" process normally associated with writing procedural programs for data restructuring. The process is accomplished by the Restructurer in two stages. In the first, the differences in the input and output data structures are recognized and the applicability of various transformation rules analyzed. The result is a plan for mapping the specified input to the desired output. In the second stage, the plan is executed using embedded knowledge about both the target language and run-time efficiency considerations. The emphasis of this paper is on the planning stage. The restructuring operations and the mapping strategies are informally described and explained with mathematical formalism. The notion of solution of a set of instantiated forms with respect to an output form is then introduced. Finally, it is shown that such a solution exists if and only if the Restructurer produces one.

Keywords: data restructuring, hierarchical structures, instantiated forms, non-first normal form databases, solution of a set of instantiated forms

Categories: E.1, H.2