Re: More on lists and sets

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. Received on Thu Mar 30 2006 - 05:52:08 CEST