Published online by Cambridge University Press: 22 March 2010
As truth is gathered, I rearrange
inside out
outside in
Perpetual change.
—Yes, Perpetual ChangeThe semantics presented in Chapter 3 describe the effect of an update on the models of a theory; the semantics give no hints whatsoever on how to translate that effect into changes in the relational theory. An algorithm for performing updates cannot proceed by generating models from the theory and updating them directly; this is because the number of standard models may be exponential in the size of the theory, and it may be very difficult to find even one model, as that is equivalent to testing the satisfiability of the theory.
In the sections of this chapter, we consider algorithmic means of accomplishing successively more complicated updates, beginning with updates under the standard semantics, without nulls and selection clauses, operating under an open-world assumption, in Section 4.1. Section 4.2 extends this approach to updates with nulls, and Section 4.3 shows how to process selection clauses correctly. Section 4.4 shows how to enforce the closed-world assumption.
Section 4.5 shows that these algorithms are correct in the sense that the alternative worlds produced under the algorithms are the same as those produced by updating each alternative world individually.
Section 4.6 discusses the computational complexity of the algorithms. For relational theories and updates without nulls, the algorithms have the same asymptotic cost as for an ordinary complete-information database update, but may increase the size of the relational theory. For updates involving nulls, the increase in size will be severe if many data atoms in the theory unify with those in the update.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.