Logical incompleteness of A-algebra for base deletes
1. Given a relation b that is a subset of relation a and it is desired to delete (so to speak) the tuples in relation b from relation a and those tuples are chosen by the expression 'a join b', this is an informal logical argument for representing the resulting value of relation a:
"b is a subset of a and the negation of relation b logically implies that relation (a join b) is to be deleted from relation a".
2.Does anybody in this group understand that a slightly less informal version of the argument to express this is:
"(relation b is a subset of relation a) implies (the negated relation ( a join b) implies the relation a minus relation (a join b))"?
3. Does anybody understand this formal version where (-a&-b)) is the relevant conclusion:
(b>a) > ((a&-(a&b)) > (-a&-b)) ?
4. Does anybody who can read a truth table understand that the formal argument in question 3 is not logically valid?
5. Does anybody understand that this argument is logically valid:
(b=a) > ((a&-(a&b)) > (-a&-b)) ?
6. Now does anybody at all understand why Codd defined natural join differently than Appendix A?
For those who were able to answer yes to the earlier questions, here are more:
7. Who understands that the question 5 argument applies Codd's natural join condition which he expressed in terms of projections ?
It is equivalent to:
((b>a) & (a>b)) > (c=a&b) > ((c&-(c&b)) > (-a&-b)),
as in "every a-tuple in 'a join b' implies a b-tuple in 'a join b' and vice-versa"
8. Does anybody remember that Codd assumed "Thus the class of qualification expressions ... just have the descriptive power of the class of well-formed formulas of an applied predicate calculus. It is well known that to preserve this descriptive power ... (in whatever syntax is chosen) ... just those in prenex normal form are adequate" ?
9. Does anybody understand that question 8 doesn't require predicate calculus syntax in a dbms user language?
10. Does anybody understand how to associate Codd's join condition with the universal quantification in the Wikipedia Subset article?
11. Now, continuing to use Codd's natural join definition, this argument is logically valid:
(b=a) > (c=a&b) > ((c&-(c&b)) > (-a&-b)).
(Note that like the argument in question 5, its truth table is a tautology.)
Can anybody see where it could be usefully applied?
12. (bonus question) Has anybody noticed the possible corollary to Codd's join condition in McGoveran's update chapter ignoring the fact that he has a data design policy in mind that is beyond Codd's (page 14 as I recall)?
To calculate the score divide the number of yes or 'me' answers by 11 and take the percent. It's possible for the seriously interested to score more than 100%.
Quote from p c on October 26, 2019, 10:00 pm1. Given a relation b that is a subset of relation a and it is desired to delete (so to speak) the tuples in relation b from relation a and those tuples are chosen by the expression 'a join b', this is an informal logical argument for representing the resulting value of relation a:
If relation value b is a subset of relation value a, they must have the same heading.
"b is a subset of a and the negation of relation b logically implies that relation (a join b) is to be deleted from relation a".
then (a join b) = b. Why are you bothering to mention the join?
2.Does anybody in this group understand that a slightly less informal version of the argument to express this is:
"(relation b is a subset of relation a) implies (the negated relation ( a join b) implies the relation a minus relation (a join b))"?
What do you mean by "negated relation"? Do you mean Appendix A's <NOT> (a join b)? That's domain dependent, so already you're in deep water. Appendix A is at pains to point out that although <NOT> is domain dependent, it can only be invoked as a translation from Tutorial D MINUS (or more generally NOT MATCHING); i.e. in the same contexts as Codd's 1972 AND NOT -- which is how Codd avoids domain dependence.
3. Does anybody understand this formal version where (-a&-b)) is the relevant conclusion:
(b>a) > ((a&-(a&b)) > (-a&-b)) ?
I don't understand. What does the notation (a>b) mean? Do you know you can use latex format here? Do you know the editor here has a menu Insert| Special character that includes all the usual FOPL symbols. If it's FOPL you're trying to write (I'm not sure), use proper symbols, it's not hard. In question 1, 2 you've used a, b to denote relation values. If you're now writing FOPL, suggest you use distinct symbols. (I'm guessing a, b denote propositions. What propositions?)
Do you mean (b→a) → ((a ∧ ¬(a ∧ b)) → (¬a ∧ ¬b)) ?
Addit: (making some big guesses) if a, b here denote the propositions whose extension is the relation values of a, b respectively in questions 1, 2, then relation value b ⊆ a is the extension of propositional (a → b). Then why does your formula (if I've guessed that correctly) start (b→a) → ...?
4. Does anybody who can read a truth table understand that the formal argument in question 3 is not logically valid?
IIRC you withdrew the truth table you presented at length (twice) on another thread. Yes I can read a truth table. Since I don't understand question 3, I've no idea what you're saying.
5. Does anybody understand that this argument is logically valid:
(b=a) > ((a&-(a&b)) > (-a&-b)) ?
What does notation (a > b) mean? If a, b denote propositions, what does notation (a=b) mean? Is that logical equivalence? Use (a≡b) or (a↔b).
6. Now does anybody at all understand why Codd defined natural join differently than Appendix A?
Codd 1972 uses the 'domain-ordered' format throughout. Appendix A uses the 'named perspective' throughout. Both those terms are explained in the Alice book.
If you adjust Codd's 1972 definition to use 'named perspective' that comes out the same as Appendix A.
Quote from p c on October 27, 2019, 5:22 amFor those who were able to answer yes to the earlier questions, here are more:
I couldn't. I'll answer some bits here that seem independent of the earlier questions.
7. Who understands that the question 5 argument applies Codd's natural join condition which he expressed in terms of projections ?
It is equivalent to:
((b>a) & (a>b)) > (c=a&b) > ((c&-(c&b)) > (-a&-b)),
as in "every a-tuple in 'a join b' implies a b-tuple in 'a join b' and vice-versa"
8. Does anybody remember that Codd assumed "Thus the class of qualification expressions ... just have the descriptive power of the class of well-formed formulas of an applied predicate calculus. It is well known that to preserve this descriptive power ... (in whatever syntax is chosen) ... just those in prenex normal form are adequate" ?
Codd failed to show that in his 1972 paper. He merely asserts it wrt his 'ALPHA'. His "assumed" it does not make it true. Since there is no formal specification of ALPHA in the 1972 paper; and no implementation, those claims from him remain unproven. Furthermore I'm pretty sure they're false: in his translation of the division operator to use existential quant, it's crucial the existentials be nested inside negations. That isn't PNF.
9. Does anybody understand that question 8 doesn't require predicate calculus syntax in a dbms user language?
I've not seen anybody claiming that a dbms user language should support predicate calculus syntax. I'm not aware of any popular user-facing dbms languages that use predicate calculus syntax. (There are some more academic languages that do, such as the Domain Relational Calculus.)
10. Does anybody understand how to associate Codd's join condition with the universal quantification in the Wikipedia article?
Which wikipedia article? Do you know you can put URL links in postings using this editor (Insert | link menu)? Do you mean the article on Relational Algebra? There's various formulas in there using universal quantification -- for example in this section on division or this on transitive closure.
11. Now, continuing to use Codd's natural join definition, this argument is logically valid:
(b=a) > (c=a&b) > ((c&-(c&b)) > (-a&-b)).
(Note that like the argument in question 5, its truth table is a tautology.)
Can anybody see where it could be usefully applied?
12. (bonus question) Has anybody noticed the possible corollary to Codd's join condition in Mcgoveran's update chapter ignoring the fact that he has a data design policy in mind that is beyond Codd's (page 14 as I recall)?
McGoveran's writings are incoherent. That DRAFT chapter on updating through views is several years old, with no sign of any revision/improvement. We have tried at length (on the old forum) to make sense of it. Though your writings are several orders of magnitude less coherent.
To calculate the score divide the number of yes or 'me' answers by 11 and take the percent. It's possible for the seriously interested to score more than 100%.
Thanks for noticing that typo, at least. It should have said Wikipedia Subset article. The point that says "When quantified, A ⊆ B is represented as ∀x(x ∈ A → x ∈ B)" expresses Codd's projection-based join condition in another way.
Keeping in mind the multiple simultaneous interpretations a strictly logical argument allows might help, as would reading the instructions for the Logic++ generator I posted. I trust mechanical evaluation much more than my own typing especially when the table form becomes very very long, not to mention when it comes to comparing two systems and far beyond that. Note that there is not one particular syntax a formal argument must use.
Note also that I'm only pointing out how Appendix A is logically incomplete because certain algebra expressions are not provable by the algebra. This has drastic consequences beyond the mundane applications discussed here, as we are told that it's been proved that predicate logic is a formal system that is complete and consistent, unlike arithmetic for example which is why when Codd said "based on predicate calculus" he meant operations that could be equated with predicate calculus, not necessarily applied by it. That was Codd's obvious reason for distinguishing data from host language.
Regarding "not aware of any ...", the only intended awareness is not about any use other than Appendix A and its application used by a logical argument.
Quote from p c on October 26, 2019, 10:00 pm1. Given a relation b that is a subset of relation a and it is desired to delete (so to speak) the tuples in relation b from relation a and those tuples are chosen by the expression 'a join b', this is an informal logical argument for representing the resulting value of relation a:
"If relation value b is a subset of relation value a, they must have the same heading."
Your examples are showing some of the pitfalls when comparing informal arguments to formal arguments.
Since formal propositional logic doesn't have headings they must be simulated in a formal argument. Some simplications can avoid complicared simulations that are not part of the argument's purpose.
The survey could have asked even more fundamental questions but that would be unmanageable. For example in this group I'd expect it would be fundamental that in TTM terms bound R{a,b,c} logically implies bound R{a} but <NOT>R{a,b,c} doesn't necessarily imply <NOT>R{a}. But in a formal argument those two relations must be distinguished somehow because prop logic doesn't have projections.
It's the same reason that in a formal argument (a&b) which is a join b when a and b are relations, is a wff that doesn't have the same logical meaning as a or b even when a and b are equal. It is only the logical conclusion, if the argument has logically valid conclusion that indicates what the possible TTM results are. A logical evaluator has to be told that when (a implies b) with a context that is also given in formal terms by an argument (not b) is allowed to imply (not a).
It is a very fundamental logical error to assume a formal argument that mentions the wff (a&b) is equivalent to an argument that mentions wff (a) instead, even if a TTM implementation would. All the artifacts that are external to the argument must be defined by the argument in logical terms. Further, a logically valid argument doesn't doesn't assume any external truth, it only makes a conditionally valid or invalid conclusion to show whether in all possible cases, IF premises are true, then the conclusion must or must not follow. For the formal arguments given, only the logical connectives negation, conjunction and implication were needed.
The survey is about an isolated aspect of Appendix A that happens to have far-reaching consequences, using the most minimal kind of language. It would be much more efficient if people could limit their responses to 'yes' or 'no' for the rather narrow specific questions given. No logical need to diverge.
Quote from p c on October 27, 2019, 6:01 pmctober 27, 2019, 12:47 pm
The survey is about an isolated aspect of Appendix A that happens to have far-reaching consequences, using the most minimal kind of language. It would be much more efficient if people could limit their responses to 'yes' or 'no' for the rather narrow specific questions given. No logical need to diverge.
Oh dear you've lapsed into incoherence again. And you've failed to take action on any of the suggestions I made for explaining yourself in forms that would be easier to understand.
I gave neither 'yes' nor 'no' responses for reasons I explained: I didn't understand the questions. Seems some of the questions had errors of logic in them -- which happens all the time with your posts. Your latest few posts abound in logic errors. I simply can't be bothered to point them out.
I still have no idea what you think is wrong with Appendix A. I think the A algebra is hugely successful for the purposes Appendix A sets itself. And I think it is relationally complete up to Codd 1972's definition of that term, after adjusting for A using the 'named perspective'.
OTOH Codd's 'relationally complete' is problematic, and I think unsatisfactory as a measure of expressive power for a query language/algebra/calculus.
"...What do you mean by "negated relation"? Do you mean Appendix A's <NOT> (a join b)? That's domain dependent, so already you're in deep water. Appendix A is at pains to point out that although <NOT> is domain dependent, it can only be invoked as a translation from Tutorial D MINUS (or more generally NOT MATCHING); i.e. in the same contexts as Codd's 1972 AND NOT -- which is how Codd avoids domain dependence..."
The questions are about the A-algebra part of a data language, not D which includes a host language. Appendix A doesn't mention domain dependence nor domains except indirectly in the sense of attributes. No matter which you pick, the only material issue for this topic issue is union compatibility which both Codd 1970 and Appendix A acknowledge.
You can always make the scope bigger and imagine implementation details to complicate the problem. But for this topic, it is obviously enough to assume one domain, say the domain of character strings.
Regarding Appendix A complement, there seems to be an almost ubiquitous desire among database workers to consruct or materialize it, which a dbms data language has no need to do.
The data language needs to decide if propositions are true or not. A relational data language indicates that decision by returning relation values to the host language. If P is a set of propositions considered true and p is the set for which it is desired to find out database truth, the data language needs to return a relation indicating that. The most obvious relation that can indicate that is one that indicates a contradiction in the form of a relational value, namely (p minus p), an empty relation, which is the same relation value as the contradiction (P-P).
The contradiction happens to also be a relative complement. When a logical argument evaluation encounters a wff (-P) all it means is that (-P) contradicts wff (P), which is the same thing that relational complement (P-P) means to a data language.
Further, you can't logically replace (-p) with (p&-p) because their bi-implication is not logically valid. Same goes for (-p) and (p-p).