Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: Satisfiability in Logic vs. satisfiability in DB theory

Re: Satisfiability in Logic vs. satisfiability in DB theory

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Mon, 05 Apr 2004 00:09:15 GMT
Message-ID: <Ls1cc.60704$Ew3.4000858@phobos.telenet-ops.be>


Anthony WIDJAJA wrote:
>
> Recently, I've seen some papers that confuse the notions of
> FOL satisfiability in logic (where the domain is specified in the model
> and may take constants not appearing in any relations)
> and first-order query satisfiability in DB theory (where the domain is
> taken to be the active domain). I'm wondering if the decidability status
> of satisfiability of any fragment of FOL changes when the domain is
> forced to be the active domain.

No, it is the same. What might matter is if you talk about FOL with finite models or not, and if you consider functions or not (but I'd have to look that up). But on finite models and without functions it is the same. This can be shown by a simple argument: if you have a finite model for the FOL formula then you can turn it into a model for the DB formula by adding a unary relation for the active domain.

Received on Sun Apr 04 2004 - 19:09:15 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US