Re: More on lists and sets

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?

• Jan Hidders