Leo, (01)
As I keep repeating, complexity is first and foremost a property
of an algorithm, indirectly a property of a problem, and only
very, very indirectly a property of a language: (02)
> This is a useful tool for determining the specific complexity
> of the description logic you are interested in. (03)
Most of those complexity claims are based on the assumption
that the language is going to be used to prove theorems. (04)
But that is certainly not the case of a logic that is used to
access a database. For example, the WHERE clause in SQL has
the expressive power of first-order logic. But when it is
used to express a query or constraint that is evaluated against
a relational DB, the worst-case complexity takes polynomial time. (05)
And since most relations in a database are indexed on the key
field or fields, many queries and constraints can be evaluated
in logarithmic time. (06)
When talking about complexity, it is essential to keep the purpose
in mind. People keep saying that language L is efficient or
inefficient without ever mentioning the all-important question: (07)
Efficient for what purpose????? (08)
John (09)
_________________________________________________________________
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/ (010)
|