The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

Questions about some relational operator definitions and comments about the DIVIDEBY operation

For a database to be logically complete the dbms has to apply deductive logic, ie. nothing can be concluded except what is logically implied by the base relations/premises, otherwise it is logically incomplete, second-order etc.  Users can infer whatever they want.

To be more specific, is it not true that if:

  • U is the set of all the facts asserted in the database
  • Q is the set of all query results that can be obtained by applying the RA to U without asserting any new facts (no EXTENDS)
  • U implies Q.
Andl - A New Database Language - andl.org
Quote from dandl on February 18, 2020, 2:42 am

For a database to be logically complete the dbms has to apply deductive logic, ie. nothing can be concluded except what is logically implied by the base relations/premises, otherwise it is logically incomplete, second-order etc.  Users can infer whatever they want.

To be more specific, is it not true that if:

  • U is the set of all the facts asserted in the database
  • Q is the set of all query results that can be obtained by applying the RA to U without asserting any new facts (no EXTENDS)
  • U implies Q.

And whatever is in Q but not in U is inferred ***by the DBMS*** by the very fact of computing the RA query result.

That a user might infer "Z is black" because the system says that "Z is white and this was asserted by X" is totally, TOTALLY, irrelevant.  That kind of inference is an application of a logic (and a system of axioms) that the DBMS is (and righteously should be) ***TOTALLY UNAWARE OF***.  So why should that be relevant to database/DBMS technology ?

Not at all. Either (a) we're in the realm of maths logic, in which the logical operator 'implies' is well-defined, and there is no corresponding 'infers' operator. Or we're (b) in the realm of ordinary English language and human mental capabilities and the DBMS does not have the capacity to 'imply' or 'infer' anything at all.

If users accept the premise that the database contains 'facts' as per U, and they accept the logic of 'U implies Q' then they should infer that each of the members of Q is true.

 

Andl - A New Database Language - andl.org
Quote from dandl on February 18, 2020, 2:42 am

For a database to be logically complete the dbms has to apply deductive logic, ie. nothing can be concluded except what is logically implied by the base relations/premises, otherwise it is logically incomplete, second-order etc.  Users can infer whatever they want.

To be more specific, is it not true that if:

  • U is the set of all the facts asserted in the database
  • Q is the set of all query results that can be obtained by applying the RA to U without asserting any new facts (no EXTENDS)
  • U implies Q.

If "implies" means material implication the answer is no.

Suppose A is a subset of B so that anything that has a property of A also has a property of B. Express that as 'A Implies B, aka (A -> B). Then assume nothing has a property of A, as in the expression (Not A).

When a query uses those expressions as premises, it's not a valid material implication to conclude Not (A And B), meaning nothing has both properties (as a four line truth table will show). It should be obvious that this is because it's still possible for something that has a property of B to have a property of A.

Codd avoided this problem by defining natural join in terms of A and B equivalence. Appendix A preserves the problem by defining natural join aka its 'conjoin' in terms of logical conjunction.

The A-algebra guarantees logically incomplete databases which requires users to make up inferences that are not premised, in this case "nothing that has a property of B has a property of A", so Not ( A Join B ) appears to be a valid conclusion of a query that makes the argument but is a valid material implication only in the user's mind's eye, not in the database as expressed by A-algebra. 

(Not to mention other havoc for designers and app coders.)

Nothing to see here.

Quote from p c on February 20, 2020, 3:28 am
Quote from dandl on February 18, 2020, 2:42 am

For a database to be logically complete the dbms has to apply deductive logic, ie. nothing can be concluded except what is logically implied by the base relations/premises, otherwise it is logically incomplete, second-order etc.  Users can infer whatever they want.

To be more specific, is it not true that if:

  • U is the set of all the facts asserted in the database
  • Q is the set of all query results that can be obtained by applying the RA to U without asserting any new facts (no EXTENDS)
  • U implies Q.

If "implies" means material implication the answer is no.

I think it does not. Here 'implies' is intended to mean simply if P then Q. I think we cannot freely perform substitutions involving not because the database does not explicitly encode negated propositions.

Suppose A is a subset of B so that anything that has a property of A also has a property of B. Express that as 'A Implies B, aka (A -> B). Then assume nothing has a property of A, as in the expression (Not A).

Sorry, but I don't follow. The database encodes facts expressed as relations comprising tuples with attributes. I'm not familiar with the use of 'property' in this context.

When a query uses those expressions as premises, it's not a valid material implication to conclude Not (A And B), meaning nothing has both properties (as a four line truth table will show). It should be obvious that this is because it's still possible for something that has a property of B to have a property of A.

Codd avoided this problem by defining natural join in terms of A and B equivalence. Appendix A preserves the problem by defining natural join aka its 'conjoin' in terms of logical conjunction.

I don't see that. Can you provide a reference or a quote?

The A-algebra guarantees logically incomplete databases which requires users to make up inferences that are not premised, in this case "nothing that has a property of B has a property of A", so Not ( A Join B ) appears to be a valid conclusion of a query that makes the argument but is a valid material implication only in the user's mind's eye, not in the database as expressed by A-algebra. 

(Not to mention other havoc for designers and app coders.)

 

Andl - A New Database Language - andl.org
Quote from dandl on February 22, 2020, 12:07 am
Quote from p c on February 20, 2020, 3:28 am
Quote from dandl on February 18, 2020, 2:42 am

For a database to be logically complete the dbms has to apply deductive logic, ie. nothing can be concluded except what is logically implied by the base relations/premises, otherwise it is logically incomplete, second-order etc.  Users can infer whatever they want.

To be more specific, is it not true that if:

  • U is the set of all the facts asserted in the database
  • Q is the set of all query results that can be obtained by applying the RA to U without asserting any new facts (no EXTENDS)
  • U implies Q.

If "implies" means material implication the answer is no.

I think it does not. Here 'implies' is intended to mean simply if P then Q. I think we cannot freely perform substitutions involving not because the database does not explicitly encode negated propositions.

Suppose A is a subset of B so that anything that has a property of A also has a property of B. Express that as 'A Implies B, aka (A -> B). Then assume nothing has a property of A, as in the expression (Not A).

Sorry, but I don't follow. The database encodes facts expressed as relations comprising tuples with attributes. I'm not familiar with the use of 'property' in this context.

When a query uses those expressions as premises, it's not a valid material implication to conclude Not (A And B), meaning nothing has both properties (as a four line truth table will show). It should be obvious that this is because it's still possible for something that has a property of B to have a property of A.

Codd avoided this problem by defining natural join in terms of A and B equivalence. Appendix A preserves the problem by defining natural join aka its 'conjoin' in terms of logical conjunction.

I don't see that. Can you provide a reference or a quote?

The A-algebra guarantees logically incomplete databases which requires users to make up inferences that are not premised, in this case "nothing that has a property of B has a property of A", so Not ( A Join B ) appears to be a valid conclusion of a query that makes the argument but is a valid material implication only in the user's mind's eye, not in the database as expressed by A-algebra. 

(Not to mention other havoc for designers and app coders.)

 

No matter whether you choose Codd's domains or TTM's tuple types whatever the  encoding, for a false proposition it is the same as for a true proposition. Choice of encoding is a coder's decision as long as the choice is logically consistent.

 

From the first post on,  this topic has been about nothing but properties, for example the set of suppliers that have the property of being suppliers with nothing about what they supply being stated and the set of suppliers where it is àlso stated that they have the property of supplying parts. 

 

Let p represent the first set and q represent the second set. In other words, p =S{S#}, q=SP{S#}.  in the sample database, because of a foreign key,, the appendix A conjoon of p and q implies that q implies p but  it is not implied that p implies q. S{S#) and SP{S#) are not guaranteed to be equivalent.

 

But Codd's natural join definition guarantees a mutual equivalence because it defines the operands of a join differently, on equality of common attribute values, so that p and q are both equal to (S Join SP) {S#}, so the mutual implication p ⇔ q is always true, a  requirement for logical validity and therefore database logical completeness, the latter meaning that the database implies nothing the dbms can't prove.

 

If you don't think that appendix A natural join is based on conjunction look for 'and' in the formal definition. If you want, you could  insist on using common sets of attributes instead of common attributes bestowing equivalent properties.

Can someone provide a definition of relational division (or a reference to such a definition); such that. the definition that follow consists of (a) a formal specification of the rules, if any, that apply to the operands of the operator in question, (b) a formal specification of the heading of the result of that operator, and (c) a formal specification of the body of that result, followed by (d) an informal discussion of the formal specifications.

Unlike other relational operators, the relational division is not formally defined in DTATRM,

No matter whether you choose Codd's domains or TTM's tuple types whatever the  encoding, for a false proposition it is the same as for a true proposition. Choice of encoding is a coder's decision as long as the choice is logically consistent.

No idea where this fits in.

From the first post on,  this topic has been about nothing but properties, for example the set of suppliers that have the property of being suppliers with nothing about what they supply being stated and the set of suppliers where it is àlso stated that they have the property of supplying parts. 

That's as may be, but if you switch terminology you leave me confused. There is nothing I recall in TTM or elsewhere about properties, or about 'suppliers having the property of being suppliers'. All I know is the headings of the relations, the predicates that accompany them and the facts asserted as tuples in the database. There is no independent assertion that a supplier is a supplier, just the predicate that links together 4 named attributes. If you want to call them properties I don't mind, but you need to define your terms carefully.

Let p represent the first set and q represent the second set. In other words, p =S{S#}, q=SP{S#}.  in the sample database, because of a foreign key,, the appendix A conjoon of p and q implies that q implies p but  it is not implied that p implies q. S{S#) and SP{S#) are not guaranteed to be equivalent.

'conjoon'? And what does it mean to imply at a second remove: 'it is not implied that p implies'?

Yes there is an implication (English sense) that S1 in S is the same entity as S1 in SP. This is not explicitly stated, but it is guaranteed in TTM by the use of the type system. In Codd that would be the same domain. Is that what you mean?

But Codd's natural join definition guarantees a mutual equivalence because it defines the operands of a join differently, on equality of common attribute values, so that p and q are both equal to (S Join SP) {S#}, so the mutual implication p ⇔ q is always true, a  requirement for logical validity and therefore database logical completeness, the latter meaning that the database implies nothing the dbms can't prove.

OK, I guess.

If you don't think that appendix A natural join is based on conjunction look for 'and' in the formal definition. If you want, you could  insist on using common sets of attributes instead of common attributes bestowing equivalent properties.

App-A talks about free variables, but I don't see anything explicit distinguishing it from Codd or TTM.

Andl - A New Database Language - andl.org
Quote from Greg Klisch on February 24, 2020, 12:37 am

Can someone provide a definition of relational division (or a reference to such a definition); such that. the definition that follow consists of (a) a formal specification of the rules, if any, that apply to the operands of the operator in question, (b) a formal specification of the heading of the result of that operator, and (c) a formal specification of the body of that result, followed by (d) an informal discussion of the formal specifications.

Unlike other relational operators, the relational division is not formally defined in DTATRM,

Codd 1972 provides a formal definition, both in isolation and in terms of other operations.

DTATRM and DBE provide operational definitions, in terms of equivalent code using other operations. To me this says it all.

r1 DIVIDEBY r2 ::= r1 { X } MINUS ( ( r1 { X } JOIN r2 ) MINUS r1 ) { X }
Andl - A New Database Language - andl.org