E-Book Content
I RELATIONAL DATABASE THEORY U m m U U U U m m m m PAOLO ATZENI UNIVERSITY OF ROME VALERIA De ANTONELLIS OF UNIVERSITY MILAN THE BENJAMIN/CUMMINGS PUBLISHING COMPANY, INC. REDWOOD CITY, CALIFORNIA READING, MASSACHUSETTS WOKINGHAM, U.K. SINGAPORE - * MENLO PARK, CALIFORNIA NEW YORK - AMSTERDAM o DON MILLS, ONTARIO * * TOKYO * MADRID BONN - - SYDNEY SAN JUAN m Sponsoring Editor: Dan Joraanstad Production Coordinator: Alyssa Wolf Cover Designer: Yvo Riezebos Copyeditor: Nick Murray Proofreader: Angela Santos Sr 36O 4 uB Dortmund Copyright © 1993 by The Benjamin/Cummings Publishing Company, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. Printed simultaneously in Canada. Library of Congress Cataloging-in-Publication Data Atzeni, Paolo, 1957Relational database theory / Paolo Atzeni, Valeria De Antonellis. p. cm. Includes bibliographical references and index. ISBN 0-8053-0249-2 1. Relational data bases. I. De Antonellis, Valeria, 1951II. Title. QA76.9.D3A925 1992 005.75'6-dc20 92-30507 CIP ISBN 0-8053-0249-2 1 2 3 4 5 6 7 8 9 10-HA-97 96 95 94 93 92 The Benjamin/Cummings Publishing Company, Inc. 390 Bridge Parkway Redwood City, California 94065 Preface This book presents a systematic treatment of the formal theory of the relational model of data, which is the foundation of current database management systems. It can be used as a text for a graduate course in database theory, or as an additional reference for an undergraduate course on data management. It will also be useful to researchers and professionals as a comprehensive introduction to the technical literature and its applications. Relational database theory has been a popular subject of research for more than twenty years, since E. F. Codd published his seminal papers in the early 1970s. The subject is important for various reasons. First, results obtained in relational theory, for instance those on normal forms, are being used by practitioners in database design. Second, while many research problems have been solved, many remain open. New avenues continue to be explored, some of which have connections to current topics of investigation in other fields, such as logic programming and object-orientation. Third, the techniques used in relational database theory and explored in this book will serve any student in theoretical computer science well, as these tools can be usefully applied to various divisions of computer science. This book presents a comprehensive treatment of the most important results in relational database theory. It is intended to serve three main purposes: 1. To present established research results in a clear way, comprehensible to both theoreticians and practitioners. 2. To introduce the reader to the relevant literature, simplifying the task by unifying notation and terminology, pointing at the most recent trends, and indicating open problems. 3. To help the reader develop skills in the proof of theorems by employing various techniques and methodologies. iv Preface Consequently, the theoretical development of the subject always involves precise notation and rigorous proofs. At the same time, theory is never discussed merely for its own sake; motivation is always present, along with practical applications of the results. Many examples and exercis