Foundations Of Databases – Serge Abiteboul

Thus it provides an adequate top-down technique for obtaining the facts in the answer to a datalog program. To prove that a fact is in the answer, one must search for a refutation of the corresponding goal. Clearly, there are many refutations possible. There are two sources of nondeterminism in searching for a refutation: (1) the choice of the selected atom, and (2) the choice of the clause to unify with the atom. Now let us assume that we have fixed some golden rule, called a selection rule, for choosing which atom to select at each step in a refutation.

A priori, such a rule may be very simple (e.g., as in Prolog, always take the leftmost atom) or in contrast very involved, taking into account the entire history of the refutation. Once an atom has been selected, we can systematically search for all possible unifying rules. Such a search can be represented in an SLD tree. For instance, consider the tree of Fig. 12.6 for the program in Example 12.4.2. The selected atoms are represented with boxes. Edges denote unifications used. Given S(1, x), only one rule can be used.

Given T (1, x2), two rules are applicable that account for the two descendants of vertex T (1, x2). The first number in edge labels denotes the rule that is used and the remaining part denotes the substitution. An SLD tree is a representation of all the derivations obtained with a fixed selection rule for atoms. 12.4 Proof-Theoretic Approach There are several important observations to be made about this particular SLD tree: (i) It is successful because one branch yields .

(ii) It has an infinite subtree that corresponds to an infinite sequence of applications of rule (2) of Example 12.4.2. (iii) It has a blocking branch. We can now explain (to a certain extent) the acronym SLD. SLD stands for selection rule-driven linear resolution for definite clauses. Rule-driven refers to the rule used for selecting the atom. An important fact is that the success or failure of an SLD tree does not depend on the rule for selecting atoms.

This explains why the definition of an SLD tree does not specify the selection rule.

Sponsoring Editor: Lynne Doran Cote Associate Editor: Katherine Harutunian Senior Production Editor: Helen M. Wythe Cover Designer: Eileen R. Hoff Manufacturing Coordinator: Evelyn M. Beaton Cover Illustrator: Toni St. Regis Production: Superscript Editorial Production Services (Ann Knight) Composition: Windfall Software (Paul C. Anagnostopoulos, Marsha Finley, Jacqueline Scarlott), using ZzTEX Copy Editor: Patricia M. Daly Proofreader: Cecilia Thurlow The procedures and applications presented in this book have been included for their instructional value.

They have been tested with care but are not guaranteed for any purpose. The publisher does not offer any warranties or representations, nor does it accept any liabilities with respect to the programs and applications. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Library of Congress Cataloging-in-Publication Data Abiteboul, S. (Serge) Foundations of databases / Serge Abiteboul. Richard Hull, Victor Vianu. p. cm. Includes bibliographical references and index. ISBN 0-201-53771-0 1. Database management. I. Hull, Richard, 1953–. II. Vianu, Victor. III. Title. QA76.9.D3A26 1995 005.74’01—dc20 94-19295 CIP Copyright © 1995 by Addison-Wesley 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 prior written permission of the publisher.

Printed in the United States of America. 1 2 3 4 5 6 7 8 9 10–MA–98 97 96 95 94 Alice: To whom are you going to dedicate the book? Vittorio: How about our parents? Riccardo: Yes, and our spouses . . . Sergio: . . . and the kids . . . Alice: Hold it, that’s a dozen people already! Don’t you guys have some common ancestor?!

All: You’re right! We also dedicate it to Seymour Ginsburg. Preface D atabase theory is a relative newcomer to the field of computer science. Early data man- agement systems were based on techniques from several classical areas of computer science, ranging from hardware and operating systems to data structures and programming languages.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 0d1c3fb2d9206253
• File Extension: .pdf
• File Size: 2,980,408 bytes (2.842 MB)
• Title: –
• Author: Unknown
• ISBN: 0201537710, 9897969594
• Pages: 705
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 1458.47 minutes
• Total Words: 291,695
• Total Characters: 1,682,820
• Average Words per Page: 413.75
• Average Characters per Page: 2386.98

Most Frequent Words

query (1441), set (1072), queries (1036), database (1023), exercise (892), relation (867), datalog (798), let (753), example (698), relational (657), one (656), schema (623), program (619), instance (617), data (564), languages (561), model (551), semantics (551), dependencies (543), consider (535), see (532), rule (510), calculus (496), used (488), algebra (485), using (477), input (465), two (458), also (443), following (440), form (430), databases (425), language (419), chapter (417), rules (405), now (402), given (399), fixpoint (393), logic (387), show (384), equivalent (381), theorem (380), relations (377), variables (372), use (370), finite (362), proof (362), first (358), tuple (354), tuples (351), result (346), prove (343), pages (323), conjunctive (321), defined (316), systems (311), tableau (307), dependency (298), value (297), fd’s (295), suppose (295), complexity (294), values (293), programs (291), new (290), case (290), thus (288), proc (279), between (277), instances (273), acm (273), constants (272), information (264), class (261), algorithm (258), theory (256), name (252), complex (248), implication (247), sort (245), calc (244), follows (243), negation (241), time (238), shown (236), join (234), domain (230), answer (229), called (228), view (228), definition (228), based (227), section (225), approach (221), programming (218), problem (218), formula (217), evaluation (213), sequence (213), particular (212).

PDF Download