Foundations of Data Organization

Foundations of data organization is a relatively new field of research in comparison to, other branches of science. It is close to twenty years old. In this short life span of this branch of computer science, it has spread to all corners of the world, which is reflected in this book. This book covers new database application areas (databases for advanced applications and CAD/VLSI databases), computational geometry, file allocation & distributed databases, database models (including non­ traditional database models), database machines, query processing & physical structures for relational databases, besides traditional file organization (hashing, index file organization, mathematical file organization and consecutive retrieval property), in order to identify new trends of database research. The papers in this book originally represent talks given at the International Conference on Foundations of Data Organization, which was held on May 21-24, 1985, in Kyoto, Japan. This conference was held at Kyoto University, and sponsored by the organizing committee of the International Conference on Foundations of Data Organization and the Japan Society for the Promotion of Science. The conference was in cooperation with: ACM SIGMOD, IEEE Computer Society, Information Processing Society of Japan, IBM Research, Kyushu University, Kobe University, IBM Japan, Kyoto Sangyo University and Polish Academy of Sciences. This Conference was the follow-up of the first conference, which was hosted by the Polish Academy of Sciences and held at Warsaw in 1981. The Warsaw conference focused mainly on consecutive retrieval property and it's applications.

Databases for Advanced Applications.- Statistics Metadata: Linear Regression Analysis.- Dynamic PATRICIA.- Design of an Integrated DBMS to Support Advanced Applications.- Use of the Relational Model for Data Representation in a Deductively Augmented Database Management System.- Hashing.- Hash-Based File Organization Utilizing Large Capacity Main Memory.- Trie Hashing: Further Properties and Performance.- The Study of A Letter Oriented Minimal Perfect Hashing Scheme.- Consecutive Retrieval Property.- On the Relaxed Consecutive Retrieval Property in File Organization.- Consecutive Retrieval Organization as a File Allocation Scheme on Multiple Disk Systems.- TRACER: Transposed File Organization Scheme with Consecutive Retrieval Property and Its Application to Statistical Database System.- Multiple Query Processing in Local Area Database System.- File Allocation and Distributed Databases.- Management of Table Partitioning and Replication in a Distributed Relational Database System.- On Strict Optimality Property of Allocating Binary Cartesian Product Files on Multiple Disk Systems.- On the Complexity of File Allocation Problem.- A Quantitative Evaluation of Scheduling Systems for the Physical Locking Scheme in a Database System.- Allocation of Documents in Two Level Memory for Information Retrieval Systems.- Mathematical File Organization and Computational Geometry.- Further Results on Hyperclaw Decomposition and Balanced Filing Schemes.- Placing Tiles in the Plane.- Mixed-Type Multiple-Valued Filing Scheme of Order One and Two.- Space Partitioning and Its Application to Generalized Retrieval Problems.- On Computing and Updating Triangulations.- Database Machines.- VLSI Trees for File Organization.- The Inverted File Tree Machine: Efficient Multi-Key Retrieval for VLSI.- Multidimensional Clustering Techniques for Large Relational Database Machines.- A Method for Realistic Comparisons of Sorting Algorithms for VLSI.- Database Models.- Update Propagation in the IFO Database Model.- Computation-tuple Sequences and Object Histories: Extended Abstract.- Projection of Object Histories.- Functional Entity Relationship Model and Update Operations (Extended Abstract).- An Algebra for an Entity-Relationship Model and Its Application to Graphical Query Processing.- Structures and Performance of Physical Database Models.- Record-to-Area Mapping in the CODASYL Environment.- An Optimal Trie Construction Algorithm for Partial-Match Queries.- FOPES: File Organization Performance Estimation System.- Empirical Comparison of Associative File Structures.- Hybrid Sorting Techniques in Grid Structures.- CAD/VLSI Databases.- A Model and Storage Technique for Versions of VLSI CAD Objects.- Storage and Access Structures for Geometric Data Bases.- A Conceptual Basis for Graphics-Based Data Management (Extended Abstract).- Semantic Data Organization on a Generalized Data Management System.- Frequency Separation Analysis for Object Oriented Databases.- Query Processing and Physical Structures for Relational Databases.- Index Selection in Relational Databases.- A Physical Structure for Efficient Processing of Relational Queries.- A Hash Join Technique for Relational Database Systems.- Data Organization Method for the Parallel Execution of Relational Operations.- Implementation of Inferential Relational Database System.- Database Theory.- Towards a Basic Relational NF2 Algebra Processor.- Two Classes of Easily Tested Integrity Constraints: Complacent and FD-complacent Integrity Constraints.- Semantic Constraints of Network Model (Extended Abstract).- Join-Decomposition of MVD-Constraints Using the Characterization by “Bases” -An Introductive Study-.- Database Research and Development in the Pacific Area Countries.- Database Research and Development in Taiwan.- Database Research and Development in Korea.- Database Research and Development in Australia.- Database Research and Development in Japan: Its Past, Present and Future.- Database Research and Development in China.- Database Research and Development in Singapore.- Author index.