The Third Manifesto ForumDatabases: Database TheoryRelational Theory and the Russell …

Please or Register to create posts and topics.

Relational Theory and the Russell Paradox

#1 · December 11, 2019, 7:56 pm

Quote from Erwin on December 11, 2019, 7:56 pm
For quite some time, I've been trying to "do a Russell", that is, come up with some sort of database design that had a Russell Paradox smell to it. I always prefer the barber variant, and here it is :

/* three relvars : persons who exist, persons who shave themselves, and persons who don't shave themselves */
VAR PERS : {P | P lives in the Russell World}
VAR PSN : {P | P shaves self not} /* with apologies for the hopeless english */
VAR PSO : {P | shaves self}
/* Constraints needed to keep these three vars consistent */
PERS = PSN UNION PSO /* C1 : all existing persons either shave themselves or don't*/
PSN INTERSECT PSO = FI   /* C2 : nobody both does and doesn't shave himself */

/* variable to denote who is the barber */
VAR BAR : {P | P is the Barber}
/* constraints concerning the barber */
BAR MINUS PERS = FI   /* C3 : Barber must be a citizen of the Russell World */
/* for the sake of the example, imagine here too a constraint "only one barber" */

/* And now for the shaving */
VAR SHAVES ::= {(B,P) | B IN BAR & P IN PSN} UNION {(P,P) | P IN PSO} /* Barber shaves people who don't shave themselves and the others shave themselves */
/* And now for the constraints related to the shaving */
BAR JOIN PSN = BAR JOIN SHAVES   /* C4 : all persons who don't shave themselves are shaved by the barber */
PSO = (SHAVES WHERE <shaver = shaved>) {<shaved>}   /* C5 : all persons who shave themselves, eurhm, shave themselves */

Okay. All these relvars & constraints are perfectly doable in TTM so let's consider them declared and test whether the empty database satisfies them.

C1 : PERS = PSN UNION PSO : FI = FI UNION FI   /*satisfied */
C2 : PSN INTERSECT PSO = FI : FI INTERSECT FI = FI   /* satisfied */
C3 : BAR MINUS PERS = FI : FI MINUS FI = FI   /* satisfied */
/* only one barber */ : under the "at most one" interpretation : satisfied - see later for the "exactly one" interpretation.
C4 : BAR JOIN PSN = BAR JOIN SHAVES : (FI JOIN FI) = (FI JOIN FI) : FI = FI   /* satisfied */
C5 : PSO = (SHAVES WHERE <shaver = shaved>) {<shaved>} : FI = (FI WHERE ...) {P} : FI =FI   /* satisfied */

All constraints satisfied, so we can declare this design and start with an empty database. Now let's add a citizen in this paradoxical universe.

Just adding the citizen is going to fail C1. We must let it be known whether that citizen shaves himself. Let's opt for 'yes' and "multiple-insert" him into both PERS and PSO.
C1 is now satisfied
C2 is still satisfied because PSN is still empty therefore its intersection with anything is too.
C3 is still satisfied because BAR is still empty therefore its difference with anything is too.
C4 is still satisfied because BAR is still empty therefore its join with anything is too.
C5 is still satisfied because the multi-insert made it so (the insert in PSO also caused an insert in SHAVES per second argument of the union).

So we can add persons who shave themselves, and somewhat curiously, there ***is*** a world that satisfies all these constraints : one that has no barber and where everyone shaves himself.

So now let's see what happens in this database if we try to add a barber. Just trying to add that person to BAR is going to fail C3. Barbers must also be persons in the citizenship. Therefore we must also add this person to PERS, and for the reasons already mentioned (constraint C1) we must therefore also declare whether this barber shaves himself or not.

Suppose we put this barber in PSN (doesn't shave himself). Then SHAVES is going to include the "tuple" (B,B) (per the left arg of the UNION that defines SHAVES). Then per C5, B should be included in PSO or else it (C5) will fail. And if C5 doesn't, then constraint C2 necessarily will.

Suppose we put this barber in PSO (does shave himself). Then SHAVES is going to include the "tuple" (B,B) (per the right arg of the UNION that defines SHAVES). Then per C4, B should be included in PSN or else it (C4) will fail. And if C4 doesn't, then constraint C2 necessarily will.

So it is impossible to introduce a barber (the very act that would render undecidable a certain proposition constraining this world) into this world without violating any declared constraint, and (what this post is actually about) *** a TTM system that supports enforcing all these constraints seems PERFECTLY capable of making that happen *** , i.e. it seems not all that impossible to use TTM-style relational technology to block out situations that account for the "undecidability" of certain propositions (and which lead certain people to want to restrain relational technology to some equivalent of logical first-order).

(Adding the constraint "there must be at least one barber" makes the empty database violate that constraint, making that constraint not even introducible, requiring a barber to first be introduced before that particular constraint can be made part of the system, but introducing a barber remains equally impossible for the reasons already given. The conclusion appears to remain the same.)

Meticulous inspection/review requested.

For quite some time, I've been trying to "do a Russell", that is, come up with some sort of database design that had a Russell Paradox smell to it. I always prefer the barber variant, and here it is :

/* three relvars : persons who exist, persons who shave themselves, and persons who don't shave themselves */
VAR PERS : {P | P lives in the Russell World}
VAR PSN : {P | P shaves self not} /* with apologies for the hopeless english */
VAR PSO : {P | shaves self}
/* Constraints needed to keep these three vars consistent */
PERS = PSN UNION PSO /* C1 : all existing persons either shave themselves or don't*/
PSN INTERSECT PSO = FI /* C2 : nobody both does and doesn't shave himself */

/* variable to denote who is the barber */
VAR BAR : {P | P is the Barber}
/* constraints concerning the barber */
BAR MINUS PERS = FI /* C3 : Barber must be a citizen of the Russell World */
/* for the sake of the example, imagine here too a constraint "only one barber" */

/* And now for the shaving */
VAR SHAVES ::= {(B,P) | B IN BAR & P IN PSN} UNION {(P,P) | P IN PSO} /* Barber shaves people who don't shave themselves and the others shave themselves */
/* And now for the constraints related to the shaving */
BAR JOIN PSN = BAR JOIN SHAVES /* C4 : all persons who don't shave themselves are shaved by the barber */
PSO = (SHAVES WHERE <shaver = shaved>) {<shaved>} /* C5 : all persons who shave themselves, eurhm, shave themselves */

Okay. All these relvars & constraints are perfectly doable in TTM so let's consider them declared and test whether the empty database satisfies them.

C1 : PERS = PSN UNION PSO : FI = FI UNION FI   /*satisfied */
C2 : PSN INTERSECT PSO = FI : FI INTERSECT FI = FI   /* satisfied */
C3 : BAR MINUS PERS = FI : FI MINUS FI = FI   /* satisfied */
/* only one barber */ : under the "at most one" interpretation : satisfied - see later for the "exactly one" interpretation.
C4 : BAR JOIN PSN = BAR JOIN SHAVES : (FI JOIN FI) = (FI JOIN FI) : FI = FI   /* satisfied */
C5 : PSO = (SHAVES WHERE <shaver = shaved>) {<shaved>} : FI = (FI WHERE ...) {P} : FI =FI   /* satisfied */

All constraints satisfied, so we can declare this design and start with an empty database. Now let's add a citizen in this paradoxical universe.

Just adding the citizen is going to fail C1. We must let it be known whether that citizen shaves himself. Let's opt for 'yes' and "multiple-insert" him into both PERS and PSO.
C1 is now satisfied
C2 is still satisfied because PSN is still empty therefore its intersection with anything is too.
C3 is still satisfied because BAR is still empty therefore its difference with anything is too.
C4 is still satisfied because BAR is still empty therefore its join with anything is too.
C5 is still satisfied because the multi-insert made it so (the insert in PSO also caused an insert in SHAVES per second argument of the union).

So we can add persons who shave themselves, and somewhat curiously, there ***is*** a world that satisfies all these constraints : one that has no barber and where everyone shaves himself.

So now let's see what happens in this database if we try to add a barber. Just trying to add that person to BAR is going to fail C3. Barbers must also be persons in the citizenship. Therefore we must also add this person to PERS, and for the reasons already mentioned (constraint C1) we must therefore also declare whether this barber shaves himself or not.

Suppose we put this barber in PSN (doesn't shave himself). Then SHAVES is going to include the "tuple" (B,B) (per the left arg of the UNION that defines SHAVES). Then per C5, B should be included in PSO or else it (C5) will fail. And if C5 doesn't, then constraint C2 necessarily will.

Suppose we put this barber in PSO (does shave himself). Then SHAVES is going to include the "tuple" (B,B) (per the right arg of the UNION that defines SHAVES). Then per C4, B should be included in PSN or else it (C4) will fail. And if C4 doesn't, then constraint C2 necessarily will.

So it is impossible to introduce a barber (the very act that would render undecidable a certain proposition constraining this world) into this world without violating any declared constraint, and (what this post is actually about) *** a TTM system that supports enforcing all these constraints seems PERFECTLY capable of making that happen *** , i.e. it seems not all that impossible to use TTM-style relational technology to block out situations that account for the "undecidability" of certain propositions (and which lead certain people to want to restrain relational technology to some equivalent of logical first-order).

(Adding the constraint "there must be at least one barber" makes the empty database violate that constraint, making that constraint not even introducible, requiring a barber to first be introduced before that particular constraint can be made part of the system, but introducing a barber remains equally impossible for the reasons already given. The conclusion appears to remain the same.)

Meticulous inspection/review requested.

#2 · December 12, 2019, 5:24 am

I don't see a logical problem here. A barber is a person in every way but that they can also cut others' hair. If we require there to be not more than 1 barber as you did then the barber must shave themself. If we allow more than 1 barber then a barber MAY shave themself but doesn't have to, as then the other barber can shave them. I don't see how introducing a barber would render something undecidable.

#3 · December 12, 2019, 11:14 am

<paper-reviewer mode>

Using FI for phi or Φ is quirky.

Your example certainly seems logically sound, but we already know the barber example demonstrates Russell's Paradox, so I'm not wholly clear what you're trying to show in terms of TTM given you're using a blend of ad-hoc syntax and FOPL semantics, rather than using TTM-based syntax/semantics like (for example) Tutorial D or some other D.

I find this concluding text...

"i.e. it seems not all that impossible to use TTM-style relational technology to block out situations that account for the 'undecidability' of certain propositions (and which lead certain people to want to restrain relational technology to some equivalent of logical first-order)"

...to be a bit oblique (e.g., "certain people"... who?) and indirect, where it should make a clear, pointed and direct conclusion.

</paper-reviewer mode>

For fun, I've been rewriting the barber example in Tutorial D but haven't finished yet. I'll post it here when done.

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org

#4 · December 12, 2019, 1:49 pm

Quote from Dave Voorhis on December 12, 2019, 1:49 pm
Here's my Tutorial D equivalent:
// All people in a Russell world...
VAR Person REAL RELATION {ID CHARACTER} KEY {ID};

// ...either shave themselves...
VAR ShavesSelf REAL RELATION {ID CHARACTER} KEY {ID};

// ...or do not shave themselves.
VAR ShavesSelfNot REAL RELATION {ID CHARACTER} KEY {ID};

// The barber
VAR Barber REAL RELATION {ID CHARACTER} KEY {};

// Who shaves who?
VAR Shaves VIRTUAL
   UNION {
     ((EXTEND ShavesSelf: {Shaver := ID, Shavee := ID}) {ALL BUT ID}),
     IF IS_EMPTY(Barber) THEN
       REL {Shaver CHAR, Shavee CHAR} {}
     ELSE
       ((EXTEND ShavesSelfNot: {Shaver := ID FROM TUPLE FROM Barber, Shavee := ID}) {ALL BUT ID})
     END IF
   };

CONSTRAINT C1_All_Persons_Shave_Or_Not
   Person = ShavesSelf UNION ShavesSelfNot;

CONSTRAINT C2_Nobody_Both_Does_And_Does_Not_Shave
   IS_EMPTY(ShavesSelf INTERSECT ShavesSelfNot);

CONSTRAINT C3_Barber_Is_A_Person
   IS_EMPTY(Barber MINUS Person);

CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber
   (Barber JOIN ShavesSelfNot) = (Barber JOIN ((Shaves RENAME {Shaver AS ID})) {ID});

CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves
   ShavesSelf = ((Shaves WHERE Shaver = Shavee) {Shavee}) RENAME {Shavee AS ID};

// Start with two people, one who shaves and one who does not.
INSERT Person REL {TUP {ID 'Dave'}}, INSERT ShavesSelf REL {TUP {ID 'Dave'}};
INSERT Person REL {TUP {ID 'Nikki'}}, INSERT ShavesSelfNot REL {TUP {ID 'Nikki'}};
Attempting to define a barber fails thusly:

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelf REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber to fail.

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelfNot REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves to fail.

Here's my Tutorial D equivalent:

// All people in a Russell world...
VAR Person REAL RELATION {ID CHARACTER} KEY {ID};

// ...either shave themselves...
VAR ShavesSelf REAL RELATION {ID CHARACTER} KEY {ID};

// ...or do not shave themselves.
VAR ShavesSelfNot REAL RELATION {ID CHARACTER} KEY {ID};

// The barber
VAR Barber REAL RELATION {ID CHARACTER} KEY {};

// Who shaves who?
VAR Shaves VIRTUAL
   UNION {
     ((EXTEND ShavesSelf: {Shaver := ID, Shavee := ID}) {ALL BUT ID}),
     IF IS_EMPTY(Barber) THEN
       REL {Shaver CHAR, Shavee CHAR} {}
     ELSE
       ((EXTEND ShavesSelfNot: {Shaver := ID FROM TUPLE FROM Barber, Shavee := ID}) {ALL BUT ID})
     END IF
   };

CONSTRAINT C1_All_Persons_Shave_Or_Not
   Person = ShavesSelf UNION ShavesSelfNot;

CONSTRAINT C2_Nobody_Both_Does_And_Does_Not_Shave
   IS_EMPTY(ShavesSelf INTERSECT ShavesSelfNot);

CONSTRAINT C3_Barber_Is_A_Person
   IS_EMPTY(Barber MINUS Person);

CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber
   (Barber JOIN ShavesSelfNot) = (Barber JOIN ((Shaves RENAME {Shaver AS ID})) {ID});

CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves
   ShavesSelf = ((Shaves WHERE Shaver = Shavee) {Shavee}) RENAME {Shavee AS ID};

// Start with two people, one who shaves and one who does not.
INSERT Person REL {TUP {ID 'Dave'}}, INSERT ShavesSelf REL {TUP {ID 'Dave'}};
INSERT Person REL {TUP {ID 'Nikki'}}, INSERT ShavesSelfNot REL {TUP {ID 'Nikki'}};

Attempting to define a barber fails thusly:

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelf REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C4_All_Who_Dont_Shave_Themselves_Are_Shaved_By_Barber to fail.

INSERT Barber REL {TUP {ID 'BobTheBarber'}}, INSERT Person REL {TUP {ID 'BobTheBarber'}}, INSERT ShavesSelfNot REL {TUP {ID 'BobTheBarber'}};

ERROR: RS0285: Update will cause CONSTRAINT C5_All_Who_Shave_Themselves_Are_Shaving_Themselves to fail.

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org

#5 · December 12, 2019, 10:14 pm

Quote from AntC on December 12, 2019, 10:14 pm
Hehe, I prefer the Groucho Marx version of the paradox: I wouldn't join a club that would allow me as a member. There's also a rather sweet version built out of the Bertie Wooster stories: Bertie is in a Gentlemen's club (The Drones); Jeeves is in a club for Gentlemen's Gentlemen (because what goes on in The Drones stays in The Drones). How about the manservants who work in those clubs? They're not Gentlemen's Gentlemen, so does that make them eligible for The Drones? Dear me no! So there must be a third club for manservants. OK that third club must have manservants; which club can they join? Ad infinitum ...

I haven't worked through your schema in detail yet, but the critical bit about the Barber paradox is this beyond-first-order requirement:

The Barber shaves everybody who doesn't shave themselves.

It's beyond first-order because the "everybody who ..." is quantifying over the set. "Doesn't shave themself" is the predicate for membership of the set.

Addit: the critical thing is this is a paradox of self-reference, that's why "themself". Where I say below "your constraints don't quantify in that fashion", I mean you don't have any self-references. Hofstadter wrote a whole book about it 'Gödel, Escher, Bach'. I've captured the self-reference below as X = Y.

The way the Barber paradox is elaborated, usually there's some tale about there used to be several barbers in town (so no paradox: each barber gets shaved by another). With the rise of the safety razor, more people take to shaving themselves; the barbering business drops off until there's only one barber left. Then it must be that last Barber shaves everybody who doesn't shave themself.

On a quick skim, your constraints don't quantify in that fashion. I think what you'd need is a base relvar of 'X shaves Y'. With a constraint either X = Y or X = Barber. Then we could have a tuple with 'Barber shaves Barber'; no constraint broken so far. (Rather than hard-coding 'Barber' or holding it as a variable: another base relvar listing the Barbers; start with several, reduce it to one. IOW the X = Barber constraint is a JOIN/Inclusion Dependency 'X ∈ Barbers'.)

Then we capture the paradox with a constraint: X ∈ Barbers ⇔ X ≠ Y "The Barber shaves everybody who doesn't shave themselves"/the set of people the Barber shaves is equal the set of people who don't shave themselves. The tuple 'Barber shaves Barber' violates that.

Another way to unspring the paradox is to say the Barber never shaves/is shaved. That is, no tuple in that table with Y = Barber. You already have constraints excluding that possibility.

Hehe, I prefer the Groucho Marx version of the paradox: I wouldn't join a club that would allow me as a member. There's also a rather sweet version built out of the Bertie Wooster stories: Bertie is in a Gentlemen's club (The Drones); Jeeves is in a club for Gentlemen's Gentlemen (because what goes on in The Drones stays in The Drones). How about the manservants who work in those clubs? They're not Gentlemen's Gentlemen, so does that make them eligible for The Drones? Dear me no! So there must be a third club for manservants. OK that third club must have manservants; which club can they join? Ad infinitum ...

I haven't worked through your schema in detail yet, but the critical bit about the Barber paradox is this beyond-first-order requirement:

The Barber shaves everybody who doesn't shave themselves.

It's beyond first-order because the "everybody who ..." is quantifying over the set. "Doesn't shave themself" is the predicate for membership of the set.

Addit: the critical thing is this is a paradox of self-reference, that's why "themself". Where I say below "your constraints don't quantify in that fashion", I mean you don't have any self-references. Hofstadter wrote a whole book about it 'Gödel, Escher, Bach'. I've captured the self-reference below as X = Y.

The way the Barber paradox is elaborated, usually there's some tale about there used to be several barbers in town (so no paradox: each barber gets shaved by another). With the rise of the safety razor, more people take to shaving themselves; the barbering business drops off until there's only one barber left. Then it must be that last Barber shaves everybody who doesn't shave themself.

On a quick skim, your constraints don't quantify in that fashion. I think what you'd need is a base relvar of 'X shaves Y'. With a constraint either X = Y or X = Barber. Then we could have a tuple with 'Barber shaves Barber'; no constraint broken so far. (Rather than hard-coding 'Barber' or holding it as a variable: another base relvar listing the Barbers; start with several, reduce it to one. IOW the X = Barber constraint is a JOIN/Inclusion Dependency 'X ∈ Barbers'.)

Then we capture the paradox with a constraint: X ∈ Barbers ⇔ X ≠ Y "The Barber shaves everybody who doesn't shave themselves"/the set of people the Barber shaves is equal the set of people who don't shave themselves. The tuple 'Barber shaves Barber' violates that.

Another way to unspring the paradox is to say the Barber never shaves/is shaved. That is, no tuple in that table with Y = Barber. You already have constraints excluding that possibility.

#6 · December 12, 2019, 11:33 pm

Quote from AntC on December 12, 2019, 11:33 pm

Quote from Erwin on December 11, 2019, 7:56 pm

Now that I've worked through your schema in more detail ...

The point about these paradoxes is that the description 'smuggles in' a contradiction. They're usually elaborated as something of a fairy-tale that starts with a logically consistent world, and by small steps (each of which seems to be plausible and consistent) ends up in an impossible world. I'm afraid your schema which prevents there ever being a Barber doesn't really 'play the game'/it doesn't have enough of a smell. Of course, logically if there's a contradiction then the world must become impossible somewhere, so it's logically valid to block there being a Barber. If this were aimed as a teaching exercise, I'd say you've failed to get the lesson across.

As per my earlier message, I'd prefer to capture an initial scenario where there's more than one barber, and no contradiction because each barber is shaved by some other barber. Then hit the constraint violation at the point where the last-but-one barber closes their business.

...

So it is impossible to introduce a barber (the very act that would render undecidable a certain proposition constraining this world) into this world without violating any declared constraint, and (what this post is actually about) *** a TTM system that supports enforcing all these constraints seems PERFECTLY capable of making that happen *** , i.e. it seems not all that impossible to use TTM-style relational technology to block out situations that account for the "undecidability" of certain propositions (and which lead certain people to want to restrain relational technology to some equivalent of logical first-order).

Um? All your constraints are expressible as first-order. This doesn't demonstrate that relational technology needs to go beyond first-order. What those 'certain people' want to avoid within the algebra is, depending on which people: a) transitive closure; b) aggregate operations; c) relvars and assignment. Your example isn't coming anywhere near those. (Leaving aside anyway whether they are actually beyond first-order.)

Whatever clever point you think you are making, I think you've just failed to demonstrate it. You have not built the scenario in such a way as to express the "undecidable" proposition, because you haven't allowed for any self-reference.

(Adding the constraint "there must be at least one barber" makes the empty database violate that constraint, making that constraint not even introducible, requiring a barber to first be introduced before that particular constraint can be made part of the system, but introducing a barber remains equally impossible for the reasons already given. The conclusion appears to remain the same.)

Meticulous inspection/review requested.

Your "introducing a barber remains equally impossible" is an artefact of your particular choice of schema, and the relvar predicates. What you've done is short-circuit the attempt to 'smuggle in' the contradiction. I simply think you've not demonstrated your claimed "what this post is actually about".

Quote from Erwin on December 11, 2019, 7:56 pm

Now that I've worked through your schema in more detail ...

The point about these paradoxes is that the description 'smuggles in' a contradiction. They're usually elaborated as something of a fairy-tale that starts with a logically consistent world, and by small steps (each of which seems to be plausible and consistent) ends up in an impossible world. I'm afraid your schema which prevents there ever being a Barber doesn't really 'play the game'/it doesn't have enough of a smell. Of course, logically if there's a contradiction then the world must become impossible somewhere, so it's logically valid to block there being a Barber. If this were aimed as a teaching exercise, I'd say you've failed to get the lesson across.

As per my earlier message, I'd prefer to capture an initial scenario where there's more than one barber, and no contradiction because each barber is shaved by some other barber. Then hit the constraint violation at the point where the last-but-one barber closes their business.

...

So it is impossible to introduce a barber (the very act that would render undecidable a certain proposition constraining this world) into this world without violating any declared constraint, and (what this post is actually about) *** a TTM system that supports enforcing all these constraints seems PERFECTLY capable of making that happen *** , i.e. it seems not all that impossible to use TTM-style relational technology to block out situations that account for the "undecidability" of certain propositions (and which lead certain people to want to restrain relational technology to some equivalent of logical first-order).

Um? All your constraints are expressible as first-order. This doesn't demonstrate that relational technology needs to go beyond first-order. What those 'certain people' want to avoid within the algebra is, depending on which people: a) transitive closure; b) aggregate operations; c) relvars and assignment. Your example isn't coming anywhere near those. (Leaving aside anyway whether they are actually beyond first-order.)

Whatever clever point you think you are making, I think you've just failed to demonstrate it. You have not built the scenario in such a way as to express the "undecidable" proposition, because you haven't allowed for any self-reference.

(Adding the constraint "there must be at least one barber" makes the empty database violate that constraint, making that constraint not even introducible, requiring a barber to first be introduced before that particular constraint can be made part of the system, but introducing a barber remains equally impossible for the reasons already given. The conclusion appears to remain the same.)

Meticulous inspection/review requested.

Your "introducing a barber remains equally impossible" is an artefact of your particular choice of schema, and the relvar predicates. What you've done is short-circuit the attempt to 'smuggle in' the contradiction. I simply think you've not demonstrated your claimed "what this post is actually about".

#7 · December 13, 2019, 12:44 am

Quote from AntC on December 12, 2019, 11:33 pm

Um? All your constraints are expressible as first-order. This doesn't demonstrate that relational technology needs to go beyond first-order. What those 'certain people' want to avoid within the algebra is, depending on which people: a) transitive closure; b) aggregate operations; c) relvars and assignment. Your example isn't coming anywhere near those. (Leaving aside anyway whether they are actually beyond first-order.)

The question of how far first-order can take us is an interesting one. I have yet to see a way to add new (calculated) values to a relational value expressible as first-order. What about the IS_EMPTY() function used in Dave's version? Perhaps a future post on the subject?

Your "introducing a barber remains equally impossible" is an artefact of your particular choice of schema, and the relvar predicates. What you've done is short-circuit the attempt to 'smuggle in' the contradiction. I simply think you've not demonstrated your claimed "what this post is actually about".

What might a 'smuggled in' contradiction look like, expressed in relational terms? I can't imagine.

Andl - A New Database Language - andl.org

#8 · December 13, 2019, 2:13 am

Quote from AntC on December 13, 2019, 2:13 am
Aha! Your schema is incapable of expressing conundrums of self-reference because each of your base relvars has only a single attribute. Here's a more appropriate and less obfuscated schema with bonus less-helpless English, no "eurhm"s. I'll try to follow your style of decls, although I agree with Dave that FI is quirky.

VAR SHAVES : { (B, P) | B shaves person P }

{{ P }} KEYS FOR SHAVES /* C11: however you express a KEY constraint, although I suppose a person might have more than one barber */

/* and/or shave themselves on workdays but go to a barber for high days */

VAR BAR : { B | B is a barber }

(SHAVES WHERE B ≠ P) NOT MATCHING BAR = FI /* C12: Inclusion Dependency all non-self-shavers must have a barber */

(BAR RENAME { P := B }) NOT MATCHING SHAVES = FI /* C13: Inclusion Dependency all barbers must get shaved */

/* note the RENAME is a symptom of the self-referencing */

/* note I haven't insisted all barbers have customers -- darned safety razors! */

I think you'll find with those constraints:

An empty database is valid. As per your design.

A SHAVES with only self-shavers (and empty BAR) is valid. As per your design.

To get non-empty BAR needs Multiple Update to both SHAVES and BAR: Insert (say) {{ B B5 }} into BAR, Insert {{B B5, P B5}} into SHAVES; (barber 5 shaves themselves).

Or if you don't like self-shaving barbers, Multiple Update: Insert {{B B7}, {B B9}} into BAR, Insert {{B B7, P B9}, {B B9, P B7}} into SHAVES; (barber 7 and barber 9 shave each other -- aha! self reference).

You can't now delete either of the two B7, B9 tuples singly from BAR nor from SHAVES: you'll get a referential integrity failure.

But you could delete the B5 tuple from BAR: barber 5 has shut up shop because of dwindling trade.

Now the bamboozling constraint "~~The~~ Some barber shaves everybody who doesn't shave themselves".

BAR = (SHAVES WHERE B ≠ P) { B } /* C14: Equality Dependency, strengthens C12's IND */

Self-shaving barber 5 violates this constraint. B5 appears in BAR, but not in (SHAVES WHERE B ≠ P).

Now pay attention class: there's various ways to translate the English of that bamboozlement into logic. (I've already changed "The" to "Some" to cater for there being more than one barber.)

"All barbers must have some customers. (And customers by definition don't shave themselves.)"

"Barbers shave only those who don't shave themselves."

"All", "some", "only", "those who", (or "the") -- classic symptoms of lurking quantifiers with scope of quantification famously vague in natural languages. It's a wonder anybody ever managed to communicate at all before Russell straightened us out.

BTW an even more ascetic schema is possible, with just relvar SHAVES as per above; and BAR being a virtual.

VAR BAR ::= { B | (B, P) IN SHAVES & B ≠ P }

Then constraint C12 holds by definition. C13 is still required. Self-shaving barber 5 will not get detected by C14 until/unless they get other customers.

Aha! Your schema is incapable of expressing conundrums of self-reference because each of your base relvars has only a single attribute. Here's a more appropriate and less obfuscated schema with bonus less-helpless English, no "eurhm"s. I'll try to follow your style of decls, although I agree with Dave that FI is quirky.

VAR SHAVES : { (B, P) | B shaves person P }

{{ P }} KEYS FOR SHAVES /* C11: however you express a KEY constraint, although I suppose a person might have more than one barber */

/* and/or shave themselves on workdays but go to a barber for high days */

VAR BAR : { B | B is a barber }

(SHAVES WHERE B ≠ P) NOT MATCHING BAR = FI /* C12: Inclusion Dependency all non-self-shavers must have a barber */

(BAR RENAME { P := B }) NOT MATCHING SHAVES = FI /* C13: Inclusion Dependency all barbers must get shaved */

/* note the RENAME is a symptom of the self-referencing */

/* note I haven't insisted all barbers have customers -- darned safety razors! */

I think you'll find with those constraints:

An empty database is valid. As per your design.
A SHAVES with only self-shavers (and empty BAR) is valid. As per your design.
To get non-empty BAR needs Multiple Update to both SHAVES and BAR: Insert (say) {{ B B5 }} into BAR, Insert {{B B5, P B5}} into SHAVES; (barber 5 shaves themselves).
Or if you don't like self-shaving barbers, Multiple Update: Insert {{B B7}, {B B9}} into BAR, Insert {{B B7, P B9}, {B B9, P B7}} into SHAVES; (barber 7 and barber 9 shave each other -- aha! self reference).
You can't now delete either of the two B7, B9 tuples singly from BAR nor from SHAVES: you'll get a referential integrity failure.
But you could delete the B5 tuple from BAR: barber 5 has shut up shop because of dwindling trade.

Now the bamboozling constraint "~~The~~ Some barber shaves everybody who doesn't shave themselves".

BAR = (SHAVES WHERE B ≠ P) { B } /* C14: Equality Dependency, strengthens C12's IND */

Self-shaving barber 5 violates this constraint. B5 appears in BAR, but not in (SHAVES WHERE B ≠ P).

Now pay attention class: there's various ways to translate the English of that bamboozlement into logic. (I've already changed "The" to "Some" to cater for there being more than one barber.)

"All barbers must have some customers. (And customers by definition don't shave themselves.)"
"Barbers shave only those who don't shave themselves."

"All", "some", "only", "those who", (or "the") -- classic symptoms of lurking quantifiers with scope of quantification famously vague in natural languages. It's a wonder anybody ever managed to communicate at all before Russell straightened us out.

BTW an even more ascetic schema is possible, with just relvar SHAVES as per above; and BAR being a virtual.

VAR BAR ::= { B | (B, P) IN SHAVES & B ≠ P }

Then constraint C12 holds by definition. C13 is still required. Self-shaving barber 5 will not get detected by C14 until/unless they get other customers.

#9 · December 13, 2019, 2:34 am

Quote from AntC on December 13, 2019, 2:34 am

Quote from dandl on December 13, 2019, 12:44 am

Quote from AntC on December 12, 2019, 11:33 pm

Um? All your constraints are expressible as first-order. This doesn't demonstrate that relational technology needs to go beyond first-order. What those 'certain people' want to avoid within the algebra is, depending on which people: a) transitive closure; b) aggregate operations; c) relvars and assignment. Your example isn't coming anywhere near those. (Leaving aside anyway whether they are actually beyond first-order.)

The question of how far first-order can take us is an interesting one. I have yet to see a way to add new (calculated) values to a relational value expressible as first-order.

We've done that to well beyond death.

What about the IS_EMPTY() function used in Dave's version? Perhaps a future post on the subject?

not (Exists x, y, z: P(x, y, z)) in which x, y, z correspond to the heading of the relation expression inside IS_EMPTY( ... ), and P( ... ) is the predicate for which that relation expression is the extension.

Your "introducing a barber remains equally impossible" is an artefact of your particular choice of schema, and the relvar predicates. What you've done is short-circuit the attempt to 'smuggle in' the contradiction. I simply think you've not demonstrated your claimed "what this post is actually about".

What might a 'smuggled in' contradiction look like, expressed in relational terms? I can't imagine.

"~~The~~ Some barber shaves everybody who doesn't shave themselves."

See my 'Now pay attention class' towards the end of my previous post. Typically the smuggling-in needs taking advantage of the vagaries of natural language. In 'relational terms' you end up with (for example) schemas/constraints for which no possible relvar content satisfies all constraints; or for which an empty database is the only valid content; or for which some of the relvars can only be empty (Erwin's schema, in which BAR must be empty).

Quote from dandl on December 13, 2019, 12:44 am

Quote from AntC on December 12, 2019, 11:33 pm

Um? All your constraints are expressible as first-order. This doesn't demonstrate that relational technology needs to go beyond first-order. What those 'certain people' want to avoid within the algebra is, depending on which people: a) transitive closure; b) aggregate operations; c) relvars and assignment. Your example isn't coming anywhere near those. (Leaving aside anyway whether they are actually beyond first-order.)

The question of how far first-order can take us is an interesting one. I have yet to see a way to add new (calculated) values to a relational value expressible as first-order.

We've done that to well beyond death.

What about the IS_EMPTY() function used in Dave's version? Perhaps a future post on the subject?

not (Exists x, y, z: P(x, y, z)) in which x, y, z correspond to the heading of the relation expression inside IS_EMPTY( ... ), and P( ... ) is the predicate for which that relation expression is the extension.

Your "introducing a barber remains equally impossible" is an artefact of your particular choice of schema, and the relvar predicates. What you've done is short-circuit the attempt to 'smuggle in' the contradiction. I simply think you've not demonstrated your claimed "what this post is actually about".

What might a 'smuggled in' contradiction look like, expressed in relational terms? I can't imagine.

"~~The~~ Some barber shaves everybody who doesn't shave themselves."

See my 'Now pay attention class' towards the end of my previous post. Typically the smuggling-in needs taking advantage of the vagaries of natural language. In 'relational terms' you end up with (for example) schemas/constraints for which no possible relvar content satisfies all constraints; or for which an empty database is the only valid content; or for which some of the relvars can only be empty (Erwin's schema, in which BAR must be empty).

#10 · December 13, 2019, 6:53 am

Oh, and by the way, Russell thought that the Barber paradox was not an example of 'Russell's Paradox' but "In this form the contradiction is not very difficult to solve."

And indeed the wiki has a first-order formula, which exhibits a contradiction.

So whatever schema/constraints we choose, we're going to end up with a contradiction/we'll be blocked at some point in trying to enter database content.

The Forum for Discussion about The Third Manifesto and Related Matters

Relational Theory and the Russell Paradox