Kingsley and Michael, (01)
KI
> I am implying that FOL should be an integral part of the underlying
> data representation. With that in place you can then use a query
> language to exploit expressiveness.
>
> RDF does enable the incorporation of FOL into structured data representation. (02)
I'm happy with those two statements. But I would qualify the following: (03)
KI
> SPARQL enables you to query RDF model based structured data. (04)
First, RDF, by itself, has no structure other than triples, of which
the middle term is interpreted as a dyadic relation. But the three
terms could from anywhere and mean anything. (05)
RDFS and OWL are later developments that can be used to define more
structure. Or the structure could be implicit in whatever good code
or spaghetti code that anyone uses to process the triples. (06)
Second, a query processor has a more direct connection to the data
than any program that calls it. The best SQL implementations have
very efficient indexing and optimizing methods that cannot be
implemented by software that doesn't have a direct connection. (07)
Third, SQL is a step backward from Codd's relational model. People
have proposed much better query languages and/or revisions to SQL. (08)
Given the difficulties of changing the standard, sophisticated users
treat SQL as a "cow", in the same sense as Harlan Mills. Following is
my recollection of what Harlan said in a talk about operating systems: (09)
HM
> Many people have complained about OS/360. They proposed many ways
> of improving it or replacing it. They're probably right. But I treat
> OS/360 as a cow. Just accept it for what it does. If you put hay and
> water in one end, you get fertilizer out the other end, and milk from
> the middle. If you keep the ends straight, you'll get along fine. (010)
JFS
>> More precisely, [the SQL WHERE clause] has the expressive power of FOL. (011)
MB
> Isn't it possible to use aggregate functions within WHERE ? Aggregate
> functions are not part of Relational Algebra, which is already FOL. (012)
That's true. There are many functions, such as SUM, which are easy
to implement during the search & retrieval process. That's another
optimization that cannot be implemented efficiently by a processor
that operates only on the results. (013)
MB
> Recursive queries from SQL:1999 are widely implemented (e.G. in the Open
> Source RDB Postgres). So we have First-order logic with a transitive
> closure operator: http://en.wikipedia.org/wiki/Descriptive_complexity (014)
Yes. The term FOL is used for a family of logics with different
extensions and limitations. I would prefer Datalog with recursion,
but the SQL WHERE clause is a useful "cow". (015)
By the way, Ingres and Postgres were designed by Michael Stonebraker,
whose QUEL notation for Ingres was far better than SQL. But he was
forced to adopt SQL as "Intergalactic Dataspeak" (as he called it). (016)
MB
> SPARQL 1.0 has the expressive power of Relational Algebra, and therefore of
> FOL: http://www.dcc.uchile.cl/cgutierr/ftp/expressive-power-sparql.pdf
>
> So what is the point of your statement that SQL WHERE is as expressive as FOL
>? (017)
Yes, but... The first "but" is that SQL, for all its problems, is a far
simpler way to express FOL than SPARQL. Just look at the first 33 pages
of that article. (018)
The second "but" is to look at Appendix III (pp. 35 and 36), which
specifies the syntax and semantics of Datalog in just two pages. (019)
The mathematical style of that appendix is rather heavy for most
programers, but Bob Kowalski taught the Datalog subset of Prolog
(with recursion) to 12 year old children. For the examples he
used and his method of teaching, see the first chapter of (020)
Kowalski, Robert A. (1979) Logic for Problem Solving, North Holland,
New York. (021)
Many years ago, I used this as a textbook for teaching Prolog to IBM
programmers. Some were confused, but most of them loved it. (022)
> BTW - Have a look a this paper:
>
> http://www.theoinf.uni-bayreuth.de/download/pods12submission.pdf
>
> On page 11, there is a table that says that SPARQL 1.1 evaluation
> with current W3C semantics is NP-complete in some cases. I guess
> this does not automatically make SPARQL 1.1 as expressive as
> Existential second-order logic but it is interesting. (023)
The reason is that RDF allows blank nodes, which are the equivalent
of existential quantifiers. In relation position, the quantifiers
range over relations. But even in argument position, blank nodes
create computational issues that are more complex than constants. (024)
JFS
>> ... it is essential to design systems for which heterogeneity,
>> diversity, and interoperability are of primary importance. (025)
KI
> That's exactly what RDF based Linked Data is all about. The only
> problem is that RDF narratives haven't always made this most
> important virtue crystal clear. (026)
I agree that those were the goals of Tim B-L's proposal. But I blame
the DAML project for designing systems that require those 36-page and
24-page *research papers* to explain the issues that Michael cited. (027)
Just look at Kowalski's book. He made the Datalog notation and its
implications crystal clear to children. I used his book to make those
ideas crystal clear to IBM programmers whose minds had been warped by
SQL, IMS, and other atrocities. (028)
The DAML project could and should have adopted Datalog as their query
language. Even with angle brackets, Datalog would be heaven compared
to the garbage they dumped on the world in 2006. (I use the word
'garbage' as a polite way to express my frustration with people who
reinvent square wheels when we had beautiful round wheels years ago.) (029)
John (030)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J (031)
|