The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

'Closed over relations'; another possibly-quiz [was: Uniqueness of R00]

12
Quote from Vadim on August 18, 2019, 4:30 pm
Quote from AntC on August 18, 2019, 1:11 pm

 

The proper term here is "closure". If you have lattice join and meet operations, and you start with a finite set, then certainly, what you'll generate would be a finite lattice with some top and bottom. Now we are not talking about abstract lattice elements but database relations. So you ask: would the lattice top be a relation with the the empty set of attributes? Likewise, would the lattice bottom be a relation with the empty set of tuples? Not necessarily.

It's worse than that.

  • If all your starting relations are empty, the generated lattice top will be an empty relation. Then what do you nominate as R01?
  • If your starting set doesn't include an empty relation (and the iterated NatJOIN doesn't produce an empty relation), you won't generate R00. We can't appeal to lattice top/bottom to determine it. We could define R00 as lattice bottom projected on lattice top, but the definition of 'projected on' relies on having R00 defined to obtain the heading of lattice top.
  • Likewise it might be impossible to generate a relation with all possible attributes and all combos of possible values for those attributes, i.e. R11, and there's no equation we can appeal to that defines it.

 

Quote from AntC on August 22, 2019, 11:54 am

OK so we should be able to specify (through axioms) that property of relational lattices that doesn't apply for lattices-in-general. Does it go something like this?

  1. For any 3 elements that are not only distinct but in no lattice ordering:
  2. Either we can NatJOIN two of them then NatJOIN that to the third to obtain a greatest lower bound different to the NatJOIN of the first two;
  3. Or we can InnerUnion two of them then InnerUnion that to the third to obtain a least upper bound different to the InnerUnion of the first two;
  4. Or both 2. and 3.

I don't see here anything database specific. Can't you pick 3 elements in any algebra and do the same? And why do you need 3 elements, when you can apply algebraic operations in any order to any existing and newly generated elements?

Without being able to prevent a M_3 structure appearing, the algebraic operations don't fit the mapped structure. So this difficulty is wider than the inability to fix R00.

How did you arrive to M_3? Because, I can't get it: with standard lattice axioms and 3 additional ones from Litak paper it generates counter example of distributivity as 6 element model.

It's worse than that.

  • If all your starting relations are empty, the generated lattice top will be an empty relation. Then what do you nominate as R01?

R_{00}

Let me take this as an opportunity to fix sloppy terminology. Let's call a set of elements closed with respect to NatJOIN and InnerUnion a galaxy. In the past, I sometimes called it database, which is misleading because database is an arbitrary set of relations, not necessarily the closed one. The other times, I used the term universe, which has wrong connotation too.

With this term, there are galaxies with the top element coinciding with galactic center, so what is wrong with that? Sure, you consider them abnormal, but this is just a property.

  • If your starting set doesn't include an empty relation (and the iterated NatJOIN doesn't produce an empty relation), you won't generate R00. We can't appeal to lattice top/bottom to determine it. We could define R00 as lattice bottom projected on lattice top, but the definition of 'projected on' relies on having R00 defined to obtain the heading of lattice top.

Again, there are galaxies where galactic center is not empty (in either dimension). You can clearly see that from the outside (when interpreting elements as database relations), but it is not detectable from the inside (when all other relations in the galaxy have those attributes&tuples as well).

  • Likewise it might be impossible to generate a relation with all possible attributes and all combos of possible values for those attributes, i.e. R11, and there's no equation we can appeal to that defines it.

I have relaxed attitude towards domain safety/dependency. If the galaxy is fixed, then R11 well defined. In fact, with additional unsafe operations, such as the ones introduced in "Relational Lattice Foundation for Algebraic Logic"  one can generate more realistic models (oops, galaxies).

 

12