# Re: More on lists and sets

Date: 30 Mar 2006 00:45:09 -0800

Message-ID: <1143708309.249322.124680_at_g10g2000cwb.googlegroups.com>

Mikito Harakiri wrote:

*> Jan Hidders wrote:
**> > Mikito Harakiri wrote:
**> > > Jan Hidders wrote:
*

> > > >

*> > > > Understood, but let's start first with a simpeler question. Is the
**> > > > axiomatization complete if we only consider /\ and \/? (So no 00, 01,
**> > > > 10 and 11.)
**> > >
**> > > Then I don't understand your question. If we remove constant symbols
**> > > (00 and 11 being the most important ones), then what is left are the
**> > > lattice axioms. Lattices however are more general than relation
**> > > algebras.
**> >
**> > Indeed, but the lattice axioms might still be complete. There are
**> > several ways in which such a set of axioms can be complete, so let me
**> > attempt to explain my question more clearly.
**> >
**> > We are considering expressions that are made up of relation variables
**> > and the /\ and \/ operators, e.g., R \/ S and (T /\ R) \/ S. Such
**> > expressions define a query over a database D where D may be defined
**> > here as a function that maps the mentioned relation variables to a
**> > relation. Let e(D) be the result of applying e to D then we can call
**> > two expressions e1 and e2 query-equivalent if for every database DB it
**> > holds that e1(DB) = e2(DB).
**> >
**> > Next to the query-equivalence we can also define lattice-equivalence:
**> > two expressions e1 and e2 are called lattice-equivalent if e1 can be
**> > rewritten to e2 using the lattice axioms.
**> >
**> > So my question is if lattice-equivalence and query-equivalence
**> > coincide. It clearly holds that lattice-equivalence implies
**> > query-equivalence, but whether query-equivalence implies
**> > lattice-equivalence (or not) is unclear to me. And as far as I can tell
**> > the N_5 lattice doesn't really provide a counterexample, but I might be
**> > missing something here.
**> >
**> > Anyway, is my question clear now? Or why such a type of completeness is
**> > important in the context of database theory?
*

>

> I posted my interpretation of your question to sci.math

*> http://groups.google.com/group/sci.math/browse_frm/thread/2e2f97683b5be214/031cd97b3003af5b?hl=en#031cd97b3003af5b*

*> People were quick to respond that lattice theory (nor partial order,*

*> nor boolean algebra for that matter) is complete.*

> You are welcome to

*> steer discussion there, as I'm not really skillful in model theory.
*

Yet it is your model. :-) Pity. Such a result would lift your work on this from "cute" to "really interesting".

- Jan Hidders