Michael, (01)
There are usually many different algorithms for solving any
particular problem: (02)
> The notions of decidability and NP-completeness are not
> properties of algorithms -- they are properties of a problem. (03)
You are probably assuming that the best algorithm(s) for a given
problem are already known or knowable. That may be the case for
some kinds of problems (e.g., the ever-popular satisfiability).
But for many kinds of the most interesting problems, the best
algorithms are definitely not known. (Examples upon request.) (04)
> In fact, descriptive complexity theory analyzes the complexity
> of all queries definable in a given language. (05)
Yes, I know. That was the immediate focus of my unhappiness
with what Leo was saying: (06)
1. The people who were doing descriptive complexity theory made
the assumption that the queries were going to be answered by
a *theorem prover*. (07)
2. They were not looking at the far more common case of answering
queries by a *model checker*. (08)
As you know, SQL databases run the world's economy, and the
WHERE clauses used to state queries and constraints have the
full expressive power of FOL (with the restriction that the
predicates involved are not defined recursively). (09)
> Note that we we are referring to worst-case complexity for any
> query and any theory definable in the language. (010)
No! You are talking about a way of using the language that is
unrealistic for a very large class of very important problems.
You must always ask what problem(s) are being solved by what
class of algorithms on what kind(s) of data. (011)
> Queries can be specified as entailment or satisfiability problems,
> and even your example can be specified as an entailment problem,
> albeit more restricted than the general case i.e. even your example
> is an application of "proving a theorem" in a restricted case. (012)
Please look at the real world. SQL databases use model-checking
algorithms, which take polynomial time in the worst case. That is
also what I would recommend for the Semantic Web. (013)
Summary: For the SQL way of answering queries and checking
constraints (which is already the most widely used approach on
the WWW, since most major web sites use SQL databases), FOL is
the appropriate language for stating constraints, definitions,
and queries. (014)
John (015)
_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/ (016)
|