Nilsson's book [1] talks about using first-order logic (and its subsets) as
the language for deductive databases. The book is 10 years old, and yet,
AFAIK the expressive power of modern state-of-art database software like
Oracle and PostgreSQL still falls far behind first-order logic: it
essentially doesn't have functors or recursion. Does anyone know why?

[1] http://www.ida.liu.se/~ulfni/lpp/

On Wed, 11 May 2005 07:22:11 -0700, alex goldman wrote:

> yet, AFAIK the expressive power of modern state-of-art database software
> like Oracle and PostgreSQL still falls far behind first-order logic: it
> essentially doesn't have functors or recursion. Does anyone know why?

I believe that Nilsson's book actually describes some of the difficulties
related to recursion: It's non-trivial to implement because it opens a
can of worms with regard to never-ending queries, etc.

Anyhow, both IBM and Oracle have recursive SQL, and I think I've read
that MSSQL 2005^6 will get it, as well. IBM's recursive SQL features are
rather close to SQL:1999/SQL:2003 (the standard) while Oracle's variant is
non-standard and not as powerful, as far as I know.

-- 
Greetings from Troels Arvin, Copenhagen, Denmark

In the last exciting episode, alex goldman <hello@spamm.er> wrote:
> Nilsson's book [1] talks about using first-order logic (and its subsets) as
> the language for deductive databases. The book is 10 years old, and yet,
> AFAIK the expressive power of modern state-of-art database software like
> Oracle and PostgreSQL still falls far behind first-order logic: it
> essentially doesn't have functors or recursion. Does anyone know why?
>
> [1] http://www.ida.liu.se/~ulfni/lpp/

Well, SQL:2003 does define a "WITH" syntax that does allow recursion
in a manner that pretty much parallels the LET macro in Lisp.  DB2
implements it, and there is a preliminary implementation for
PostgreSQL.

Oracle has a "CONNECT BY" construct that allows a rather more limited
form of recursion.

None of that even so much as scratches the difference between these
systems and Prolog.

The point is more that people don't generally understand logic, and
_especially_ the folk for whom it the move from COBOL-based ISAM to
the uncertainty of the degree of declarativeness of SQL.  

If the fact that cost-based optimizers makes it somewhat uncertain how
an SQL processor will evaluate a particular query is disturbing (and,
to many, it is), the leap to the greatly less certainty of
backtracking is too scary for words.

One genuine problem with "the Prolog way" is that the order in which
rules are established will affect outcomes.  That's a bit disturbing
for all of us...

Let me step back to the ISAM-versus-SQL thing, for a moment; it comes
back in the matter of "relationalness."  

The people using SQL to store data often don't grasp that there's a
difference between expressing various facts as a set of relations and
stuffing data into a database like you stuff material into a file.

There is quite a big difference between "relational fact processing"
and "stuffing data into a vaguely structured file system."  

Oracle Corporation gets more licensing fees out of adding in wacky
features that step away from the "orthogonal power" of relational
processing in favor of highly attuned extensions that help them tie
people to the expensive add-ons.

Parallelling this, MySQL AB has been eminently successful at much the
same sort of "vendor lock-in" with low end web applications where they
have been able to convince plenty of makers of such applications to
write their applications to be specifically attuned to the behaviours
of version 3.23 to the point that upgrading to different versions
might well be implausible even though it's an ancient six-year old
product "outdated" by two *major* subsequent releases (4.0 and 4.1).

This misses, of course, _another_ perspective on things, namely the
array perspective.  Consider APL...  It represents a mathematical
notation for describing relationships, and allows some pretty stunning
opportunities for speedups when operations can act efficiently on
vectors.  Kx Systems' kdb+ system particularly provides a mapping
between SQL and a form of APL which is evidently astonishingly fast
for timeseries databases.
-- 
"cbbrowne","@","gmail.com"
http://linuxfinances.info/info/postgresql.html 
Users should cultivate an ability to make the simplest molehill into a
mountain by finding controversial interpretations of innocuous
sounding statements that the sender never intended or imagined.  
-- from the Symbolics Guidelines for Sending Mail

I don't think I would call Oracle "State of the Art"; more like a file
system in thin disguise.

Standard SQL has the SQL/PSM and CTE (Common Table Expressions), so we
are computationally complete.  But the truth is that most commercial
users do not need recursion to do a payroll, keep an inventory, etc.

On 12 May 2005 06:59:18 -0700, "-CELKO-" <jcelko212@earthlink.net>
wrote:

>I don't think I would call Oracle "State of the Art"; 

I agree.

>Standard SQL has the SQL/PSM and CTE (Common Table Expressions), so we
>are computationally complete.  But the truth is that most commercial
>users do not need recursion to do a payroll, keep an inventory, etc.

I disagree, most commercial users would need recursion to solve the
part explosion problems of most inventory systems.


Regards

While people who responded seem to disagree on whether SQL has recursion,
what about functors?

For example, can you express something like this with SQL?

for_any X Y : car(cons(X, Y), X)

-CELKO- wrote:
> I don't think I would call Oracle "State of the Art"; more like a file
> system in thin disguise.
> 
> Standard SQL has the SQL/PSM and CTE (Common Table Expressions), so we
> are computationally complete.  But the truth is that most commercial
> users do not need recursion to do a payroll, keep an inventory, etc.
> 

  It may be that most  commercial users do not need a deductive
database to do things that do not require recursion, but that
still leaves open the heretical possibility that there exist
needs which some commercial users have but which their DBMS does
not allow them to meet because it does allow them to
formulate the questions that it is necessary to ask to find out
if such unmet needs exist.

  BillH
--

Christopher Browne wrote:
> Oracle has a "CONNECT BY" construct that allows a rather more limited
> form of recursion.

Well, "connect by" is [admittedly not especially elegant] way to
express transitive closure. Now, are there any queries that can be
expressed with "Recursive With" but not with transitive closure?

alex goldman wrote:
> While people who responded seem to disagree on whether SQL has recursion,

?? I didn't see any disagreement. What the different answers told you 
was that this differs per SQL standard and per implementation.

> what about functors?
> 
> For example, can you express something like this with SQL?
> 
> for_any X Y : car(cons(X, Y), X)

That depends on what you mean by "can express". Since SQL is a query 
language in which you formulate queries over tables it can only 
formulate queries over tables and not over functors. So in that sense 
the answer is "no" but that observation is about as interesting as the 
fact that SQL also cannot make coffee. If you reformulate it as a 
statement about tables by, for example, modeling car as a binary table 
and cons as a ternary table then you *can* express this and for that you 
don't even need recursion.

-- Jan Hidders

Mikito Harakiri wrote:
> 
> Well, "connect by" is [admittedly not especially elegant] way to
> express transitive closure. Now, are there any queries that can be
> expressed with "Recursive With" but not with transitive closure?

I think there are. It is known that on an ordered domain FO(TC) (first 
order logic plus transitive closure) can express exactly all NSPACE[log 
n] queries and FO(LFP) (first order logic plus a least fixpoint 
operator) exactly all PTIME queries. The latter class is known to be 
strictly greater than the first.

-- Jan Hidders

Jan Hidders wrote:

> alex goldman wrote:
>> While people who responded seem to disagree on whether SQL has recursion,
> 
> ?? I didn't see any disagreement. What the different answers told you
> was that this differs per SQL standard and per implementation.
> 
>> what about functors?
>> 
>> For example, can you express something like this with SQL?
>> 
>> for_any X Y : car(cons(X, Y), X)
> 
> That depends on what you mean by "can express". Since SQL is a query
> language in which you formulate queries over tables it can only
> formulate queries over tables and not over functors. So in that sense
> the answer is "no" but that observation is about as interesting as the
> fact that SQL also cannot make coffee. If you reformulate it as a
> statement about tables by, for example, modeling car as a binary table
> and cons as a ternary table then you can express this and for that you
> don't even need recursion.

The difference between having functors and not having them is fundamental.
In one case inference is decidable, and in another it isn't (If you think
this is uninteresting, you are probably in the wrong business) The
expressiveness varies accordingly.

"Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message 
news:i8s681h5vi6oq1da8oei2qobp147d17upg@4ax.com...
> On 12 May 2005 06:59:18 -0700, "-CELKO-" <jcelko212@earthlink.net>
> wrote:

>>Standard SQL has the SQL/PSM and CTE (Common Table Expressions), so we
>>are computationally complete.  But the truth is that most commercial
>>users do not need recursion to do a payroll, keep an inventory, etc.
>
> I disagree, most commercial users would need recursion to solve the
> part explosion problems of most inventory systems.

What you need in theory to solve problems in practice, and
what you need in practice to solve problems in practice, are
two entirely different things.

You're just disagreeable because your POV
is heavily bound to the pedagogy of Date et al
which attempts to reduce current practice to a
data-centric model conceived in response to the
technological environment of the 1970's.






Pete Brown
Falls Creek
Oz
www.mountainman.com.au

In article <Y5Age.33690$B82.990538@news20.bellglobal.com>, Christopher Browne wrote:
> In the last exciting episode, alex goldman <hello@spamm.er> wrote:
>> Nilsson's book [1] talks about using first-order logic (and its subsets) as
>> the language for deductive databases. The book is 10 years old, and yet,
>> AFAIK the expressive power of modern state-of-art database software like
>> Oracle and PostgreSQL still falls far behind first-order logic: it
>> essentially doesn't have functors or recursion. Does anyone know why?
 
> The point is more that people don't generally understand logic, and
> _especially_ the folk for whom it the move from COBOL-based ISAM to
> the uncertainty of the degree of declarativeness of SQL.  
> 
> If the fact that cost-based optimizers makes it somewhat uncertain how
> an SQL processor will evaluate a particular query is disturbing (and,
> to many, it is), the leap to the greatly less certainty of
> backtracking is too scary for words.

Efficient deductive databases do not use backtracking.  They use
relational operations just like SQL databases.  For non-recursive
queries, there is no reason for a deductive database to be any less
efficient or predictable in performance than an SQL database.
The performance of recursive queries is much more difficult to
predict, whether you are using SQL or a deductive database.
For example the sizes of relations to be joined can be very
different from one recursive invocation to the next within the
same query, which makes the optimizer's life very difficult.

Part of the reason for the lack of interest in deductive databases
is that the systems that have been implemented have been university
research projects that have produced nice query languages, but without
the (perceived) robustness, performance, tools and guaranteed ongoing
support needed for commercial adoption.  I have been involved with one
of these efforts (the Aditi project <http://www.cs.mu.oz.au/aditi>,
which uses Mercury <http://www.cs.mu.oz.au/mercury> as its query
language).

I think it would be much easier to promote a deductive query language
built on top of an existing mature database system, selling it as
cleaner and easier to use than SQL, with the increased expressive
power being an added bonus.  At the time the Aditi project started,
SQL databases weren't extendable enough for this to be done with
reasonable performance.  Looking at PostgreSQL now, I think that
has changed.

> One genuine problem with "the Prolog way" is that the order in which
> rules are established will affect outcomes.  That's a bit disturbing
> for all of us...

While deductive query languages may look like Prolog, they are not
Prolog, and do not share Prolog's non-logical behaviour.

Simon Taylor.

Jan Hidders wrote:
>
> I think there are. It is known that on an ordered domain FO(TC) (first 
> order logic plus transitive closure) can express exactly all NSPACE[log 
> n] queries and FO(LFP) (first order logic plus a least fixpoint 
> operator) exactly all PTIME queries. The latter class is known to be 
> strictly greater than the first.

P (det poly time) certainly includes NL (nondet log space) but I don't 
think it is currently known whether this inclusion is strict. Do you 
have a reference? (I'm looking at Immerman, Descriptive Complexity, 1999):

  "It has not yet been proved that L is not equal to PH.."

where L is contained in NL, and P is contained in PH.

Maybe it has something to do with "ordered domain"?
-- 
Mitch Harris
(remove q to reply)

On Fri, 13 May 2005 06:42:17 GMT, "mountain man"
<hobbit@southern_seaweed.com.op> wrote:

>> I disagree, most commercial users would need recursion to solve the
>> part explosion problems of most inventory systems.
>
>What you need in theory to solve problems in practice, and
>what you need in practice to solve problems in practice, are
>two entirely different things.

That's bullshit.

>You're just disagreeable because your POV
>is heavily bound to the pedagogy of Date et al
>which attempts to reduce current practice to a
>data-centric model conceived in response to the
>technological environment of the 1970's.

To say that recursion is not useful to solve part explosion problems
shows profound ignorance.


Regards

"Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message 
news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...

> To say that recursion is not useful to solve part explosion problems
> shows profound ignorance.


1) WTF is this critical inventory explosion problem?
2) How many organisations are experiencing this problem?






Pete Brown
Falls Creek
Oz
www.mountainman.com.au

mountain man wrote:

> "Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message
> news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...
> 
>> To say that recursion is not useful to solve part explosion problems
>> shows profound ignorance.
> 
> 
> 1) WTF is this critical inventory explosion problem?

A widget is made of components.  Each component is made of other components,
and so on and so on.  The nesting level is not defined ahead of time and
can go to arbitrary depths.

Building a flat list of a complete parts explosion for an item therefore is
a hassle.

> 2) How many organisations are experiencing this problem?
> 

All manufacturers in the world?

-- 
Kenneth Downs
Secure Data Software, Inc.
(Ken)nneth@(Sec)ure(Dat)a(.com)

Alfredo Novoa wrote:
>
> I disagree, most commercial users would need recursion to solve the
> part explosion problems of most inventory systems.
>
>
> Regards

All you need is an algorithm for left-most tree traversal (and of
course a database in which you can define a tree). It's nice of
oracle to supply the logic for left-most tree traversal, but it can
be done easy enuf in say the programming language c.

Also the algorithm doesn't need to be recursive - if memory serves
(I wrote a couple of parts explosions/implosions for MRP systems
a number of years ago) if you don't use recursion you can get by
with a stack containing where you are at each level 'above' you.

AFAIK there is no algorithm using recursion that can't be 'emulated'
by one not using recursion.

Maybe you have another meaning for 'recursion' in mind than the
strictly algorithmic/programming one?

Thanks.

Ken

On 13 May 2005 09:35:47 -0700, "ken quirici" <kquirici@yahoo.com>
wrote:

>All you need is an algorithm for left-most tree traversal (and of
>course a database in which you can define a tree).

I don't know any database system in which you can not.

>Also the algorithm doesn't need to be recursive 

Of course.

>(I wrote a couple of parts explosions/implosions for MRP systems
>a number of years ago) if you don't use recursion you can get by
>with a stack containing where you are at each level 'above' you.

I wrote similar routines.

>AFAIK there is no algorithm using recursion that can't be 'emulated'
>by one not using recursion.

Indeed, but all what a computer does can be emulated with pencils and
paper sheets or with knife marks in a wall :)

>Maybe you have another meaning for 'recursion' in mind than the
>strictly algorithmic/programming one?

No, what I mean is that recursion is a very desirable feature for
inventory system developers.



Regards

Jan Hidders wrote:
> Mikito Harakiri wrote:
> >
> > Well, "connect by" is [admittedly not especially elegant] way to
> > express transitive closure. Now, are there any queries that can be
> > expressed with "Recursive With" but not with transitive closure?
>
> I think there are. It is known that on an ordered domain FO(TC)
(first
> order logic plus transitive closure) can express exactly all
NSPACE[log
> n] queries and FO(LFP) (first order logic plus a least fixpoint
> operator) exactly all PTIME queries. The latter class is known to be
> strictly greater than the first.

How about FO+aggregation? Actually, I was expecting that somebody from
DB2 camp would jump in and exibit such a query. Well, database wars are
over.

There is no question that any big database vendor that has no problems
with budget is capable implementing a feature X, especially that it's a
part of the standard. It seems, however, like swallowing some
accounting company has more priority than getting database issues
straight.

alex goldman wrote:
> Jan Hidders wrote:
>
> > but that observation is about as interesting as the
> > fact that SQL also cannot make coffee.
>
> The difference between having functors and not having them is
fundamental.

The difference between having a cup of coffee in the morning or not is
also fundamental for the productive work later in the day.

Are functors part of mathematical logic, or the whole theory could
exist happily without them?

| Kenneth Downs <knode.wants.this@see.sigblock> wrote:
|
| mountain man wrote:
| 
| > "Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message
| > news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...
| > 
| >> To say that recursion is not useful to solve part explosion problems
| >> shows profound ignorance.
| > 
| > 
| > 1) WTF is this critical inventory explosion problem?
| 
| A widget is made of components.  Each component is made of other components,
| and so on and so on.  The nesting level is not defined ahead of time and
| can go to arbitrary depths.

But never really does.
 
| Building a flat list of a complete parts explosion for an item therefore is
| a hassle.
| 
| > 2) How many organisations are experiencing this problem?
| > 
| 
| All manufacturers in the world?

But they've seen it since data processing began, and have solved it many
times, usually by some adhoc hack. I don't recall any particular scheme
but I wouldn't be at all surprised to see multiple foreign keys in the
parts table: one gives the sub-parts at the next lower level, and
another gives the basic warehouse sub-part bins, and another goes to the
sub-parts that accounts think are atomic, which is where the price is
stored, and ... . If it's really complicated some lucky hexhead gets to
write a db procedure in C that navigates specially for that problem, and
he'll get a spec saying "allow for 5 nested levels" since the analyst
can't imagine there being any more than that in the foreseeable future.
That's what DP is like. Adding recursion to it would simply cause fear
of the unknown in all those who never did recursion in their Cobol past,
which is most of the managers.

--
Patrick Herring, http://www.anweald.co.uk/ph

alex goldman wrote:
> 
> The difference between having functors and not having them is fundamental.
> In one case inference is decidable, and in another it isn't (If you think
> this is uninteresting, you are probably in the wrong business) The
> expressiveness varies accordingly.

Sure. I never said that functors per se were uninteresting in the 
context of databases, just that if your question is interpreted in a 
naive way the answer is evidently "no" in a very uninteresting way. 
Having said that, it still looks a bit artificial if you introduce them 
only for the reason of boosting the expressive power of the query language.

-- Jan Hidders

Mitch Harris wrote:
> Jan Hidders wrote:
>>
>> I think there are. It is known that on an ordered domain FO(TC) (first 
>> order logic plus transitive closure) can express exactly all 
>> NSPACE[log n] queries and FO(LFP) (first order logic plus a least 
>> fixpoint operator) exactly all PTIME queries. The latter class is 
>> known to be strictly greater than the first.
> 
> P (det poly time) certainly includes NL (nondet log space) but I don't 
> think it is currently known whether this inclusion is strict. Do you 
> have a reference? (I'm looking at Immerman, Descriptive Complexity, 1999):
> 
>  "It has not yet been proved that L is not equal to PH.."
> 
> where L is contained in NL, and P is contained in PH.
> 
> Maybe it has something to do with "ordered domain"?

I'm afraid it has to do with me being a bit "unordered". :-( The problem 
is indeed still open.

-- Jan Hidders

"Kenneth Downs" <knode.wants.this@see.sigblock> wrote in message 
news:tuuel2-uph.ln1@pluto.downsfam.net...
> mountain man wrote:
>
>> "Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message
>> news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...
>>
>>> To say that recursion is not useful to solve part explosion problems
>>> shows profound ignorance.
>>
>>
>> 1) WTF is this critical inventory explosion problem?
>
> A widget is made of components.  Each component is made of other 
> components,
> and so on and so on.  The nesting level is not defined ahead of time and
> can go to arbitrary depths.

Thanks for the brief.

Yes, arbitary but not infinite depths, and once the maximum
depth is chartered, the current entire instance of the problem
can be flattened - no big deal.  Auto-regen flat structure as
required.

Throw the max depth code into an automated exception alert
to present on a queue to some workgroup that an instance has
arisen where widget_id 123456789 has exceeded max depth.


> Building a flat list of a complete parts explosion for an item therefore 
> is
> a hassle.

If you dont know the depth it is, but you build
a tool to determine the maximim depth first.


In fact there are literally hundreds of alternative work-
arounds to this type of problem without involving
any form of esoteric generalised recursion theory.



>> 2) How many organisations are experiencing this problem?
>>
>
> All manufacturers in the world?


Not the ones I've ever had anything to do with.

My main clients have been patent and trade mark attorneys
and their IP management systems invariably generate these
types of problems where relationships involve trees and
their branches. EG:

Tracking the relationships between patent applications,
especially divisional patents, that can have parents, which
themselves are a divisional patent of another divisional, etc.
sounds like the same form of problem.

If you relied upon theory you'd have a problem.
Fortunately there are viable practice-based
alternatives in SQL.





Pete Brown
Falls Creek
Oz
www.mountainman.com.au

mountain man wrote:
[snip "recursion useful to solve part explosion problems"]

 > In fact there are literally hundreds of alternative work-
 > arounds to this type of problem without involving
 > any form of esoteric generalised recursion theory.

<delurk>

Just curious:
What is esoteric about it?
Or: What makes you look for alternatives?

</delurk>

 > ...
 > If you relied upon theory you'd have a problem.
 > Fortunately there are viable practice-based
 > alternatives in SQL.

"mAsterdam" <mAsterdam@vrijdag.org> wrote in message 
news:4285cbf6$0$64528$e4fe514c@news.xs4all.nl...
> mountain man wrote:
> [snip "recursion useful to solve part explosion problems"]
>
> > In fact there are literally hundreds of alternative work-
> > arounds to this type of problem without involving
> > any form of esoteric generalised recursion theory.
>
> <delurk>
>
> Just curious:
> What is esoteric about it?
> Or: What makes you look for alternatives?
>
> </delurk>
>
> > ...
> > If you relied upon theory you'd have a problem.
> > Fortunately there are viable practice-based
> > alternatives in SQL.


In my case practice based alternatives were engineered
for many years before I became aware that generalised and
theoretical treatments of the problem were being considered.

So its not that I went looking for alternatives, rather that in
the early days I was not aware of any recursion theory.

IMO there are at least 2 roads
to database systems theory:
the road of theory and
the road of practice.



Pete Brown
Falls Creek
Oz
www.mountainman.com.au

"Jan Hidders" <jan.hidders@REMOVETHIS.pandora.be> wrote in message 
news:xVQge.89347$4x.5404810@phobos.telenet-ops.be...
> alex goldman wrote:
>> While people who responded seem to disagree on whether SQL has recursion,
>
> ?? I didn't see any disagreement. What the different answers told you was 
> that this differs per SQL standard and per implementation.
>
>> what about functors?
>>
>> For example, can you express something like this with SQL?
>>
>> for_any X Y : car(cons(X, Y), X)
>
> That depends on what you mean by "can express". Since SQL is a query 
> language in which you formulate queries over tables it can only formulate 
> queries over tables and not over functors. So in that sense the answer is 
> "no" but that observation is about as interesting as the fact that SQL 
> also cannot make coffee. If you reformulate it as a statement about tables 
> by, for example, modeling car as a binary table and cons as a ternary 
> table then you *can* express this and for that you don't even need 
> recursion.
>
> -- Jan Hidders

It actually depends on what <alex goldman> means by

a. 'Functor',  the word that has different meaning in different PLs/contexts

b. car(cons(X,Y), X).  If it's Lisp,  the expression does not make sense. 
If it's a Prolog 'functor', it does not make any sense either.

VC wrote:

> 
> "Jan Hidders" <jan.hidders@REMOVETHIS.pandora.be> wrote in message
> news:xVQge.89347$4x.5404810@phobos.telenet-ops.be...
>> alex goldman wrote:
>>> While people who responded seem to disagree on whether SQL has
>>> recursion,
>>
>> ?? I didn't see any disagreement. What the different answers told you was
>> that this differs per SQL standard and per implementation.
>>
>>> what about functors?
>>>
>>> For example, can you express something like this with SQL?
>>>
>>> for_any X Y : car(cons(X, Y), X)
>>
>> That depends on what you mean by "can express". Since SQL is a query
>> language in which you formulate queries over tables it can only formulate
>> queries over tables and not over functors. So in that sense the answer is
>> "no" but that observation is about as interesting as the fact that SQL
>> also cannot make coffee. If you reformulate it as a statement about
>> tables by, for example, modeling car as a binary table and cons as a
>> ternary table then you *can* express this and for that you don't even
>> need recursion.
>>
>> -- Jan Hidders
> 
> It actually depends on what <alex goldman> means by
> 
> a. 'Functor',  the word that has different meaning in different
> PLs/contexts
> 
> b. car(cons(X,Y), X).  If it's Lisp,  the expression does not make sense.
> If it's a Prolog 'functor', it does not make any sense either.

In the future, please add qualifiers like "to me" to silly statements like
the above. Car of a cons, consisting of X and Y, is X.

some dude wrote:
>> that observation is about as interesting as the fact that SQL also cannot 
>> make coffee.

It is not a fact that SQL cannot make coffee. Native SQL
(ie: across vendors) may easily be associated with a 24x7
task scheduler capable of switching on appropriately
configured external peripheral devices.

Conditional values associated with sugar and milk are
catered for in the WHERE statement.
eg: 1) where sugar = 1.5 and milk = YES.
     2) where sugar is null and milk is null

SQL compliant coffee machines might be rare, but
they exist, and they make good coffee, right on
schedule.





Pete Brown
Falls Creek
Oz
www.mountainman.com.au

alex goldman wrote:
> VC wrote:
>>b. car(cons(X,Y), X).  If it's Lisp,  the expression does not make sense.
>>If it's a Prolog 'functor', it does not make any sense either.
> In the future, please add qualifiers like "to me" to silly statements like
> the above. Car of a cons, consisting of X and Y, is X.

But what is car(cons(X,Y),X)? That looks like it's feeding
car two things, namely cons(X,Y) and X. I understand car eats
a list and spits out the first element of the list, but
have no idea what it does with a pair of objects.

Robert Low wrote:

> alex goldman wrote:
>> VC wrote:
>>>b. car(cons(X,Y), X).  If it's Lisp,  the expression does not make sense.
>>>If it's a Prolog 'functor', it does not make any sense either.
>> In the future, please add qualifiers like "to me" to silly statements
>> like the above. Car of a cons, consisting of X and Y, is X.
> 
> But what is car(cons(X,Y),X)? 

It's a relation (whereas in Lips, it would be a function)

> That looks like it's feeding 
> car two things, namely cons(X,Y) and X. I understand car eats
> a list and spits out the first element of the list, 

In Lisp. More acctuarately, it takes a cons cell (which does not have to be
a /proper/ list) and returns its first element.

(cons '(1 . 2)) -> 1

In Lisp, it's an elementary function. In prolog, we define a
corresponding /relation/ (of arity 2) stating that car of a cons is its
first element.

> but 
> have no idea what it does with a pair of objects.

Relations don't "do" anything. Inference procedures do. Relations just state
properties. Unlike Lisp, in Prolog you can also ask `reverse` questions
like what object is this a cons of?

alex goldman wrote:

> (cons '(1 . 2)) -> 1

this should be "car" instead

alex goldman wrote:

> in Prolog you can also ask `reverse` questions
> like what object is this a cons of?

s/cons/car/   my mind must have been elsewhere

alex goldman wrote:
> Robert Low wrote:
>>But what is car(cons(X,Y),X)? 
> It's a relation (whereas in Lips, it would be a function)

So it's just the statement that car of cons(X,Y) is X?
(To put it another way, the pair (Z,X) satisfies car(Z,X)
iff X is car(Z)?)

Robert Low wrote:

> alex goldman wrote:
>> Robert Low wrote:
>>>But what is car(cons(X,Y),X)?
>> It's a relation (whereas in Lips, it would be a function)
> 
> So it's just the statement that car of cons(X,Y) is X?


If the inference procedure "knew" about equality, we could write

car(cons(X, Y)) = X, or equivalently X = car(cons(X, Y))

In Prolog, it doesn't, so /one/ way to express "car" relation is like I did.

> (To put it another way, the pair (Z,X) satisfies car(Z,X)
> iff X is car(Z)?)

Er, no "iff", and we only defined car of arity 2.

Quoth "ken quirici" <kquirici@yahoo.com>:
> AFAIK there is no algorithm using recursion that can't be 'emulated'
> by one not using recursion.

Ackermann's function may be an exception; there do exist some
fundamentally recursive expressions where "emulation" doesn't work out
well.

The normal alternative to recursion is merely to hide it by the use of
a stack.  (FORTRAN folk know this well, as FORTRAN was very
recursion-unfriendly until quite recently.)

And while recursion is an abstraction that can cause confusion to
those new to it, the ways of hiding it tends to lead to code that is
more opaque than straightforward recursion would have been.
-- 
(format nil "~S@~S" "cbbrowne" "gmail.com")
http://linuxdatabases.info/info/finances.html
Rules of the  Evil Overlord #3. "My noble  half-brother whose throne I
usurped will be killed, not kept anonymously imprisoned in a forgotten
cell of my dungeon." <http://www.eviloverlord.com/>

"mountain man" <hobbit@southern_seaweed.com.op> wrote:
> "Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message 
> news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...
>
>> To say that recursion is not useful to solve part explosion problems
>> shows profound ignorance.
>
>
> 1) WTF is this critical inventory explosion problem?
> 2) How many organisations are experiencing this problem?

BOM explosion is a standard problem for any manufacturing or assembly
company.

Ford, GM, Daimler/Chrysler are the canonical examples of such
organizations.

A dealer orders a 2005 Magnum XI, with some set of requested features.

The order goes in, and gets recursively exploded into successively
more detailed sets of inventory requests.

You need a car; that means you need:
 - Chassis
 - Engine 
 - Drive train
 - Wheel assemblies, and everything to connect them to the drive train
 - Seats

The engine, then, is a subsystem that must itself be exploded into a
further bill of materials representing the components needed to build
the engine.

Stereo makers (Panasonic, Pioneer, Sony, Harmon Kardon, ...)  will
have somewhat simpler BOM explosions.  You may buy a stereo "system"
which consists of:

 - Receiver/Amp
 - DVD player
 - Tape deck
 - Speakers
 - Cabling

Each of which then explodes into a BOM that leads to drawing
inventory.

The explosion reverberates in a number of ways...
-- 
"cbbrowne","@","gmail.com"
http://linuxdatabases.info/info/emacs.html
"[In the first  lecture of a course on complexity  theory]. If I teach
this  course thoroughly  enough, none  of  you will  attempt the  exam
questions on  this topic, and I  shall consider this to  be a complete
success."  -- Arthur Norman

alex goldman wrote:
> Robert Low wrote:
>>So it's just the statement that car of cons(X,Y) is X?
> If the inference procedure "knew" about equality, we could write 
> car(cons(X, Y)) = X, or equivalently X = car(cons(X, Y))
> In Prolog, it doesn't, so /one/ way to express "car" relation is like I did.

Oh, OK, I see where I've been misinterpreting what you
wrote now.

Christopher Browne wrote:
>> The normal alternative to recursion is merely to hide it by the use
of
> a stack.  (FORTRAN folk know this well, as FORTRAN was very
> recursion-unfriendly until quite recently.)
>

Yes I mentioned that in connection w/ leftmost tree traversal. I
certainly didn't use a stack to hide the recursion- the stack was
my first choice. Or maybe I looked it up in a book.

> And while recursion is an abstraction that can cause confusion to
> those new to it, the ways of hiding it tends to lead to code that is
> more opaque than straightforward recursion would have been.

I have seen recursive algorithms that certainly left ME tangled up;
I can't remember what they were but they were the A->B;C->A;B->C;D->C;
A->D type of thing. I have a feeling that people sometimes try to do
everything by the most compact recursion possible and end up with
monstrously difficult programs (where by 'program' I mean the main
routine and all subroutines). In the world of commercial programming
that I inhabit code readability and maintainability and
understandability count for more than recursive compactness. I
hesitate actually to call it elegance, which was my first choice,
because the kind of thing I sketched out above is not really elegant,
is it?

Would it be fair to say that recursion uses the subroutine call
arguments to replace stack entries? If so, I would prefer the stack
as a kind of universally available (let's just say for now)
state-descriptor, rather than carrying the info around in my
routine-travel-bag. Although if there is a text floating around
somewhere that goes into more detail about recursion vs. non-recursion,
I would appreciate knowing about it. Always willing to turn the page.

There of course are arguments about whether recursion is more expensive
of computer time than non-recursion - I won't weigh in on that argument

Thanks.

Ken

mountain man wrote:

> "Kenneth Downs" <knode.wants.this@see.sigblock> wrote in message
> news:tuuel2-uph.ln1@pluto.downsfam.net...
>> mountain man wrote:
>>
>>> "Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message
>>> news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...
>>>
>>>> To say that recursion is not useful to solve part explosion problems
>>>> shows profound ignorance.
>>>
>>>
>>> 1) WTF is this critical inventory explosion problem?
>>
>> A widget is made of components.  Each component is made of other
>> components,
>> and so on and so on.  The nesting level is not defined ahead of time and
>> can go to arbitrary depths.
> 
> Thanks for the brief.
> 
> Yes, arbitary but not infinite depths, and once the maximum
> depth is chartered, the current entire instance of the problem
> can be flattened - no big deal.  Auto-regen flat structure as
> required.

Two objections from experience.

First, if you set the depth at N, somebody will need N+1.  They will need it
on Christmas Eve coinciding with your daughter's wedding.

Second, it is dangerous to expect to pass complete run-outs when information
changes because you lose the ability to keep transactions small.  Multiply
the run-outs by a high user count and you've got a major bottleneck.

> 
> Throw the max depth code into an automated exception alert
> to present on a queue to some workgroup that an instance has
> arisen where widget_id 123456789 has exceeded max depth.

See first objection above. 

Third objection is the dumb retail terminal.  Counter help says, "I can't
sell you that radio you are holding in your hand because the computer says
we don't have any."  The limit you set and the exceeding depth will be seen
by the users as an arbitrary and onerous.

> 
> 
>> Building a flat list of a complete parts explosion for an item therefore
>> is
>> a hassle.
> 
> If you dont know the depth it is, but you build
> a tool to determine the maximim depth first.
> 
> 
> In fact there are literally hundreds of alternative work-
> arounds to this type of problem without involving
> any form of esoteric generalised recursion theory.
> 

Agreed, you don't need anything esoteric, the solutions are well-known, it's
just they all contain the moral equivalent of a divide by zero.

> 
> 
>>> 2) How many organisations are experiencing this problem?
>>>
>>
>> All manufacturers in the world?
> 
> 
> Not the ones I've ever had anything to do with.
> 
> My main clients have been patent and trade mark attorneys
> and their IP management systems invariably generate these
> types of problems where relationships involve trees and
> their branches. EG:
> 
> Tracking the relationships between patent applications,
> especially divisional patents, that can have parents, which
> themselves are a divisional patent of another divisional, etc.
> sounds like the same form of problem.

Is it possible they are not hitting the system that hard?  Not a high volume
of transactions?  Sounds like for lawyers it would be no problem to explode
a hierarchy on each change, since they just don't change that often, no?

> 
> If you relied upon theory you'd have a problem.
> Fortunately there are viable practice-based
> alternatives in SQL.

???  



-- 
Kenneth Downs
Secure Data Software, Inc.
(Ken)nneth@(Sec)ure(Dat)a(.com)

"Christopher Browne" <cbbrowne@acm.org> wrote in message 
news:Lbphe.49341$B82.1595210@news20.bellglobal.com...


....[trim]...

> Each of which then explodes into a BOM that leads to drawing
> inventory.
>
> The explosion reverberates in a number of ways...


Thanks for the further detailed example.




Nice quote!


> "cbbrowne","@","gmail.com"
> http://linuxdatabases.info/info/emacs.html
> "[In the first  lecture of a course on complexity  theory]. If I teach
> this  course thoroughly  enough, none  of  you will  attempt the  exam
> questions on  this topic, and I  shall consider this to  be a complete
> success."  -- Arthur Norman


Heisenburg gave up working on theory of complexity and turbulence,
and retreated from that arena to take up academic studies in far more
mundane disciplines such as nuclear physics - freely admitting defeat.





Pete Brown
Falls Creek
Oz
www.mountainman.com.au/chaos.htm

mountain man wrote:

> 
> IMO there are at least 2 roads
> to database systems theory:
> the road of theory and
> the road of practice.
> 

You are in good company.  Aristotle believed all virtuous action was
informed by both theory and practice, and that to some extent they informed
each other.  Practice brought wisdom that theory might never obtain, and
what he called "meditation" on theory could inform practice in ways that
would never come up if a routine was always being followed.  But since we
don't study those "old guys" anymore....
 

-- 
Kenneth Downs
Secure Data Software, Inc.
(Ken)nneth@(Sec)ure(Dat)a(.com)

Centuries ago, Nostradamus foresaw when "VC" <boston103@hotmail.com> would write:
> "Jan Hidders" <jan.hidders@REMOVETHIS.pandora.be> wrote in message 
> news:xVQge.89347$4x.5404810@phobos.telenet-ops.be...
>> alex goldman wrote:
>>> While people who responded seem to disagree on whether SQL has recursion,
>>
>> ?? I didn't see any disagreement. What the different answers told you was 
>> that this differs per SQL standard and per implementation.
>>
>>> what about functors?
>>>
>>> For example, can you express something like this with SQL?
>>>
>>> for_any X Y : car(cons(X, Y), X)
>>
>> That depends on what you mean by "can express". Since SQL is a
>> query language in which you formulate queries over tables it can
>> only formulate queries over tables and not over functors. So in
>> that sense the answer is "no" but that observation is about as
>> interesting as the fact that SQL also cannot make coffee. If you
>> reformulate it as a statement about tables by, for example,
>> modeling car as a binary table and cons as a ternary table then you
>> *can* express this and for that you don't even need recursion.
>>
>> -- Jan Hidders
>
> It actually depends on what <alex goldman> means by
>
> a. 'Functor',  the word that has different meaning in different PLs/contexts
>
> b. car(cons(X,Y), X).  If it's Lisp,  the expression does not make sense. 
> If it's a Prolog 'functor', it does not make any sense either.

I expect he's talking about the ML notion of functor, which is the
type signature of a 'module.'

In C++, the analagous thing is a template, where, once you have
defined a template, you can apply it to various types.  

Thus, a template for a stack could be applied to various data types so
you can have stacks of various sorts of objects.  Similarly, a B-tree
template allows having various B-trees for various object types.

In Ada, Modula-3, and Common Lisp this is called "generics."

In Java, the most nearly analagous thing is called an abstract class.
In Objective C, they call things like this "protocols."  And come to
think of it, Keene's book on CLOS also uses the term "protocols" for
Common Lisp...

So a functor for a stack would be some expression of certain vital
data structures and functions, e.g.:

  - There's some place to store where the functions look to
    find the stack's objects.

  - There's some initialization function, which returns an
    empty stack.

  - There's a "push" function to put something on the stack

  - There's a "pop" function to pull an item off the stack

  - There's presumably some exception handling for cases of
    overflow (maybe) and underflow (for sure).

In ML, you characterize the API for such things as "modules."

The special "generic module" is known as a functor.

By using this, you can nail down definitions for important data
structures and algorithms via functors and modules, and then be
certain that code that uses them will be free of type errors.

Two contrasts...

 - Prolog, on the one hand, almost pretends to be type-free.

 - SQL, on the other hand, has wide variations in the degree
   to which typing is supported/noticed.

   At the most primitive end, SQLite takes the classic Tcl approach
   where every data type is actually just a string.

   The object/relational systems (PostgreSQL, Illustra) have a pretty
   strong idea about every bit of data having some sort of type, and
   being strict about what closure they do support.  For instance,
   setting ridiculous dates like February 30th is rejected...

   More typical is for there to be a mixture of strictness and
   weakness; most SQL systems aren't as strict about data typing,
   though not so little as SQLite...
-- 
let name="cbbrowne" and tld="gmail.com" in String.concat "@" [name;tld];;
http://linuxdatabases.info/info/linuxdistributions.html
"More computing sins are committed  in the name of efficiency (without
necessarily achieving it) than for any other single reason - including
blind stupidity."  -- W.A. Wulf

Christopher Browne wrote:

> 
> I expect he's talking about the ML notion of functor, which is the
> type signature of a 'module.'
> 

And since we are competing in misunderstanding, by ML you mean machine
learning, right? :-)

No, functor is usually defined in BNF grammars for first-order logic. For
example, in 
   car(cons(X,Y), X) 
car is a predicate, cons is a functor. A term is either a constant like
adam, a variable like X, or a functor like cons(X,Y) above. Sometimes the
term "function" is used instead of "functor", but I don't like it, because
it creates confusion. "Function" is better used for predicates that possess
certain properties (determinism)

Oops! "ken quirici" <kquirici@yahoo.com> was seen spray-painting on a wall:
> Christopher Browne wrote:
>> And while recursion is an abstraction that can cause confusion to
>> those new to it, the ways of hiding it tends to lead to code that is
>> more opaque than straightforward recursion would have been.
>
> I have seen recursive algorithms that certainly left ME tangled up;
> I can't remember what they were but they were the A->B;C->A;B->C;D->C;
> A->D type of thing. I have a feeling that people sometimes try to do
> everything by the most compact recursion possible and end up with
> monstrously difficult programs (where by 'program' I mean the main
> routine and all subroutines). In the world of commercial programming
> that I inhabit code readability and maintainability and
> understandability count for more than recursive compactness. I
> hesitate actually to call it elegance, which was my first choice,
> because the kind of thing I sketched out above is not really
> elegant, is it?

In mathematics, it is entirely common for proofs to use recursion.

"Proof by induction" is heavily used.  

Once someone is familiar with that, the use of recursion becomes just
another technique, and the result is both compact and readable.

If the inductive proof that your algorithm works has 4 statements,
then a recursive implementation is quite likely to have somewhere
around 4 statements.

Adding in a stack will make it WAY more complicated, and hide the
similarities between the proof and the implementation, thereby making
it enormously more difficult to be confident that you got it right.

> Would it be fair to say that recursion uses the subroutine call
> arguments to replace stack entries? If so, I would prefer the stack
> as a kind of universally available (let's just say for now)
> state-descriptor, rather than carrying the info around in my
> routine-travel-bag. Although if there is a text floating around
> somewhere that goes into more detail about recursion vs. non-recursion,
> I would appreciate knowing about it. Always willing to turn the page.

No, the converse is what is true.

Recursion is the more basic notion.

In many languages, stacks are used in either representation.  In ML,
it is common to use heap-based allocation in lieu of stacks; were it
not for that, I'd be able to call it "virtually universal" for them to
be essentially synonymous.

> There of course are arguments about whether recursion is more
> expensive of computer time than non-recursion - I won't weigh in on
> that argument

That falls TOTALLY into the realm of "implementational details."  

If your favorite compiler implements one or the other badly, then one
will be massively less efficient than the other.

In Scheme, the language design _requires_ handling tail recursive
functions efficiently with the result that coding using a "manual
stack" is quite likely to be MASSIVELY less efficient than utilizing
tail recursion.  With tail recursion, the function is known to be
"eating" arguments as fast as they are being generated, such that the
recursive call can be treated as a GOTO, and there is no need for any
stack.

Thus, faking recursion using a stack would consume ENORMOUS amounts of
additional resources for the (rather common) case of tail recursion.

In FORTRAN, the opposite is likely to be true.
-- 
output = ("cbbrowne" "@" "gmail.com")
http://linuxdatabases.info/info/postgresql.html
Rules of the Evil Overlord #73. "I will not agree to let the heroes go
free if they  win a rigged contest, even though  my advisors assure me
it is impossible for them to win." <http://www.eviloverlord.com/>

"Kenneth Downs" <knode.wants.this@see.sigblock> wrote in message 
news:qbiil2-164.ln1@pluto.downsfam.net...
> mountain man wrote:
>
>> "Kenneth Downs" <knode.wants.this@see.sigblock> wrote in message
>> news:tuuel2-uph.ln1@pluto.downsfam.net...
>>> mountain man wrote:
>>>
>>>> "Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message
>>>> news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...
>>>>
>>>>> To say that recursion is not useful to solve part explosion problems
>>>>> shows profound ignorance.
>>>>
>>>>
>>>> 1) WTF is this critical inventory explosion problem?
>>>
>>> A widget is made of components.  Each component is made of other
>>> components,
>>> and so on and so on.  The nesting level is not defined ahead of time and
>>> can go to arbitrary depths.
>>
>> Thanks for the brief.
>>
>> Yes, arbitary but not infinite depths, and once the maximum
>> depth is chartered, the current entire instance of the problem
>> can be flattened - no big deal.  Auto-regen flat structure as
>> required.
>
> Two objections from experience.
>
> First, if you set the depth at N, somebody will need N+1.  They will need 
> it
> on Christmas Eve coinciding with your daughter's wedding.


OK.  Set the depth at N + X, where N is the maximum depth
and X is your comfort buffer.


> Second, it is dangerous to expect to pass complete run-outs when 
> information
> changes because you lose the ability to keep transactions small.  Multiply
> the run-outs by a high user count and you've got a major bottleneck.


I dont understand what you mean by run-outs.
I suspect it has some form of relationship to baseball.


>> Throw the max depth code into an automated exception alert
>> to present on a queue to some workgroup that an instance has
>> arisen where widget_id 123456789 has exceeded max depth.
>
> See first objection above.


Throw max depth + N into the alert queue.
(Where N relfects your index of comfort).


> Third objection is the dumb retail terminal.  Counter help says, "I can't
> sell you that radio you are holding in your hand because the computer says
> we don't have any."  The limit you set and the exceeding depth will be 
> seen
> by the users as an arbitrary and onerous.


If the N+X limit was somehow exceeded, the item would be
automatically sitting on a centralised data integrity exception
queue.

It is probably important to mention here that IMO there are
thousands of possible data integrity exceptions that will enter
any production database system, no matter how well the data
structures and constraints have been defined.  Therefore an
automated data integrity exception series is often the first thing
constructed.



>>> Building a flat list of a complete parts explosion for an item therefore
>>> is
>>> a hassle.
>>
>> If you dont know the depth it is, but you build
>> a tool to determine the maximim depth first.
>>
>>
>> In fact there are literally hundreds of alternative work-
>> arounds to this type of problem without involving
>> any form of esoteric generalised recursion theory.
>>
>
> Agreed, you don't need anything esoteric, the solutions are well-known, 
> it's
> just they all contain the moral equivalent of a divide by zero.


That's what the theoreticians say,
but I dont believe them.  ;-)


>>>> 2) How many organisations are experiencing this problem?
>>>>
>>>
>>> All manufacturers in the world?
>>
>>
>> Not the ones I've ever had anything to do with.
>>
>> My main clients have been patent and trade mark attorneys
>> and their IP management systems invariably generate these
>> types of problems where relationships involve trees and
>> their branches. EG:
>>
>> Tracking the relationships between patent applications,
>> especially divisional patents, that can have parents, which
>> themselves are a divisional patent of another divisional, etc.
>> sounds like the same form of problem.
>
> Is it possible they are not hitting the system that hard?  Not a high 
> volume
> of transactions?  Sounds like for lawyers it would be no problem to 
> explode
> a hierarchy on each change, since they just don't change that often, no?

Correct, the inventory example would have a higher volume of
transactions than the attorney example, but the principle should
be applicable to either.

With very high volume of transactions the incremental "flattening"
of new stock (since last "flattening") may need to be scheduled
with a greater periodicity, or invoked per each new widget.






Pete Brown
Falls Creek
Oz
www.mountainman.com.au

mountain man wrote:
> mAsterdam wrote: 
>>mountain man wrote:
>>[snip "recursion useful to solve part explosion problems"]
>>
>>>In fact there are literally hundreds of alternative work-
>>>arounds to this type of problem without involving
>>>any form of esoteric generalised recursion theory.
>>
>><delurk>
>>
>>Just curious:
>>What is esoteric about it?
>>Or: What makes you look for alternatives?
>>>...
>>>If you relied upon theory you'd have a problem.
>>>Fortunately there are viable practice-based
>>>alternatives in SQL.
> 
> In my case practice based alternatives were engineered
> for many years before I became aware that generalised and
> theoretical treatments of the problem were being considered.
> 
> So its not that I went looking for alternatives, rather that in
> the early days I was not aware of any recursion theory.
> 
> IMO there are at least 2 roads
> to database systems theory:
> the road of theory and
> the road of practice.

The users of roman numbers could do
very well without 0 - at least that's
what their generations thought.
I suspect that in the early days of the change
to arab numbers they looked on 0 as being of value,
albeit theoretical.

Programming languages did put recursion
on their practical road back in the 1960's.

Patrick Herring <ph@anweald.co.uk> wrote in message news:<h8s9819ojcvqibkuugpv6uub76l7sua2um@4ax.com>...

> | A widget is made of components.  Each component is made of other components,
> | and so on and so on.  The nesting level is not defined ahead of time and
> | can go to arbitrary depths.
> 
> But never really does.

Does what?

Go to arbitrary depths like 2, for instance?

> But they've seen it since data processing began, and have solved it many
> times, usually by some adhoc hack.

AKA botch-up.

> he'll get a spec saying "allow for 5 nested levels" since the analyst
> can't imagine there being any more than that in the foreseeable future.

To allow thousands of millions of levels requires virtually the same
effort as to allow 5, and in the real world such analyst's assumptions
fail very often. I am tired of fixing similar things.

> That's what DP is like. Adding recursion to it would simply cause fear
> of the unknown in all those who never did recursion in their Cobol past,
> which is most of the managers.

Anybody might learn to use recursion in a few hours.

It was an everyday practice a lot of years before I was born.


Regards

See below:

"alex goldman" <hello@spamm.er> wrote in message 
news:1436952.HqgieSMmFo@yahoo.com...
> VC wrote:
>
>>
>> "Jan Hidders" <jan.hidders@REMOVETHIS.pandora.be> wrote in message
>> news:xVQge.89347$4x.5404810@phobos.telenet-ops.be...
>>> alex goldman wrote:
>>>> While people who responded seem to disagree on whether SQL has
>>>> recursion,
>>>
>>> ?? I didn't see any disagreement. What the different answers told you 
>>> was
>>> that this differs per SQL standard and per implementation.
>>>
>>>> what about functors?
>>>>
>>>> For example, can you express something like this with SQL?
>>>>
>>>> for_any X Y : car(cons(X, Y), X)
>>>
>>> That depends on what you mean by "can express". Since SQL is a query
>>> language in which you formulate queries over tables it can only 
>>> formulate
>>> queries over tables and not over functors. So in that sense the answer 
>>> is
>>> "no" but that observation is about as interesting as the fact that SQL
>>> also cannot make coffee. If you reformulate it as a statement about
>>> tables by, for example, modeling car as a binary table and cons as a
>>> ternary table then you *can* express this and for that you don't even
>>> need recursion.
>>>
>>> -- Jan Hidders
>>
>> It actually depends on what <alex goldman> means by
>>
>> a. 'Functor',  the word that has different meaning in different
>> PLs/contexts
>>
>> b. car(cons(X,Y), X).  If it's Lisp,  the expression does not make sense.
>> If it's a Prolog 'functor', it does not make any sense either.
>
> In the future, please add qualifiers like "to me" to silly statements like
> the above. Car of a cons, consisting of X and Y, is X.

Ah, so Prolog it is.  In this case, car(cons(X,Y), X) still does not make 
syntactical sense.  This string should be either :

assert( car(cons(X,Y), X)).

or exist as a line, terminated by a dot, in a file loaded  by 'consult'.

Now,  back to you assertion that the string of characters in question 
somehow possesses superior expressive power.  The string is nothing more but 
a Prolog way to describe a data structure ('compound term' in the Prolog 
jargon), roughly equivalent to a database relation.  Let's say we have a 
line like this:

point(X,Y,Z) or junk1(junk2(A, B, C), C).

Then 'point',  'junk1' or 'junk2 would be called 'functors' and X,Y,Z or A, 
B, C 'arguments'.

Now, you could ask a 'question' like:

junk1(junk2(1,2,3), X) and Prolog, using simple pattern matching would say 
"X=3".

By the same token,  given assert( car(cons(X,Y), X)). and saying something 
like

car( cons( cons( 1, cons( 2, nil )), cons( 3, cons( 4, nil )) ), X ).

would yield:

"X = cons(1, cons(2, nil))"

Big deal ...  In SQL, a 'question' like that could be expressed with a 
trivial select statement.

See below:


"alex goldman" <hello@spamm.er> wrote in message 
news:2406031.I2Scl5LCZd@yahoo.com...
> Christopher Browne wrote:
>
>>
>> I expect he's talking about the ML notion of functor, which is the
>> type signature of a 'module.'

No,  Prolog's notion of functor is just a fancy way to refer to the atom at 
the start of a stucture (aka compound term).  E.g. in

date(14, may, 2005), 'date' is a functor.

>>
>
> And since we are competing in misunderstanding, by ML you mean machine
> learning, right? :-)
>
> No, functor is usually defined in BNF grammars for first-order logic. For
> example, in
>   car(cons(X,Y), X)
> car is a predicate, cons is a functor. .

That is not correct.  In Prolog,  structures can be nested,  therefore, both 
'car' and 'cons'  (which by the way do not possess any special meaning per 
se) are 'functors'.

 Sometimes the
> term "function" is used instead of "functor", but I don't like it, because
> it creates confusion.

You right in not liking it since the word "function" simply does not exist 
in the Prolog vocabulary.

"Function" is better used for predicates that possess
> certain properties (determinism)

Please read , like,  a book or something on Prolog 101 before trying to 
mislead a lot of people.

VC wrote:
[...]

Would you go and troll somewhere else please?

Please see in-line:

"Christopher Browne" <cbbrowne@acm.org> wrote in message 
news:cpyhe.49787$B82.1717445@news20.bellglobal.com...
[...snipped ...]

[VC]
>> It actually depends on what <alex goldman> means by
>>
>> a. 'Functor',  the word that has different meaning in different 
>> PLs/contexts
>>
>> b. car(cons(X,Y), X).  If it's Lisp,  the expression does not make sense.
>> If it's a Prolog 'functor', it does not make any sense either.
>

[CB]
> I expect he's talking about the ML notion of functor, which is the
> type signature of a 'module.'

Well, it appears he is trying to talk about Prolog's functor.   An excerpt 
from Prolog's BNF:

....
<predicate>::=<atom>|<structure>
<structure>::=<atom>(<term list>)
<term list>::=<term>|<term list>,<term>
<term>::=<numeral>|<atom>|<variable>|<structure>

A 'functor' is just the atom from  Line 2 (in the structure definition). 
E.g.

likes(john, mary).

.... is a predicate of 'arity' 2  (two arguments);  at the time,  it's a 
structure whose functor is 'likes'.

Sometimes, in Prolog,  people use the 'functor' and 'predicate' 
interchangeably. Also, in some books,  an 'atom' is called a 'functor' with 
'arity' zero.   I am not sure what the point of using multiple labels for 
essentially the same thing is. Probably,  'functor' makes trivial stuff 
sound real important...

mountain man wrote:

> "Kenneth Downs" <knode.wants.this@see.sigblock> wrote in message
> news:qbiil2-164.ln1@pluto.downsfam.net...
>> mountain man wrote:
>>
>>> "Kenneth Downs" <knode.wants.this@see.sigblock> wrote in message
>>> news:tuuel2-uph.ln1@pluto.downsfam.net...
>>>> mountain man wrote:
>>>>
>>>>> "Alfredo Novoa" <alfredo_novoa@hotmail.com> wrote in message
>>>>> news:87t881l00onh3tibjbqvokll34kn2d67s9@4ax.com...
>>>>>
>>>>>> To say that recursion is not useful to solve part explosion problems
>>>>>> shows profound ignorance.
>>>>>
>>>>>
>>>>> 1) WTF is this critical inventory explosion problem?
>>>>
>>>> A widget is made of components.  Each component is made of other
>>>> components,
>>>> and so on and so on.  The nesting level is not defined ahead of time
>>>> and can go to arbitrary depths.
>>>
>>> Thanks for the brief.
>>>
>>> Yes, arbitary but not infinite depths, and once the maximum
>>> depth is chartered, the current entire instance of the problem
>>> can be flattened - no big deal.  Auto-regen flat structure as
>>> required.
>>
>> Two objections from experience.
>>
>> First, if you set the depth at N, somebody will need N+1.  They will need
>> it
>> on Christmas Eve coinciding with your daughter's wedding.
> 
> 
> OK.  Set the depth at N + X, where N is the maximum depth
> and X is your comfort buffer.

User will require N + X + 1, as you are getting on the plane for your
long-awaited vacation.

> 
> 
>> Second, it is dangerous to expect to pass complete run-outs when
>> information
>> changes because you lose the ability to keep transactions small. 
>> Multiply the run-outs by a high user count and you've got a major
>> bottleneck.
> 
> 
> I dont understand what you mean by run-outs.

Flattening. 



> 
> 
>>> Throw the max depth code into an automated exception alert
>>> to present on a queue to some workgroup that an instance has
>>> arisen where widget_id 123456789 has exceeded max depth.
>>
>> See first objection above.
> 
> 
> Throw max depth + N into the alert queue.
> (Where N relfects your index of comfort).

This is an after-the-fact fix, less robust than a system that allows
infinite nesting in theory, and is therefore bounded only by physical
resources.

> 
> 
>> Third objection is the dumb retail terminal.  Counter help says, "I can't
>> sell you that radio you are holding in your hand because the computer
>> says
>> we don't have any."  The limit you set and the exceeding depth will be
>> seen
>> by the users as an arbitrary and onerous.
> 
> 
> If the N+X limit was somehow exceeded, the item would be
> automatically sitting on a centralised data integrity exception
> queue.

Tell that to the customer at the counter who wants to buy the radio, "As
soon as we clear the data integrity exception queue we'll have you on your
way --- hey? Where'd he go?  Sir?  Do you want the radio?"

> 
> It is probably important to mention here that IMO there are
> thousands of possible data integrity exceptions that will enter
> any production database system, no matter how well the data
> structures and constraints have been defined.  Therefore an
> automated data integrity exception series is often the first thing
> constructed.
> 

Ouch.  Include me out.

> 
> 
>>>> Building a flat list of a complete parts explosion for an item
>>>> therefore is
>>>> a hassle.
>>>
>>> If you dont know the depth it is, but you build
>>> a tool to determine the maximim depth first.
>>>
>>>
>>> In fact there are literally hundreds of alternative work-
>>> arounds to this type of problem without involving
>>> any form of esoteric generalised recursion theory.
>>>
>>
>> Agreed, you don't need anything esoteric, the solutions are well-known,
>> it's
>> just they all contain the moral equivalent of a divide by zero.
> 
> 
> That's what the theoreticians say,
> but I dont believe them.  ;-)

Which theoretician says this?  This is worth a subthread.

> 
> 
>>>>> 2) How many organisations are experiencing this problem?
>>>>>
>>>>
>>>> All manufacturers in the world?
>>>
>>>
>>> Not the ones I've ever had anything to do with.
>>>
>>> My main clients have been patent and trade mark attorneys
>>> and their IP management systems invariably generate these
>>> types of problems where relationships involve trees and
>>> their branches. EG:
>>>
>>> Tracking the relationships between patent applications,
>>> especially divisional patents, that can have parents, which
>>> themselves are a divisional patent of another divisional, etc.
>>> sounds like the same form of problem.
>>
>> Is it possible they are not hitting the system that hard?  Not a high
>> volume
>> of transactions?  Sounds like for lawyers it would be no problem to
>> explode
>> a hierarchy on each change, since they just don't change that often, no?
> 
> Correct, the inventory example would have a higher volume of
> transactions than the attorney example, but the principle should
> be applicable to either.
> 
> With very high volume of transactions the incremental "flattening"
> of new stock (since last "flattening") may need to be scheduled
> with a greater periodicity, or invoked per each new widget.
> 
> 

Methinks our different approaches are heavily influenced by our situations
on the ground.  As a parting argument I would still want to use a more
robust solution, because it will work in the light and heavy load, while
the one built for the light load can't scale.

-- 
Kenneth Downs
Secure Data Software, Inc.
(Ken)nneth@(Sec)ure(Dat)a(.com)

Clinging to sanity, Christopher Browne <cbbrowne@acm.org> mumbled into her beard:
> Quoth "ken quirici" <kquirici@yahoo.com>:
>> AFAIK there is no algorithm using recursion that can't be 'emulated'
>> by one not using recursion.
>
> Ackermann's function may be an exception; there do exist some
> fundamentally recursive expressions where "emulation" doesn't work out
> well.

I said this badly.

There is a class of functions termed as "primitive recursive
functions" which are defined using recursion, but which may be
implemented using only "for loops."  Power function and GCD, are
examples of primitive recursive functions.

You may have found that all of the recursive algorithms _that you have
looked_ at  were primitive recursive, thereby making them particularly
amenable to non-recursive alternatives.

There was a theory widely believed at the turn of the last century
that all functions were, in fact, primitive recursive.  

Ackermann provided the counterexample named after him back in 1928,
thereby proving such beliefs to be false.

At some level, computers implement everything via state machines, and
so there is a sense in which they're "not doing things in a manner
that is aware of recursion."  But that is normally as blandly useless
as is the use of "Turing equivalence" to argue that any programming language is as
good as any other.  

There is _some_ sense in which it is true, but immediately that you
have to read and write code, that sense disappears.
-- 
let name="cbbrowne" and tld="gmail.com" in String.concat "@" [name;tld];;
http://linuxdatabases.info/info/slony.html
"When we write programs that "learn", it turns out that we do and they
don't." -- Alan Perlis

Martha Stewart called it a Good Thing when "mountain man" <hobbit@southern_seaweed.com.op> wrote:
> So its not that I went looking for alternatives, rather that in
> the early days I was not aware of any recursion theory.

You mean to say that you have been doing database work since the
1960s, and have been ignoring theory ever since?

You'd pretty much have to go back to the 1950s for recursion not to be
available...
-- 
(format nil "~S@~S" "cbbrowne" "gmail.com")
http://linuxdatabases.info/info/linuxdistributions.html
Rules of the  Evil Overlord #60. "My five-year-old  child advisor will
also  be asked to  decipher any  code I  am thinking  of using.  If he
breaks the code  in under 30 seconds, it will not  be used. Note: this
also applies to passwords." <http://www.eviloverlord.com/>

VC wrote:

> A 'functor' is just the atom from  Line 2 (in the structure definition).
> E.g.
> 
> likes(john, mary).
> 
> ... is a predicate of 'arity' 2  (two arguments);  at the time,  it's a
> structure whose functor is 'likes'.

Well, that's one way to understand the grammar and the place of `functor' in
it. The way Russel & Norvig define it in Artificial Intelligence the Modern
Approach, predicate is not a [kind of a] functor, and a functor is not a
[kind of a] predicate. Actually AIMA uses "function" instead of "functor",
which you claimed no one ever does.

It's interesting that just yesterday you said that   car(cons(X, Y), X) 
"does not make any sense", and today you know the one and only true way of
Prolog. Now, scram, troll.

alex goldman wrote:
> 
> It's interesting that just yesterday you said that   car(cons(X, Y), X) 
> "does not make any sense", and today you know the one and only true way of
> Prolog. Now, scram, troll.

VC has a rather good track record of making interesting and useful 
postings, whereas your speciality seems to be asking rather vague 
questions and then getting into arguments with people who actually try 
to make sense of them.

*plonk*

-- Jan Hidders

Dear VC,

> Sometimes, in Prolog,  people use the 'functor' and 'predicate' 
> interchangeably.

Who are these miscreants?

> I am not sure what the point of using multiple labels for 
> essentially the same thing is.

None.

Best wishes,

Bill

Jan Hidders wrote:

> alex goldman wrote:
>> 
>> It's interesting that just yesterday you said that   car(cons(X, Y), X)
>> "does not make any sense", and today you know the one and only true way
>> of Prolog. Now, scram, troll.
> 
> VC has a rather good track record of making interesting and useful
> postings, whereas your speciality seems to be asking rather vague 
> questions and then getting into arguments with people who actually try
> to make sense of them.

Sometimes, a person asking questions might know that some answers are quite
incorrect.

For instance, someone asking whether SQL has functors might know that having
functors is a big deal. First-order logic without functors is far less
expressive. The restricted language is called Datalog. The inference in
Datalog is decidable and the inference in First-order logic isn't.

When someone like you gives an obviously misinformed "answer" that having
functors is as interesting as whether SQL can make coffee, you should be
grateful when I take time to point that out
<message-id:3907907.uYUagk22Ws@yahoo.com>

But I can see that you choose to act upset instead.

OTOH VC is just a plain insulting troll, as anyone reading this thread in
chronological order can tell. He claimed "car(cons(X,Y), X). " does not
make any sense (not to him, just not any sense, period). 
Or take this insulting little nugget:

> Please read , like,  a book or something on Prolog 101 before trying 
> to  mislead a lot of people.

Which the VC troll wrote in response to "[In first-order logic, the term]
`function' is better used for predicates that possess certain properties
(determinism)"

I think the insulting ignoramus should tell that to Quinlan too:

http://www-ai.ijs.si/~ilpnet2/systems/ffoil.html

alex goldman wrote:
> First-order logic without functors is far less
> expressive. The restricted language is called Datalog. The inference
in
> Datalog is decidable and the inference in First-order logic isn't.

For crist sake, what "functor" in logic are you talking about? There is
no such index entry in the Mendelson's "Intro to Mathematical Logic"
textbook. Mathworld  "functor" entry indicates that it's category
theory concept.

Mikito Harakiri wrote:
> 
> For crist sake, what "functor" in logic are you talking about? There is
> no such index entry in the Mendelson's "Intro to Mathematical Logic"
> textbook.

Try looking for "function symbol".

-- Jan Hidders

Jan Hidders wrote:
> Mikito Harakiri wrote:
> >
> > For crist sake, what "functor" in logic are you talking about?
There is
> > no such index entry in the Mendelson's "Intro to Mathematical
Logic"
> > textbook.
>
> Try looking for "function symbol".

Thank you for clarifying that, Jan. Returning to OP question:

"AFAIK the expressive power of modern state-of-art database software
like
Oracle and PostgreSQL still falls far behind first-order logic: it
essentially doesn't have functors or recursion."

In SQL DBMSs aren't "function symbols" just UDFs (aka stored
procedures), then? Including fairly recent incarnations: table
functions?

On Mon, 16 May 2005 09:35:57 -0700, alex goldman <hello@spamm.er> said:
> First-order logic without functors is far less expressive. The
> restricted language is called Datalog. The inference in Datalog is
> decidable and the inference in First-order logic isn't.

If by "functor" you mean "function symbol", you seem to be suggesting
that validity in first-order logic without function symbols is decidable
(it isn't).  Am I misreading you?

Chris Menzel

Mikito Harakiri wrote:
> 
> Returning to OP question:
> 
> "AFAIK the expressive power of modern state-of-art database software 
> like Oracle and PostgreSQL still falls far behind first-order logic:
> it essentially doesn't have functors or recursion."
> 
> In SQL DBMSs aren't "function symbols" just UDFs (aka stored 
> procedures), then? Including fairly recent incarnations: table 
> functions?

The way that function symbols are interpreted in Prolog and what gives 
them their expressive power in combination with recursion is more like 
what you would call a tuple constructor. So a term like f(x,y) 
represents a binary tuple with fields x and y and a label f that 
distinguishes it from g(x,y). So a better analogue would be user-defined 
record types where the type system allows arbitrary deep nesting or 
recursive types.

-- Jan Hidders

Just to prevent spreading mis-information:

> > alex goldman wrote:
[...skipped ...]

>. First-order logic without functors is far less
> expressive.

There is no FOL with 'functors'


>The restricted language is called Datalog. The inference in
> Datalog is decidable and the inference in First-order logic isn't.

Datalog is decidable precisely because it chucked Prolog's 'functor'.
Prolog is of course undecidable.

Please see in-line:

"Jan Hidders" <jan.hidders@REMOVETHIS.pandora.be> wrote in message 
news:IO4ie.92778$S43.5526623@phobos.telenet-ops.be...
> Mikito Harakiri wrote:
>>
>> For crist sake, what "functor" in logic are you talking about? There is
>> no such index entry in the Mendelson's "Intro to Mathematical Logic"
>> textbook.
>
> Try looking for "function symbol".
>
> -- Jan Hidders

Well,  if we are talking about FOL,  then a "functor" simply is not in FOL's 
vocabulary ("function symbol" of course is).

In category theory, functors are mappings between "small" categories.

In computer science, the word functor's been ab/mis-used so much that there 
is little in common between its uses in different computer languages. 
Prolog's usage is remarkably funny especially taking into account that the 
latter operates with relations/predicates,  not functions. 

Jan Hidders wrote:
> Mikito Harakiri wrote:
> >
> > Returning to OP question:
> >
> > "AFAIK the expressive power of modern state-of-art database
software
> > like Oracle and PostgreSQL still falls far behind first-order
logic:
> > it essentially doesn't have functors or recursion."
> >
> > In SQL DBMSs aren't "function symbols" just UDFs (aka stored
> > procedures), then? Including fairly recent incarnations: table
> > functions?
>
> The way that function symbols are interpreted in Prolog and what
gives
> them their expressive power in combination with recursion is more
like
> what you would call a tuple constructor. So a term like f(x,y)
> represents a binary tuple with fields x and y and a label f that
> distinguishes it from g(x,y). So a better analogue would be
user-defined
> record types where the type system allows arbitrary deep nesting or
> recursive types.

I'm not sure I see the significance of nesting, although I seem to get
a feeling why genericity of record type is a big deal. Table function
output is defined in terms of static object type. I wonder if any RDBMS
allows "generic" table functions, where I can declare the type of the
output relation on the fly. Among the other things, it would allow to
define relational operators in terms of table functions. In particular,
one could write his own join method as table function!

Please see below:

"Mikito Harakiri" <mikharakiri_nospaum@yahoo.com> wrote in message 
news:1116265939.405452.181220@o13g2000cwo.googlegroups.com...
>
> Jan Hidders wrote:
>> Mikito Harakiri wrote:
>> >
>> > For crist sake, what "functor" in logic are you talking about?
> There is
>> > no such index entry in the Mendelson's "Intro to Mathematical
> Logic"
>> > textbook.
>>
>> Try looking for "function symbol".
>
> Thank you for clarifying that, Jan. Returning to OP question:
>
> "AFAIK the expressive power of modern state-of-art database software
> like
> Oracle and PostgreSQL still falls far behind first-order logic: it
> essentially doesn't have functors or recursion."
>
> In SQL DBMSs aren't "function symbols" just UDFs (aka stored
> procedures), then? Including fairly recent incarnations: table
> functions?
>

Using the word "function symbol" with respect to the Prolog data structure 
makes as much sense as the "functor" but that's the jargon people use. 
Whatever you call the beast, it's just a data structure label, not much 
different from say a C/C++ structure variable name.

As to the expressive power,  let's take for instance Datalog,  a decidable 
subset of Prolog without structures.  Datalog's expressive power is 
equivalent to that of relational algebra + recursion. E.g. a row in the 
Oracle demo table 'Emp(id int, name varchar(10), salary int)' might be 
represented by the following Datalog "fact":

emp(1234, john, 120000).

Datalog's relation/predicate maps to a relational table.  Now, to find out 
the employee name and salary knowing his id,  you'd ask this:

emp(1234, N, S).

.... which is the same as SELECT name, salary FROM emp WHERE Id=1234;

Since all the major databases implement some form of recursive query (DB2 
amd Yukon WITH....UNION ALL,  and Oracle CONNECT BY),  SQL's expressive 
power equals and even exceeds Datalog's since the latter does not even 
implemet arithmetic addition (it would have made it undecidable), let alone 
more complicated stuff.

If you are curious about this sort of things,  you might take a look at the 
XSB Prolog database interface ( 
http://www.cs.sunysb.edu/~sbprolog/manual2/node69.html ).

VC 

In article <1116283418.903814.273940@f14g2000cwb.googlegroups.com>, Mikito Harakiri wrote:
> 
> Jan Hidders wrote:
>> Mikito Harakiri wrote:
>> >
>> > Returning to OP question:
>> >
>> > "AFAIK the expressive power of modern state-of-art database
> software
>> > like Oracle and PostgreSQL still falls far behind first-order
> logic:
>> > it essentially doesn't have functors or recursion."
>> >
>> > In SQL DBMSs aren't "function symbols" just UDFs (aka stored
>> > procedures), then? Including fairly recent incarnations: table
>> > functions?
>>
>> The way that function symbols are interpreted in Prolog and what
> gives
>> them their expressive power in combination with recursion is more
> like
>> what you would call a tuple constructor. So a term like f(x,y)
>> represents a binary tuple with fields x and y and a label f that
>> distinguishes it from g(x,y). So a better analogue would be
> user-defined
>> record types where the type system allows arbitrary deep nesting or
>> recursive types.
> 
> I'm not sure I see the significance of nesting, although I seem to get
> a feeling why genericity of record type is a big deal.
 
Nesting is not significant; it's allowing data structures to express
choice that increases the expressive power.  Without that, database
developers have to resort to kludges like NULL or excessively complex
relational decompositions to deal with missing or optional data.

Simon Taylor.

In article <o5-dnaR_h4DiwhTfRVn-uQ@comcast.com>, VC wrote:
>> Thank you for clarifying that, Jan. Returning to OP question:
>>
>> "AFAIK the expressive power of modern state-of-art database software
>> like
>> Oracle and PostgreSQL still falls far behind first-order logic: it
>> essentially doesn't have functors or recursion."
> 
> As to the expressive power,  let's take for instance Datalog,  a decidable 
> subset of Prolog without structures.  Datalog's expressive power is 
> equivalent to that of relational algebra + recursion.

....
 
> Since all the major databases implement some form of recursive query (DB2 
> amd Yukon WITH....UNION ALL,  and Oracle CONNECT BY),  SQL's expressive 
> power equals and even exceeds Datalog's since the latter does not even 
> implemet arithmetic addition (it would have made it undecidable), let alone 
> more complicated stuff.

Pure Datalog is a tool for proving theorems about the expressiveness
of different query languages.  No-one would use pure Datalog as a 
serious query language; they would use something much more expressive.
For example, the Aditi deductive database will be able to use the full
power of the Mercury programming language in queries.

SQL with recursive extensions may be able to express all queries
expressible in Datalog (I haven't seen a proof), but in all but very
simple cases it won't be at all convenient.  Queries that would
naturally be written as mutually recursive predicates in Datalog
would most likely be very painful to write in SQL.

Simon Taylor.

"alex goldman" <hello@spamm.er> wrote in message
news:25978468.7Z4LEkyPSR@yahoo.com...
> Nilsson's book [1] talks about using first-order logic (and its subsets)
as
> the language for deductive databases. The book is 10 years old, and yet,
> AFAIK the expressive power of modern state-of-art database software like
> Oracle and PostgreSQL still falls far behind first-order logic: it
> essentially doesn't have functors or recursion. Does anyone know why?
>
> [1] http://www.ida.liu.se/~ulfni/lpp/


What do you mean by "the expressive power of ...database software" ?
I assume you meant "the expressive power of  data (sub)language".

1) functors
They are eliminated in the first step of the "normalization" process.
See Codd 1970 paper ( http://www.scism.sbu.ac.uk/~rmkemp/codd1970.pdf )
The semantic in Prolog  and deductive databases is based on the Herbrand
universe and LFP (least fixpoint).
Existence of functors mean infinite domains, which mean quantifiers cannot
always be eliminated.

2) recursion
There are many places for recursion:
- in a language like Java, C/C++, Pascal, Cobol , etc. used in conjunction
with the DBMS
- in the language of stored procedures (PL/SQL, Java, etc.)
- in the data (sub)language,  in the definition of a view for example.

"Christopher Browne" <cbbrowne@acm.org> wrote in message 
news:8jUhe.527$dS3.209076@news20.bellglobal.com...
> Martha Stewart called it a Good Thing when "mountain man" 
> <hobbit@southern_seaweed.com.op> wrote:
>> So its not that I went looking for alternatives, rather that in
>> the early days I was not aware of any recursion theory.
>
> You mean to say that you have been doing database work since the
> 1960s, and have been ignoring theory ever since?
>
> You'd pretty much have to go back to the 1950s for recursion not to be
> available...


What I mean to say is that, aside from brief encounters with
shoe-boxes full of punch cards in the early days, and the
theory associated with programming dinosaurs, my bread
and butter has been derived from the management of
database systems + application software + development
+ change management.

Only in recent years did I become interested in the theory
associated with various aspects database systems.




Pete Brown
Falls Creek
Oz
www.mountainman.com.au

> "Kenneth Downs" <knode.wants.this@see.sigblock> wrote in message 
> news:6tcll2-l9l.ln1@pluto.downsfam.net...
>> mountain man wrote:

> Methinks our different approaches are heavily influenced by our situations
> on the ground.


Naturally.


> As a parting argument I would still want to use a more
> robust solution, because it will work in the light and heavy load, while
> the one built for the light load can't scale.

If one were always given the luxury of selection
and choice then of course, there exists many solutions
that are more "robust" than the example I used.

So in this sense, I dont think we disagree.



However, as a general principle, I cannot agree
with your assessment of the management of all
forms of data integrity exceptions.


>> It is probably important to mention here that IMO there are
>> thousands of possible data integrity exceptions that will enter
>> any production database system, no matter how well the data
>> structures and constraints have been defined.  Therefore an
>> automated data integrity exception series is often the first thing
>> constructed.
>>
>
> Ouch.  Include me out.

Let us assume you did not write the database schema
and the applicatrion software code--- let us assume
you have inherited a system.

(ie: of course if you were to build a system entirely
yourself then it would be without any form of exceptions ;-)


So, say you were the IT manager of a production site
consistent of the following:

* RDBMS software from your vendor of choice.
* Application software package using this RDBMS


Do you still insist that database integrity exceptions
are unimportant, and if not, how are you proposing
to identify such exceptions, especially the really bad
examples, other than by routine automated tasks?





Pete Brown
Falls Creek
Oz
www.mountainman.com.au

"mAsterdam" <mAsterdam@vrijdag.org> wrote in message 
news:42870df1$0$64598$e4fe514c@news.xs4all.nl...

....[trim]...

> Programming languages did put recursion
> on their practical road back in the 1960's.


Thanks for that historical perspective.

When I was referring to "current theory" of recursion
I was thinking about articles such as these, for example.

http://xxx.lanl.gov/find/grp_cs,grp_math/1/ti:+recursion/0/1/0/all/0/1?per_page=100






Pete Brown
Fallas Creek
Oz
www.mountainman.com.au

"Simon Taylor" <stayl@cs.mu.oz.au> wrote in message 
news:428982b5$1@news.unimelb.edu.au...
> Nesting is not significant; it's allowing data structures to express
> choice that increases the expressive power.

Could you please elaborate on this one ?

>Without that, database
> developers have to resort to kludges like NULL or excessively complex
> relational decompositions to deal with missing or optional data.

And on this one too ?  With an example if possible ...
>
> Simon Taylor.

Thanks. 

"mAsterdam" <mAsterdam@vrijdag.org> wrote:
 in message news:42870df1$0$64598$e4fe514c@news.xs4all.nl...
> mountain man wrote:

>> IMO there are at least 2 roads
>> to database systems theory:
>> the road of theory and
>> the road of practice.
>
> The users of roman numbers could do
> very well without 0 - at least that's
> what their generations thought.
> I suspect that in the early days of the change
> to arab numbers they looked on 0 as being of value,
> albeit theoretical.


As an aside, AFAIK the arab numbers are Indian.

Brahmagupta's (b.598 A.D) treatise Brahma-sputa-siddhanta
was translated into Arabic under the title Sind Hind.

For several centuries this translation mained a standard
text of reference in the Arab world. It was from this
translation of an Indian text on Mathematics that the
Arab mathematicians perfected the decimal system and
gave the world its current system of enumeration which
we call the Arab numerals, which are originally Indian
numerals.

Sorry about the tangentiation,




Pete Brown
Falls Creek
Oz
www.mountainman.com.au

In article <p56dnTmpwdoJWxTfRVn-sQ@comcast.com>, VC wrote:
> 
> "Simon Taylor" <stayl@cs.mu.oz.au> wrote in message 
> news:428982b5$1@news.unimelb.edu.au...
>> Nesting is not significant; it's allowing data structures to express
>> choice that increases the expressive power.
> 
> Could you please elaborate on this one ?

Nested data where there is no choice between function symbols
can always be flattened into 1NF.

>>Without that, database
>> developers have to resort to kludges like NULL or excessively complex
>> relational decompositions to deal with missing or optional data.
> 
> And on this one too ?  With an example if possible ...

Taking the example from
<http://web.onetel.com/~hughdarwen/TheThirdManifesto/Missing-info-without-nulls.pdf>

The relational decomposition as described in that presentation is a
poor solution because it makes queries more complex, the integrity
constraints required can't be implemented in any available RDBMS,
and probably couldn't be implemented efficiently anyway.

So, the missing or optional data needs to be embedded in the table
somehow.

With NULLs:
--Table Person_Info ---------------------------------
Id	Name	Job_Info		Salary
-----------------------------------------------------
1234	"Anne"	"lawyer"		10000
1235	"Boris"	"banker"		NULL
1236	"Cindy"	NULL			70000
1237	"Dave"	NULL			NULL
-----------------------------------------------------

With special values:
--Table Person_Info ---------------------------------
Id	Name	Job_Info		Salary
-----------------------------------------------------
1234	"Anne"	"lawyer"		10000
1235	"Boris"	"banker"		-1
1236	"Cindy"	"unknown"		70000
1237	"Dave"	"unemployed"		0
-----------------------------------------------------

With function symbols / functors / algebraic data types:
---Table Person_Info --------------------------------
Id	Name	Job_Info		Salary
-----------------------------------------------------
1234	"Anne"	employed("lawyer")	salary(10000)
1235	"Boris"	employed("banker")	unknown
1236	"Cindy"	unknown			salary(70000)
1237	"Dave"	unemployed		unsalaried
-----------------------------------------------------

Using NULLs, if there are multiple reasons for a field to be
missing, it is impossible to distinguish between them.

Special values are a poor solution because queries can mistake
them for real data.

With function symbols, any number of cases can be handled.
When programming a query the programmer must explicitly handle
the unknown or inapplicable values; they don't automatically
propagate themselves through the query like NULLs, and they
can't be mistaken for real data.

In short, the version using function symbols has much more of
a "say what you mean" flavour to it, and is simpler and more
robust for it.  The downside is that it is more difficult for
application languages like C and Java to work with.

Simon Taylor.

Christopher Browne wrote:
> Oops! "ken quirici" <kquirici@yahoo.com> was seen spray-painting on a
wall:
> > Christopher Browne wrote:
> >> And while recursion is an abstraction that can cause confusion to
> >> those new to it, the ways of hiding it tends to lead to code that
is
> >> more opaque than straightforward recursion would have been.
> >
> > I have seen recursive algorithms that certainly left ME tangled up;
> > I can't remember what they were but they were the
A->B;C->A;B->C;D->C;
> > A->D type of thing. I have a feeling that people sometimes try to
do
> > everything by the most compact recursion possible and end up with
> > monstrously difficult programs (where by 'program' I mean the main
> > routine and all subroutines). In the world of commercial
programming
> > that I inhabit code readability and maintainability and
> > understandability count for more than recursive compactness. I
> > hesitate actually to call it elegance, which was my first choice,
> > because the kind of thing I sketched out above is not really
> > elegant, is it?
>
> In mathematics, it is entirely common for proofs to use recursion.
>
> "Proof by induction" is heavily used.
>
> Once someone is familiar with that, the use of recursion becomes just
> another technique, and the result is both compact and readable.
>
> If the inductive proof that your algorithm works has 4 statements,
> then a recursive implementation is quite likely to have somewhere
> around 4 statements.
>
> Adding in a stack will make it WAY more complicated, and hide the
> similarities between the proof and the implementation, thereby making
> it enormously more difficult to be confident that you got it right.
>
> > Would it be fair to say that recursion uses the subroutine call
> > arguments to replace stack entries? If so, I would prefer the stack
> > as a kind of universally available (let's just say for now)
> > state-descriptor, rather than carrying the info around in my
> > routine-travel-bag. Although if there is a text floating around
> > somewhere that goes into more detail about recursion vs.
non-recursion,
> > I would appreciate knowing about it. Always willing to turn the
page.
>
> No, the converse is what is true.
>
> Recursion is the more basic notion.
>
> In many languages, stacks are used in either representation.  In ML,
> it is common to use heap-based allocation in lieu of stacks; were it
> not for that, I'd be able to call it "virtually universal" for them
to
> be essentially synonymous.
>
> > There of course are arguments about whether recursion is more
> > expensive of computer time than non-recursion - I won't weigh in on
> > that argument
>
> That falls TOTALLY into the realm of "implementational details."
>
> If your favorite compiler implements one or the other badly, then one
> will be massively less efficient than the other.
>
> In Scheme, the language design _requires_ handling tail recursive
> functions efficiently with the result that coding using a "manual
> stack" is quite likely to be MASSIVELY less efficient than utilizing
> tail recursion.  With tail recursion, the function is known to be
> "eating" arguments as fast as they are being generated, such that the
> recursive call can be treated as a GOTO, and there is no need for any
> stack.
>
> Thus, faking recursion using a stack would consume ENORMOUS amounts
of
> additional resources for the (rather common) case of tail recursion.
>
> In FORTRAN, the opposite is likely to be true.
> --
> output = ("cbbrowne" "@" "gmail.com")
> http://linuxdatabases.info/info/postgresql.html
> Rules of the Evil Overlord #73. "I will not agree to let the heroes
go
> free if they  win a rigged contest, even though  my advisors assure
me
> it is impossible for them to win." <http://www.eviloverlord.com/>

Thanks for the reply.

Would the Aho book on Foundations of computer science be a good place
to find out some of the stuff you were talking about?

Thanks.

Ken

Please see in-line:

Simon Taylor wrote:
> In article <p56dnTmpwdoJWxTfRVn-sQ@comcast.com>, VC wrote:
> >
> > "Simon Taylor" <stayl@cs.mu.oz.au> wrote in message
> > news:428982b5$1@news.unimelb.edu.au...
> >> Nesting is not significant; it's allowing data structures to
express
> >> choice that increases the expressive power.
> >
> > Could you please elaborate on this one ?
>
> Nested data where there is no choice between function symbols
> can always be flattened into 1NF.

Sorry,  could you give an example ?


>
> With function symbols / functors / algebraic data types:
> ---Table Person_Info --------------------------------
> Id	Name	Job_Info		Salary
> -----------------------------------------------------
> 1234	"Anne"	employed("lawyer")	salary(10000)
> 1235	"Boris"	employed("banker")	unknown
> 1236	"Cindy"	unknown			salary(70000)
> 1237	"Dave"	unemployed		unsalaried
> -----------------------------------------------------
>
> Using NULLs, if there are multiple reasons for a field to be
> missing, it is impossible to distinguish between them.
>
> Special values are a poor solution because queries can mistake
> them for real data.
>
> With function symbols, any number of cases can be handled.
> When programming a query the programmer must explicitly handle
> the unknown or inapplicable values; they don't automatically
> propagate themselves through the query like NULLs, and they
> can't be mistaken for real data.
>
> In short, the version using function symbols has much more of
> a "say what you mean" flavour to it, and is simpler and more
> robust for it.  The downside is that it is more difficult for
> application languages like C and Java to work with.


But using database user-defined types you can achieve precisely the
same.  E.g. in Oracle:

CREATE OR REPLACE TYPE salary AS OBJECT ( ...);

insert into emp values(1000, 'sam', salary('1000'));
....
insert into emp values(1010, 'nick', salary('unemployed'));


The same can be done in DB2 or any other database (Postgress)
implementing user-defined types (also known as 'object' types).

Admittedly,  the syntax is not as nice,  but expressive power is there
;)

VC




> 
> Simon Taylor.

Simon Taylor wrote:
> In article <1116283418.903814.273940@f14g2000cwb.googlegroups.com>, Mikito Harakiri wrote:
>>Jan Hidders wrote:
>>>
>>>The way that function symbols are interpreted in Prolog and what gives
>>>them their expressive power in combination with recursion is more like
>>>what you would call a tuple constructor. So a term like f(x,y)
>>>represents a binary tuple with fields x and y and a label f that
>>>distinguishes it from g(x,y). So a better analogue would be user-defined
>>>record types where the type system allows arbitrary deep nesting or
>>>recursive types.
>>
>>I'm not sure I see the significance of nesting, although I seem to get
>>a feeling why genericity of record type is a big deal.
>  
> Nesting is not significant; it's allowing data structures to express
> choice that increases the expressive power.

I tend to disagree. Choice by itself can always be flattened, but 
arbitrary deep nesting cannot, so it does matter for the expressive 
power of the query language.

-- Jan Hidders

vc wrote:

> Just to prevent spreading mis-information:
> 
>> > alex goldman wrote:
> [...skipped ...]
> 
>>. First-order logic without functors is far less
>> expressive.
> 
> There is no FOL with 'functors'

Looks like this idiot doesn't even realize the relation between Prolog and
FOL. How much humiliation can he take?

http://clip.dia.fi.upm.es/~logalg/slides/5_autded/node1.html
http://www.cee.hw.ac.uk/~alison/ai3notes/subsection2_4_3_2.html

Enjoy

>>.First-order logic without functors is far less expressive. The 
>> restricted language is called Datalog. The inference in Datalog 
>> is decidable and the inference in First-order logic isn't. 
> 
> Datalog is decidable precisely because it chucked Prolog's 'functor'.
> Prolog is of course undecidable.

How does poorly rephrasing something count as prevention of spreading of
mis-information (sic) ?

In-line:

"alex goldman" <hello@spamm.er> wrote in message 
news:1301963.fDU1I1y9sr@yahoo.com...
> vc wrote:
>
>> Just to prevent spreading mis-information:
>>
>>> > alex goldman wrote:
>> [...skipped ...]
>>
>>>. First-order logic without functors is far less
>>> expressive.
>>
>> There is no FOL with 'functors'
>
> Looks like this idiot doesn't even realize the relation between Prolog and
> FOL. How much humiliation can he take?
>
> http://clip.dia.fi.upm.es/~logalg/slides/5_autded/node1.html
> http://www.cee.hw.ac.uk/~alison/ai3notes/subsection2_4_3_2.html
>
> Enjoy
>
>>>.First-order logic without functors is far less expressive. The
>>> restricted language is called Datalog. The inference in Datalog
>>> is decidable and the inference in First-order logic isn't.
>>
>> Datalog is decidable precisely because it chucked Prolog's 'functor'.
>> Prolog is of course undecidable.
>
> How does poorly rephrasing something count as prevention of spreading of
> mis-information (sic) ?
>

Well,  the two web-sites <alex goldman>'s referring to are maintained by 
folks clearly influenced by the Prolog jargon ("computational logic" and 
"AI").

No standard mathematical logic handbook uses the word 'functor' as meaning a 
'function symbol' for a very good reason.

In order to cure yourself from Internet "education" ill effects, you might 
consider a trip to the nearest library and borrowing for example this book:

HB Enderton: A Mathematical Introduction to Logic, Academic Press, 1972

VC wrote:

> In order to cure yourself from Internet "education" ill effects, you might
> consider a trip to the nearest library and borrowing for example this
> book:
> 
> HB Enderton: A Mathematical Introduction to Logic, Academic Press, 1972

Again, the anonymous "VC" troll is trying to "educate" me.

You forgot to reply to this. Does Quinlan need to take Prolog 101?



OTOH VC is just a plain insulting troll, as anyone reading this thread in
chronological order can tell. He claimed "car(cons(X,Y), X). " does not
make any sense (not to him, just not any sense, period). 
Or take this insulting little nugget:

> Please read , like,  a book or something on Prolog 101 before trying 
> to  mislead a lot of people.

Which the VC troll wrote in response to "[In first-order logic, the term]
`function' is better used for predicates that possess certain properties
(determinism)"

I think the insulting ignoramus should tell that to Quinlan too:

http://www-ai.ijs.si/~ilpnet2/systems/ffoil.html

VC wrote:
> alex goldman wrote: 
>>vc wrote:
>>>Just to prevent spreading mis-information:
>>>>>alex goldman wrote:
....
>>Looks like this idiot doesn't even realize the relation between Prolog and
>>FOL. How much humiliation can he take?
....
>>>>.First-order logic without functors is far less expressive. The
>>>>restricted language is called Datalog. The inference in Datalog
>>>>is decidable and the inference in First-order logic isn't.
>>>
>>>Datalog is decidable precisely because it chucked Prolog's 'functor'.
>>>Prolog is of course undecidable.
>>
>>How does poorly rephrasing something count as prevention of spreading of
>>mis-information (sic) ?
> 
> Well,  the two web-sites <alex goldman>'s referring to are maintained by 
> folks clearly influenced by the Prolog jargon ("computational logic" and 
> "AI").
> 
> No standard mathematical logic handbook uses the word 'functor' as meaning a 
> 'function symbol' for a very good reason.
> 
> In order to cure yourself from Internet "education" ill effects, you might 
> consider a trip to the nearest library and borrowing for example this book:
> 
> HB Enderton: A Mathematical Introduction to Logic, Academic Press, 1972

Thank you for staying polite.

mountain man wrote:
> mAsterdam wrote:
>>mountain man wrote:
> 
>>>IMO there are at least 2 roads
>>>to database systems theory:
>>>the road of theory and
>>>the road of practice.
>>
>>The users of roman numbers could do
>>very well without 0 - at least that's
>>what their generations thought.
>>I suspect that in the early days of the change
>>to arab numbers they looked on 0 as being of value,
>>albeit theoretical.
> 
> As an aside, AFAIK the arab numbers are Indian.
> 
> Brahmagupta's (b.598 A.D) treatise Brahma-sputa-siddhanta
> was translated into Arabic under the title Sind Hind.
> 
> For several centuries this translation mained a standard
> text of reference in the Arab world. It was from this
> translation of an Indian text on Mathematics that the
> Arab mathematicians perfected the decimal system and
> gave the world its current system of enumeration which
> we call the Arab numerals, which are originally Indian
> numerals.
> 
> Sorry about the tangentiation,

Nice :-) tangentiate as much as you like.

mountain man wrote:
> mAsterdam wrote: 
>>Programming languages did put recursion
>>on their practical road back in the 1960's.
> 
> Thanks for that historical perspective.
> 
> When I was referring to "current theory" of recursion
> I was thinking about articles such as these, for example.
> 
> http://xxx.lanl.gov/find/grp_cs,grp_math/1/ti:+recursion/0/1/0/all/0/1?per_page=100

Wo! That's the heavy stuff. I browsed some of the articles but they were 
   all very math-introvert - the kind of material I only tend to really 
try to grasp when somebody I trust tells me it is worth my while. I am
not a mathematician, but when I put some effort into it (taking me a lot
more time than it would a mathematician) I do get it most of the time.
Could you point out a few which are?

| alfredo_novoa@hotmail.com (Alfredo Novoa) wrote:
|
| Patrick Herring <ph@anweald.co.uk> wrote in message news:<h8s9819ojcvqibkuugpv6uub76l7sua2um@4ax.com>...
| 
| > | A widget is made of components.  Each component is made of other components,
| > | and so on and so on.  The nesting level is not defined ahead of time and
| > | can go to arbitrary depths.
| > 
| > But never really does.
| 
| Does what?
| 
| Go to arbitrary depths like 2, for instance?

Go to unforeseeable depths for a good reason.

| > But they've seen it since data processing began, and have solved it many
| > times, usually by some adhoc hack.
| 
| AKA botch-up.

AKA "practical limitation of theoretical possibilities". A good
practical reason not to allow arbitrarily long chains of sub_part(X, Y)
is that the part table might be corrupt e.g. with a part being its own
sub_part, so you might get a loop. Easier to double the number you first
thought of as a practical limit than require the entire database to be
perfect at all times. It's not pretty but it does work.

| > he'll get a spec saying "allow for 5 nested levels" since the analyst
| > can't imagine there being any more than that in the foreseeable future.
| 
| To allow thousands of millions of levels requires virtually the same
| effort as to allow 5, and in the real world such analyst's assumptions
| fail very often. I am tired of fixing similar things.

In the UK we have the phrase "money for old rope" <g>.

| > That's what DP is like. Adding recursion to it would simply cause fear
| > of the unknown in all those who never did recursion in their Cobol past,
| > which is most of the managers.
| 
| Anybody might learn to use recursion in a few hours.
| 
| It was an everyday practice a lot of years before I was born.

Sure, I'm not disagreeing with you, just describing what happens in the
DP world, a world where Prolog ought to be really useful but never took
off. I suspect there are foundational reasons why not, along the lines
of the above.

--
Patrick Herring, http://www.anweald.co.uk/ph

In article <30pie.93684$yc.5551208@phobos.telenet-ops.be>, Jan Hidders wrote:
> Simon Taylor wrote:
>> In article <1116283418.903814.273940@f14g2000cwb.googlegroups.com>, Mikito Harakiri wrote:
>>>Jan Hidders wrote:
>>>>
>>>>The way that function symbols are interpreted in Prolog and what gives
>>>>them their expressive power in combination with recursion is more like
>>>>what you would call a tuple constructor. So a term like f(x,y)
>>>>represents a binary tuple with fields x and y and a label f that
>>>>distinguishes it from g(x,y). So a better analogue would be user-defined
>>>>record types where the type system allows arbitrary deep nesting or
>>>>recursive types.
>>>
>>>I'm not sure I see the significance of nesting, although I seem to get
>>>a feeling why genericity of record type is a big deal.
>>  
>> Nesting is not significant; it's allowing data structures to express
>> choice that increases the expressive power.
> 
> I tend to disagree. Choice by itself can always be flattened, but 
> arbitrary deep nesting cannot, so it does matter for the expressive 
> power of the query language.

How can you have arbitrarily deep nesting without choice?
At some point you have to choose to stop nesting.

Simon.

"alex goldman" <hello@spamm.er> wrote in message 
news:2833197.QA2ogCgjIP@yahoo.com...
> ......"[In first-order logic, the term]
> `function' is better used for predicates that possess certain properties
> (determinism)"

What's that supposed to mean ?

One would hope that by now you'd have an introductory book on logic and 
learned :
-- that FOL does not talk about function or 'functors' but rather about 
'function symbols',  among other things;
-- that FOL can get rid of function symbols and be as expressive as with 
them;
-- that FOL without 'function symbols' ain't equivalent to Datalog
... et cetera...
>
> 

VC wrote:

> 
> "alex goldman" <hello@spamm.er> wrote in message
> news:2833197.QA2ogCgjIP@yahoo.com...
>> ......"[In first-order logic, the term]
>> `function' is better used for predicates that possess certain properties
>> (determinism)"
> 
> What's that supposed to mean ?

Look, anonymous troll, I was hoping you'd follow the link to Quinlan's paper

J.R. Quinlan. Learning first-order definitions of *functions* . Journal of
Artificial Intelligence Research, 5:139-161, 1996.

and find that he means by "function" exactly what I alluded to. And I'm sure
you did, but being a troll, you just continue trolling instead of admitting
you were wrong, namely

1. Very knowledgeable people use the term "function" to refer to certain
kinds of predicates.

2. FOL courses are being taught where the term "functor" is used in place of
"function symbol"

(Which, as I already indicated, is justified in view of #1 and Prolog
practice)

3. You are an idiot because you resorted to insults (go read prolog 101,
etc.) because your prefered terminology (if there ever was one) differs
from mine.

4. Saying " `for_any X Y : car(cons(X,Y), X)` does not make any sense
because it's missing a period at the end" is a sign of utter stupidy and/or
trolling.

You just keep inventing brand-new silliness, as if what you previously wrote
isn't enough?

VC wrote:

> -- that FOL can get rid of function symbols and be as expressive as with
> them;

?!?


First-order logic without function symbols (F O) provided the basis for
query languages for the early commercial relational database systems. Its
appeal lies in its simplicity, clear semantics, and dual declarative and
procedural incarnations. Indeed, F O has a simple algebraization which is
particularly amenable to optimization. While F O has many appealing
features, it has limited expressive power. For instance, it cannot compute
the transitive closure of a graph. [1]

[1] Expressive Power of Query Languages, Serge Abiteboul & Victor Vianu

http:www.informatik.uni-freiburg.de/~dbis/lehre/db-th-ws0001/papers/abi_vianu.ps

"alex goldman" <hello@spamm.er> wrote in message 
news:1741495.boTg3PEKqR@yahoo.com...
> VC wrote:
>
>>
>> "alex goldman" <hello@spamm.er> wrote in message
>> news:2833197.QA2ogCgjIP@yahoo.com...
>>> ......"[In first-order logic, the term]
>>> `function' is better used for predicates that possess certain properties
>>> (determinism)"
>>
>> What's that supposed to mean ?
>
> Look, anonymous troll, I was hoping you'd follow the link to Quinlan's 
> paper
>
> J.R. Quinlan. Learning first-order definitions of *functions* . Journal of
> Artificial Intelligence Research, 5:139-161, 1996.
>
> and find that he means by "function" exactly what I alluded to. And I'm 
> sure
> you did, but being a troll, you just continue trolling instead of 
> admitting
> you were wrong, namely
>
> 1. Very knowledgeable people use the term "function" to refer to certain
> kinds of predicates.
>

Are you familiar with the notion of "argumentum ad verecundiam " ?



> 2. FOL courses are being taught where the term "functor" is used in place 
> of
> "function symbol"
>
> (Which, as I already indicated, is justified in view of #1 and Prolog
> practice)

FOL ain't Prolog,  and the "very knowledgeable people",  whoever they are, 
do their students a disservice by using a sloppy language.

>
> 3. You are an idiot because you resorted to insults (go read prolog 101,
> etc.) because your prefered terminology (if there ever was one) differs
> from mine.
>
> 4. Saying " `for_any X Y : car(cons(X,Y), X)` does not make any sense
> because it's missing a period at the end" is a sign of utter stupidy 
> and/or
> trolling.

In Prolog, the string  `for_any X Y : car(cons(X,Y), X)` does not make any 
syntactical sense wven with a dot. 

"alex goldman" <hello@spamm.er> wrote in message 
news:2040780.qLjtXq1iaR@yahoo.com...
> You just keep inventing brand-new silliness, as if what you previously 
> wrote
> isn't enough?
>
> VC wrote:
>
>> -- that FOL can get rid of function symbols and be as expressive as with
>> them;
>
> ?!?
>
>
> First-order logic without function symbols (F O) provided the basis for
> query languages for the early commercial relational database systems. Its
> appeal lies in its simplicity, clear semantics, and dual declarative and
> procedural incarnations. Indeed, F O has a simple algebraization which is
> particularly amenable to optimization. While F O has many appealing
> features, it has limited expressive power. For instance, it cannot compute
> the transitive closure of a graph. [1]
>
> [1] Expressive Power of Query Languages, Serge Abiteboul & Victor Vianu
>
> http:www.informatik.uni-freiburg.de/~dbis/lehre/db-th-ws0001/papers/abi_vianu.ps

1. It's been know , at least since Russel's times, that any FOL formula with 
function symbols
can be translated to an equivalent FOL formula without function symbols. 
The Horn subset however cannot.

2. Are you familiar with the notion of "argumentum ad verecundiam " ?

VC wrote:

> 
> "alex goldman" <hello@spamm.er> wrote in message
> news:2040780.qLjtXq1iaR@yahoo.com...
>> You just keep inventing brand-new silliness, as if what you previously
>> wrote
>> isn't enough?
>>
>> VC wrote:
>>
>>> -- that FOL can get rid of function symbols and be as expressive as with
>>> them;
>>
>> ?!?
>>
>>
>> First-order logic without function symbols (F O) provided the basis for
>> query languages for the early commercial relational database systems. Its
>> appeal lies in its simplicity, clear semantics, and dual declarative and
>> procedural incarnations. Indeed, F O has a simple algebraization which is
>> particularly amenable to optimization. While F O has many appealing
>> features, it has limited expressive power. For instance, it cannot
>> compute the transitive closure of a graph. [1]
>>
>> [1] Expressive Power of Query Languages, Serge Abiteboul & Victor Vianu
>>
>>
http:www.informatik.uni-freiburg.de/~dbis/lehre/db-th-ws0001/papers/abi_vianu.ps
> 
> 1. It's been know , at least since Russel's times, that any FOL formula
> with function symbols
> can be translated to an equivalent FOL formula without function symbols.
> The Horn subset however cannot.
> 
> 2. Are you familiar with the notion of "argumentum ad verecundiam " ?


Let me get this straight. Because you don't grasp the fundamentals, I have
to reproduce all theories, proofs, etc. right here, without referencing any
papers by others? I have never seen such idiocy. (Actually, HERC comes to
mind, but he has a medical condition)

You wrote: "FOL can get rid of function symbols and be as expressive as 
with them"

Abiteboul & Vianu write: "[FOL without function symbols] has limited
expressive power. For instance, it cannot compute the transitive closure of
a graph"

How more explicit do you need the proof that you don't know what the hell
you are talking about? (Rhetoric question, you are just a troll, after all)

VC wrote:

> 
> "alex goldman" <hello@spamm.er> wrote in message
> news:1741495.boTg3PEKqR@yahoo.com...
>> VC wrote:
>>
>>>
>>> "alex goldman" <hello@spamm.er> wrote in message
>>> news:2833197.QA2ogCgjIP@yahoo.com...
>>>> ......"[In first-order logic, the term]
>>>> `function' is better used for predicates that possess certain
>>>> properties (determinism)"
>>>
>>> What's that supposed to mean ?
>>
>> Look, anonymous troll, I was hoping you'd follow the link to Quinlan's
>> paper
>>
>> J.R. Quinlan. Learning first-order definitions of *functions* . Journal
>> of Artificial Intelligence Research, 5:139-161, 1996.
>>
>> and find that he means by "function" exactly what I alluded to. And I'm
>> sure
>> you did, but being a troll, you just continue trolling instead of
>> admitting
>> you were wrong, namely
>>
>> 1. Very knowledgeable people use the term "function" to refer to certain
>> kinds of predicates.
>>
> 
> Are you familiar with the notion of "argumentum ad verecundiam " ?

Idiot, you told me to go read prolog 101 for the very thing Quinlan is
doing. Do you think he should do that too, Mr. anon?

> 
>> 2. FOL courses are being taught where the term "functor" is used in place
>> of
>> "function symbol"
>>
>> (Which, as I already indicated, is justified in view of #1 and Prolog
>> practice)
> 
> FOL ain't Prolog,  and the "very knowledgeable people",  whoever they are,
> do their students a disservice by using a sloppy language.

You claimed "There is no FOL with functors". Well, I gave you proof that
there is. Why aren't you satisfied? (Rhetoric question, you are just a
troll, after all)


>> 3. You are an idiot because you resorted to insults (go read prolog 101,
>> etc.) because your prefered terminology (if there ever was one) differs
>> from mine.
>>
>> 4. Saying " `for_any X Y : car(cons(X,Y), X)` does not make any sense
>> because it's missing a period at the end" is a sign of utter stupidy
>> and/or
>> trolling.
> 
> In Prolog, the string  `for_any X Y : car(cons(X,Y), X)` does not make any
> syntactical sense wven with a dot.

Of course the string is not valid Prolog, but claiming it does not make any
sense because it's missing a period at the end is a sign of utter stupidity
and/or trolling.

Dear VC,

> FOL ain't Prolog,  and the "very knowledgeable people",  whoever they are, 
> do their students a disservice by using a sloppy language.

Pots and kettles. ;-)

Best wishes,

Bill

alex goldman <hello@spamm.er> writes:

> You wrote: "FOL can get rid of function symbols and be as expressive as 
> with them"
>
> Abiteboul & Vianu write: "[FOL without function symbols] has limited
> expressive power. For instance, it cannot compute the transitive closure of
> a graph"

It muddies the waters a bit to talk about what a logic can "compute";
bit still I don't see why these statements are contradictory, as you
seem to believe.

In fact the notion of transitive closure is not expressible in FOL,
even with function symbols --

see eg

ttic.uchicago.edu/~dmcallester/notes/fol.ps

-- 
Alan Smaill

Simon Taylor wrote:
> In article <30pie.93684$yc.5551208@phobos.telenet-ops.be>, Jan Hidders wrote:
>>Simon Taylor wrote:
>>>In article <1116283418.903814.273940@f14g2000cwb.googlegroups.com>, Mikito Harakiri wrote:
>>>>Jan Hidders wrote:
>>>>
>>>>>The way that function symbols are interpreted in Prolog and what gives
>>>>>them their expressive power in combination with recursion is more like
>>>>>what you would call a tuple constructor. So a term like f(x,y)
>>>>>represents a binary tuple with fields x and y and a label f that
>>>>>distinguishes it from g(x,y). So a better analogue would be user-defined
>>>>>record types where the type system allows arbitrary deep nesting or
>>>>>recursive types.
>>>>
>>>>I'm not sure I see the significance of nesting, although I seem to get
>>>>a feeling why genericity of record type is a big deal.
>>> 
>>>Nesting is not significant; it's allowing data structures to express
>>>choice that increases the expressive power.
>>
>>I tend to disagree. Choice by itself can always be flattened, but 
>>arbitrary deep nesting cannot, so it does matter for the expressive 
>>power of the query language.
> 
> How can you have arbitrarily deep nesting without choice?
> At some point you have to choose to stop nesting.

You don't need variant records for that, if you have a set-type you can 
at some point decide to have an empty set, but I suppose that if you 
stretch the concept a little you could argue that his is also some form 
of "choice". Anyway, you seemed to imply (and I denied) that just having 
choice is *sufficient* to increase the expressive power which is of 
course not the same as claiming that it is *necessary*.

-- Jan Hidders

VC wrote:
> 
> 2. Are you familiar with the notion of "argumentum ad verecundiam " ?

VC, are you familiar with the expression "Don't feed the Trolls"? :-) 
This is not meant as criticism, you have every right to do so if you 
want to, but it would be better for all the newsgroups involved if you 
didn't.

-- Jan Hidders

On Wed, 18 May 2005 09:23:32 -0700, alex goldman <hello@spamm.er> said:
> ...
> [VC]wrote: "FOL can get rid of function symbols and be as expressive as 
> with them"

That's right, so long as you mean (as I imagine you do) FOL with
identity.  If you have identity, then the expressive work of n-place
function symbols in a language L1 can be done in a language L2 in which
the function symbols of L1 are replaced by n+1-place predicates that are
axiomatized to express functional relations.  So, e.g., the work of a
1-place function symbol f in L1 can be done by its corresponding 2-place
predicate F in L2 by axiomatizing F such that (x)(y)(z)[(F(x,y) &
F(x,z)) -> y=z] and translating the sentences of L1 into L2 accordingly.
Thus, the sentence (x)(y)(f(x) = f(y) -> x=y) could be translated into
(x)(y)(z)(F(x,z) & F(y,z) -> x=y).  (This sounds a bit seat of the
pants, but there are general, systematic ways of defining such
translation schemes.)

> Abiteboul & Vianu write: "[FOL without function symbols] has limited
> expressive power. For instance, it cannot compute the transitive
> closure of a graph"

I'm confused by the talk of computation here, but, in the model
theoretic sense of "expressive power", the TC of a graph is not
expressible in first-order logic with or without function symbols.

Chris Menzel

Jan Hidders wrote:
> VC wrote:
> 
>>
>> 2. Are you familiar with the notion of "argumentum ad verecundiam " ?
> 
> 
> VC, are you familiar with the expression "Don't feed the Trolls"? :-) 

Jan Hidders, are you familiar with the expression "Don't feed the
feeders of the Trolls"?
.... [obvious copy&paste from previous contributions cut]

Oops, did I just bring recursion into this thread ?
Of course not. It was always there.

Cheers

Bart Demoen

Bart Demoen wrote:

> Jan Hidders wrote:
>> VC wrote:
>> 
>>>
>>> 2. Are you familiar with the notion of "argumentum ad verecundiam " ?
>> 
>> 
>> VC, are you familiar with the expression "Don't feed the Trolls"? :-)
> 
> Jan Hidders, are you familiar with the expression "Don't feed the
> feeders of the Trolls"?
> ... [obvious copy&paste from previous contributions cut]
> 
> Oops, did I just bring recursion into this thread ?
> Of course not. It was always there.
> 
> Cheers
> 
> Bart Demoen

OK, OK, it's time for somebody to call somebody else a Nazi or a fascist or
something so we can invoke Godwin's Law and end this thread  once and for
all. 

-- 
Kenneth Downs
Secure Data Software, Inc.
(Ken)nneth@(Sec)ure(Dat)a(.com)

alex goldman wrote:
> >>
> >> VC wrote:
> >>
> >>> -- that FOL can get rid of function symbols and be as expressive
as with
> >>> them;
> >>
> >> ?!?
> >>
> >>
> >> First-order logic without function symbols (F O) provided the
basis for
> >> query languages for the early commercial relational database
systems. Its
> >> appeal lies in its simplicity, clear semantics, and dual
declarative and
> >> procedural incarnations. Indeed, F O has a simple algebraization
which is
> >> particularly amenable to optimization. While F O has many
appealing
> >> features, it has limited expressive power. For instance, it cannot
> >> compute the transitive closure of a graph. [1]
> >>
> >> [1] Expressive Power of Query Languages, Serge Abiteboul & Victor
Vianu
> >>
> >>
>
http:www.informatik.uni-freiburg.de/~dbis/lehre/db-th-ws0001/papers/abi_vianu.ps
> >

FOL,  with or without function symbols,  cannot express transitive
closure. The article talks about FOL recursive extentions,  that's all.

E.g. non-recursive Datalog's expressive power is equivalent to that of
FOL,  but recursive Datalog is equivalent to, say, the negation and
equality free existential fragment of least fixed-point logic (LFPL or
FOL augmented with the least-point operator).

Please see in-line:

Jan Hidders wrote:
> VC wrote:
> >
> > 2. Are you familiar with the notion of "argumentum ad verecundiam "
?
>
> VC, are you familiar with the expression "Don't feed the Trolls"? :-)

> This is not meant as criticism, you have every right to do so if you
> want to, but it would be better for all the newsgroups involved if
you
> didn't.
> 

OK,  I guess you are quite right..

Thank you.

> -- Jan Hidders

Bart Demoen wrote:
> Jan Hidders wrote:
>>
>> VC, are you familiar with the expression "Don't feed the Trolls"? :-) 
> 
> Jan Hidders, are you familiar with the expression "Don't feed the
> feeders of the Trolls"?
> ... [obvious copy&paste from previous contributions cut]
> 
> Oops, did I just bring recursion into this thread ?
> Of course not. It was always there.

I believe I made a reasonable request that has a good chance of being 
effective. I fail to understand why you think it necessary to react in 
such an aggressive way with the risc of making this thread even longer 
than it already is.

Kind regards from the University of Antwerp,

-- Jan Hidders

vc wrote:
> Jan Hidders wrote:
>>
>>VC, are you familiar with the expression "Don't feed the Trolls"? :-)
> 
>>This is not meant as criticism, you have every right to do so if you
>>want to, but it would be better for all the newsgroups involved if you
>>didn't.
> 
> OK,  I guess you are quite right..

Thank you. I know how hard this can be.

-- Jan Hidders

Jan Hidders wrote:
> Bart Demoen wrote:
> > Jan Hidders wrote:
> >>
> >> VC, are you familiar with the expression "Don't feed the Trolls"?
:-)
> >
> > Jan Hidders, are you familiar with the expression "Don't feed the
> > feeders of the Trolls"?
> > ... [obvious copy&paste from previous contributions cut]
> >
> > Oops, did I just bring recursion into this thread ?
> > Of course not. It was always there.
>
> I believe I made a reasonable request that has a good chance of being

> effective. I fail to understand why you think it necessary to react
in
> such an aggressive way with the risc of making this thread even
longer
> than it already is.

Pehaps, it was a sarcastic hint that you are capable of posting much
more interesting messages, than boring usenet etiquette messages?

In an attempt to throw the authorities off his trail, "ken quirici" <kquirici@yahoo.com> transmitted:
> Would the Aho book on Foundations of computer science be a good place
> to find out some of the stuff you were talking about?

I haven't seen it, so I can't be certain.

But according to the table of contents, where Chapter 2 is entitled
"Iteration, Inducation and Recursion," that seems rather promising...
-- 
(format nil "~S@~S" "cbbrowne" "ntlug.org")
http://linuxdatabases.info/info/emacs.html
"How should I know if it  works?  That's what beta testers are for.  I
only  coded  it."   (Attributed  to  Linus Torvalds,  somewhere  in  a
posting)

Christopher Browne wrote:
> > But according to the table of contents, where Chapter 2 is entitled
> "Iteration, Inducation and Recursion," that seems rather promising...
>

Thanks for the reply. Yes, that is promising. I was just afraid its
treatment was comprehensive but not sufficiently rigorous or deep.

It's got thick paper. That's the problem. No technical book with
thick paper can be any good. Shiny is ok (barely) but not thick.

Ken

Jan Hidders wrote:

> I fail to understand why you think it necessary to react in 
> such an aggressive way with the risc of making this thread even longer 
> than it already is.

I fail to see what was aggressive about my reaction: I was only turning
the tables on you in a joking way. But please tell me which part of my
posting exactly you thought was agressive, so that I can try to
understand and maybe avoid it in the future.

Anyway, comp.lang.prolog, to which this since-long-absurd discussion is
cross-posted, is one of the rare newsgroups without trolls and unlike
you, we don't really know how to deal with them.
So please forgive us and me in particular.

Cheers

Bart Demoen

Bart Demoen wrote:
> Anyway, comp.lang.prolog, to which this since-long-absurd discussion
is
> cross-posted, is one of the rare newsgroups without trolls and unlike
> you, we don't really know how to deal with them.

A group without trolls? Unbelievable!
OK, here is the bait: It must be that Prolog is not used anymore?

This may have been an unfortunate notice to have posted  in
comp.databases.troll-heaven



"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message
news:1116618623.68481@seven.kulnet.kuleuven.ac.be...

> Anyway, comp.lang.prolog, to which this since-long-absurd discussion is
> cross-posted, is one of the rare newsgroups without trolls and unlike

[newsgroups restricted to comp.lang.prolog]

Bart Demoen wrote:
> 
> I fail to see what was aggressive about my reaction: I was only turning
> the tables on you in a joking way. But please tell me which part of my
> posting exactly you thought was agressive, so that I can try to
> understand and maybe avoid it in the future.

Ok. Let me try to explain why it was a bit upsetting. Of course this is 
just my interpretation and I understand very well that this is not how 
you meant it. Looking back I think I probably overreacted. So I'm just 
telling you this to explain why there was steam coming out of my ears :-).

- You started with my full personal name. On usenet that's pretty much 
the equivalent of raising your voice. Usually this is only done when the 
debate gets very friendly or very unfriendly. Yes, I knew you just did 
this to mirror my remark, but still.

- Then you accused me of fanning the thread. With that you attacked any 
moral authority that I might have on a moment when I might dearly need 
it to do something about the situation. That you did this in a clever 
and funny way only made that accusation more abrasive. Moreover, and 
perhaps this is the most important of all, there were no smileys 
anywhere to be seen. You didn't sound like a newbie or an inexperienced 
poster so apparently you really meant it and wanted to avoid the 
impression that it should be taken with a grain of salt.

- Then you continued with a remark that seemed to imply that the 
evidence to support your accusation was so obvious and well known by 
everybody that it even didn't need to be included. I was not just a 
little bit guilty, I was *very* guilty.

- Finally, to put the cherry on the cake, you ended with a clever remark 
that seemed to be there to preemptively block an obvious counterargument 
I might use to defend myself. Not only had you dealt the first blow, you 
already had prepared yourself for my reponse.

You can probably imagine that at this point I was wondering what exactly 
I had done to offend you so much. :-)

> Anyway, comp.lang.prolog, to which this since-long-absurd discussion is
> cross-posted, is one of the rare newsgroups without trolls and unlike
> you, we don't really know how to deal with them.

You don't have trolls? In comp.databases.theory its almost .... no, 
wait, let's not do that. :-)

> So please forgive us and me in particular.

Forgive you? I really don't think there's anything to forgive. 
Misunderstandings like this happen all the time on usenet. But if you 
want to do penance you can do so by using at least one smiley in each of 
your next five postings. :-)

Cheers,

-- Jan Hidders

Mikito Harakiri wrote:

> A group without trolls? Unbelievable!
> OK, here is the bait: It must be that Prolog is not used anymore?

That's troll bait - we don't fall for that.

Cheers

Bart Demoen

Jan Hidders wrote:
[...]

 > > So please forgive us and me in particular.
 >
 > Forgive you? I really don't think there's anything to forgive.

Ok, ok, you convinced me. I am retracting my plea for forgiveness.

Just so there are no more misunderstandings: have you by now admitted
that you accused me wrongly of aggression and is it you who should be
(or are) apologising ? Because, if you do, I am ready to absolve you
without any further smiley debet - just ask for it.

Cheers

Bart Demoen