Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: Satisfiability in Logic vs. satisfiability in DB theory
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.