Leo, (01)
Just one comment about expressivity: (02)
> Expressivity: Expressivity of the semantic model (i.e.,
> underlying knowledge representation language or logic)
> [No scale determined yet] (03)
There are two very important, but widely misunderstood points
about logic: (04)
1. Expressivity of a statement or a theory is independent
of the language in which it is stated. Translation
*never* changes the expressivity. (05)
2. Computational complexity is *not* a result of the
expressivity of any statement, but of the algorithms
used to process that statement. (06)
For example, SQL allows full FOL for queries and constraints, but
the algorithms that process SQL databases are always decidable and
never take more than polynomial time. In fact, many if not most
SQL queries can be evaluated in linear or even logarithmic time. (07)
An example of a logarithmic-time query: (08)
"Find John Doe's department, manager, and job code." (09)
An example of a linear-time query: (010)
"Find all employees who earn more than their managers." (011)
Even highly complex queries can be evaluated very efficiently
if they are only processed on a subset of the database: (012)
"For all employees in department C99, find [Very Complex Query]." (013)
This query may require a polynomial with a large exponent, such as 3.
But if there are only 20 employees in dept. C99, the time would be
proportional to 8,000 -- a trivial number with current hardware. (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)
|