Quote from AntC on January 13, 2021, 11:01 pm

Quote from tobega on January 13, 2021, 2:12 pm

Quote from AntC on January 13, 2021, 1:40 am

Quote from tobega on January 12, 2021, 1:09 pm

 

 

 

 

Just wrong. I can add the number of apples to the number of oranges. The answer is not a number of apples nor a number of oranges; but its a number of pieces of fruit (for example).

Actually you are not adding apples and oranges, you are first converting them to a common unit "fruit", i.e. M apple(s) * 1 fruit/apple + N orange(s) * 1 fruit/orange = (M+N) fruit(s).

Unfortunately we lose some information in the process and it is not easy to convert back.

Any operation in any domain 'loses information'. If all we know is that the answer is 4, we've lost the information that it came from 2+2 vs 3 + 1 vs 4 + 0 vs 5 + -1, etc.

 

... you are saying the same as Erwin that there must be an "AND" between tuples so that all tuples must be true.

 

Right, you do both seem to be saying the same thing, that in the example the only acceptable interpretation (the only way to have a valid relation value?) is to say that:

"All the tuples are true and each tuple means that Employee X works in Department Y OR on project Z"

The problem I have with that is that when I project on (Employee, Department), I get a relation value where it is suddenly very difficult to assert anything about the employee's relation to the department.

Any operation in any domain 'loses information'. Nothing RM-specific here. The OR is already losing information wrt the Department. It's not the projection operation that loses that. A tuple appearing in that disjunction doesn't necessarily assert anything about the employees relation to a department -- because perhaps the tuple 'came from' (to speak very loosely) the X working on project Z.

Specifically with the projection operation, we're 'projecting away' some attribute(s). The logical equivalent of that is Existential quantification:

• 'Employee X works in Department Y OR there exists Project Z such that X works on Z.'

That tells you just as much (or rather just as little) about the employee's relation to the department.

Since it would (I presume) still be required to have "AND" between all the tuples, my only recourse seems to be to say that each tuple means "Employee X may work in Department Y".

Logically, we have now unfortunately lost some information, since the "may" could be  "doesn't" in each case. Previously I knew that the employee does in fact work in one of the departments. Unless of course there is something else that tells me that every employee must work in a department, but that is not clear.

Practically when doing algorithmic work, I think it is often more useful to think in the other way, so for the example I would want to say:

"One of the tuples is true and each tuple means Employee X works in Department Y on project Z"

The advantage of that is that under the projection on (Employee, Department), the logic trivially stays the same

"One of the tuples is true and each tuple means Employee X works in Department Y"

 

No the presence of the tuple in the projection of a disjunction does not mean Employee X works in Department Y. The relation value that has the predicate you want is the original input with only attributes {employee, department}. In general operations are not meaning-preserving that start from some relation, manipulate it then produce a relation with the same heading as the original input -- even if they also produce the same value. In (3 + 1) - 2 = 2, the subtracting 2 yielding 2 does not show that you started from 2 + 2. Nothing specific to the RM here.

Quote from dandl on January 13, 2021, 11:07 pm

I've been following along here hoping it would all make sense. It doesn't, and throwing ANDs and ORs and other vague terms around just confuses things.

In my very simplistic view, a relation consists of a set of tuples, each of which is a fact asserted by some suitably knowledgeable authority, and which makes the associated predicate true. The CWA says that each missing tuple (fact not so asserted) is false. The RA is a set of operators on those relations to return new relations. Each new relation has a new predicate that can be derived logically. The existence of a tuple in that new relation is the assertion of the fact that makes that predicate true; its absence makes the predicate false. It's that simple.

The basic RA defined by Codd is 5 operators (SPJUN, no R); the modern ERA has another 4 (RVWA). Each operator can be defined formally. This is solid, reliable, comprehensive and comprehensible. This is what SQL does, in its own clunky way.

Algebra-A is part of the process of formally defining a basis for the RA. It defines 5 operators formally (NOT,AND,OR,RENAME,REMOVE) and 2 informally (TCLOSE and relcons). I see the work as incomplete, but it goes close. It was a long time ago.

And that's all there is. IMO you should concentrate on getting a full understanding of the ERA -- this is the entry point. By all means go down from ERA into A to see formal definitions, but mainly you need to work up from ERA to language, syntax and features. That's what TTM is all about.

Quote from AntC on January 13, 2021, 11:15 pm

Quote from tobega on January 13, 2021, 5:15 pm

Quote from tobega on January 13, 2021, 2:39 pm

Quote from AntC on January 13, 2021, 1:59 am

Quote from tobega on January 12, 2021, 1:37 pm

The thing I mentioned about two operators doing "the same thing" but having different meaning may depend on the outcome of the other current question, but consider that I have a set consisting of the tuple {employee: E, department: D} and another set consisting of the tuple {employee: E, department: C} where both mean "Employee X works in department Y"

They mean whatever the database designer specifies that they mean. Are the two sets derived from some relvar, perhaps by some relational operations? Perhaps one means this is the employees 'home' department and the other means this is where the employee is temporarily assigned.

I can put these together into a set containing both, with the <or> operator or the union operator, the outcome will look exactly the same as regards the set of tuples.

Fine. What is the predicate for that derived relation value?

In one case, I might know that both are true, that E indeed shares their time between the departments, so I claim it would be more correct to use "union", and the relation value represents a conjunction of tuples.

Hunh? "union" produces a disjunction. It's "intersection" that produces a conjunction. If you applied "intersection" you'd get an empty relation value. Representing a predicate (perhaps) "No employee is temporarily assigned to their home department".

Say I get a list/set of employee to department assignments from the Main Street office and another from the High Street office. When I union those two sets, I get an AND between them (and by your own statements previously, there can only be an AND between tuples). Semantically I would say that is definitely not an OR.

Also, even if an employee has two different assignments, both are true, so still a semantic AND rather than an OR

In the other case, I know that perhaps only one of the statements is true, so it is eminently suitable to use <or> and the relation value represents a disjunction of tuples.

You appear to be saying you might use <or> or you might use <or>. What on earth are you trying to say?

What if your input relations each contain 2 tuples, the ones you identify plus {employee: F, department: D} and {employee: F, department: C} respectively? Then are you trying to build a predicate in which exactly one of the four is true? Or exactly one for each distinct Employee? What if one only of the input relations has {employee: G, department: D}? What predicate do you want now?

Indeed, that is exactly the relevant question.

This case perhaps gets a little contrived, sorry I can't make up a more believable one.

Consider that we have two places where we keep track of our employees' assignments to departments, but unfortunately we don't update them simultaneously. We do know, however, that at least one of the places always gets updated on a change of assignment. Now it makes more semantic sense to speak of OR, because in case the two sources agree, that collapses to the same tuple in the set, but if they differ, one of them is known to be true (and maybe both).

But we have run into trouble if we require an AND between all tuples, so what is a reasonable predicate here?

The relation value, in the absence of knowing the query that produced it doesn't "mean" anything. There's no reason to expect two relation values that happen to be equal but are derived from different queries "mean" the same thing.

Now I've answered more than enough of this from you. If you don't show evidence you've read Ch 2, I'm not going to answer more.

Fair enough, thanks for your patience so far!

OK, so I realize what's not been clear here, and I was losing sight of it as well, is that while the names in algebra "A" obviously are correct according to a set theoretic view,

The names <OR>, <AND>, <NOT> are according to a predicate logic point of view. The names UNION, INTERSECTION, MINUS (≡ logical r <AND> <NOT> s) are their set-theoretic counterparts.

I am thinking from a perspective of a user of a relation value, what is a word that semantically corresponds to the way I would use the operator?

Now the set theoretic view is of course theoretically correct given the formal definitions and absolutely perfect for implementing a set, to check for membership in the union I would check if it is a member of the one set OR the other set.

But IMO it's a rubbish name when working with relation values and logic, so I wouldn't want to call the operator "OR". Using the name "UNION" is fine, because it semantically means "together", a kind of "and", which is how I would view it. On the other hand, the extended case in algebra A where the headers are different does in fact correspond to an "OR" logically and semantically as well.

 

DTATRM Ch 2 (bottom of p.29) will tell you that relation values are 'extensions' of a predicate -- which expresses the 'intension'. The tuples appearing in a relation value (a set) represent the attribute-values for which the intension holds at that point in time.

Relational operators operate on extensions -- which is why they're usually named/specified in terms of set operations. But the original RA [Codd 1972] could only conceive of set operations on relation values with the same heading -- which is why they're sometimes called 'UNION-compatible operations' in SQL. That's too restrictive for expressing all possible logical operations (queries) you might want over the database. As Hugh's message on this thread pointed out, A's <OR> (and <NOT>) are 'unsafe' operations, they're not intended to appear in a practical query language. (That some of us round here have never the less implemented them in query languages is tribute to the breadth of D&D's vision.)

Quote from tobega on January 14, 2021, 9:44 am

Thanks for all the answers so far, they are helping sort things out.

Apologies for the vagueness, but it might now be evident that my interest lies mainly in considering logic propositions and designing a language for manipulating them in order to arrive at the result of an algorithm. I see that the relational algebra operators can allow me to express operations over large sets of statements instead of having to iterate. Provided of course that it can be shown to hold. And if so, my concern is also about providing well-named operators in a language for this kind of manipulation.

 

Quote from dandl on January 14, 2021, 1:31 pm

Then you might find that the RA has some unfortunate limits. The RA is pretty good for  'slicing and dicing' existing data values, and the ERA can certainly generate new values, but it is not Turing complete. For a query language this is an advantage (queries are guaranteed to terminate) but it makes many algorithms inaccessible.

The version of RA in Rel/TD has limited versions of transitive closure and aggregation so you cannot for example do a parts explosion or a path cost analysis. The workaround for Rel/TD is to use the non-RA language features.

If logic propositions and algorithms are your interest, I'm not sure the RA is the place to start. Perhaps Lisp or Haskell or Prolog or even Datalog?

Quote from Hugh on January 14, 2021, 3:28 pm

I've seen some statements in this thread that cause me to want to clarify some points.

"Relation" is a mathematical term.  Mathematics doesn't deal with variables in the computing sense, so doesn't need to clarify that a relation is a value.  Add the word "value" only when there is any risk of your use of just "relation" being taken to mean relvar.  That might be quite often in this forum!

Antc observed that in TTM "every relvar is required  to have a key".   Yes, but I'm afraid RM Pre 15's statement to that effect is strictly redundant.  By definition every relation satisfies at least one key constraint, simply because it is a set of tuples, so the same tuple cannot appear more than once.   RM Pre 15 also requires every relvar to be subject to at least one declared key constraint, but it permits such a declaration to be implicit.  Tutorial D supports KEY{ALL BUT ...}, such that if the ... is replaced by nothing, then the set of all the attributes constitute the only declared key.  It is reasonable to allow that to be implicit when no explicit key declaration is given but unfortunately in some people's opinion (including my own, on reflection!) that was a poor choice by us.

The connection between a relation and a predicate is sometimes better expressed using the verb "satisfy".   Relation r satisfies predicate P iff for every tuple in r, a true proposition results when its values are used to replace every free variable in P.  There may be many such predicates.  TABLE_DEE, for example, satisfies every predicate that has no free variables and is a tautology, such as "1 is odd", or "1 is either even or odd".  The relation REL{TUP{n 1}} satisfies the predicate "n = 1" but might also satisfy the predicate "n is the number of suppliers located in Amsterdam" if it were the result of a query asking for that value.  A predicate declared for a relvar is one that is assumed to be satisfied by every relation assigned to that relvar, from the time of assignment up until the next assignment.

Hugh

 

Quote from tobega on January 14, 2021, 7:51 pm

Quote from dandl on January 14, 2021, 1:31 pm

Then you might find that the RA has some unfortunate limits. The RA is pretty good for  'slicing and dicing' existing data values, and the ERA can certainly generate new values, but it is not Turing complete. For a query language this is an advantage (queries are guaranteed to terminate) but it makes many algorithms inaccessible.

The version of RA in Rel/TD has limited versions of transitive closure and aggregation so you cannot for example do a parts explosion or a path cost analysis. The workaround for Rel/TD is to use the non-RA language features.

If logic propositions and algorithms are your interest, I'm not sure the RA is the place to start. Perhaps Lisp or Haskell or Prolog or even Datalog?

Lisp and Haskell never really appealed to me. I do like Julia, though, which is basically a Lisp with a sane FORTRAN-like syntax and lots of scientific steroids. But I also really like coding in Tailspin and am still having lots of fun developing it.

Prolog and/or Datalog are great suggestions, but my assessment so far is that logic programming is too different to integrate smoothly into another language, even when they in fact interoperate seamlessly as in Shen. Conceptually you still end up with two islands in your code, usually one is never visited.

I don't think of it as a workaround to use non-RA features, I'd say the height of success is when you no longer think of it as different things but all are just smoothly integrated parts of the same language. That is why I started putting relational features into Tailspin now, because I saw things starting to come together and it's so far going better than I first thought.

• A tuple with named attributes is exactly what a Tailspin "structure" is, so creating a relation value is very similar to creating a list of structures.
• The idea of a "projection" extends to array indexing, albeit with different projection types for the array parts, and the same syntax for relations can be applied to structures embedded in multi-dimensional arrays. So, e.g., project onto the "foo" attribute of every fifth element of every column of a permutation of the rows.
• All operations in Tailspin can produce a stream of zero or more values which is perfect for ungrouping, but could also make any projection produce more than one tuple, if desired.

Newer languages have built-in Maps and Sets, but they are really just a poor man's relations (tada!) so in Tailspin I want to provide more powerful operations, like the possibility to do a "join" between maps, for example. Since Tailspin has very strict rules about where mutable variables can exist, I'll probably still provide Map and Set processors (i.e. mutable objects), and a more general Relation/Table to enable insertion/deletion semantics and then do relational operations on immutable views.

When I have the relation syntax, I realize that a relation works very well as a source of basic facts for Datalog, so then I suppose I might be getting closer to integrating it with the relational selection syntax.

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Y>}>)
Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Z>}>), Container(Z, Y)

[$Container(X, 'shiny gold')] -> $::length

as a tentative datalogish solution to part 1 of the day 7 problem I posted earlier. This still looks and feels rather foreign. I may get used to it.

 

 

Quote from dandl on January 15, 2021, 12:31 am

Quote from tobega on January 14, 2021, 7:51 pm

Quote from dandl on January 14, 2021, 1:31 pm

Then you might find that the RA has some unfortunate limits. The RA is pretty good for  'slicing and dicing' existing data values, and the ERA can certainly generate new values, but it is not Turing complete. For a query language this is an advantage (queries are guaranteed to terminate) but it makes many algorithms inaccessible.

The version of RA in Rel/TD has limited versions of transitive closure and aggregation so you cannot for example do a parts explosion or a path cost analysis. The workaround for Rel/TD is to use the non-RA language features.

If logic propositions and algorithms are your interest, I'm not sure the RA is the place to start. Perhaps Lisp or Haskell or Prolog or even Datalog?

Lisp and Haskell never really appealed to me. I do like Julia, though, which is basically a Lisp with a sane FORTRAN-like syntax and lots of scientific steroids. But I also really like coding in Tailspin and am still having lots of fun developing it.

And that's the point. No-one need ever use your language, creating it is the thing. I created Andl in the same spirit.

Prolog and/or Datalog are great suggestions, but my assessment so far is that logic programming is too different to integrate smoothly into another language, even when they in fact interoperate seamlessly as in Shen. Conceptually you still end up with two islands in your code, usually one is never visited.

I don't think of it as a workaround to use non-RA features, I'd say the height of success is when you no longer think of it as different things but all are just smoothly integrated parts of the same language. That is why I started putting relational features into Tailspin now, because I saw things starting to come together and it's so far going better than I first thought.

Doesn't work that way. There are a few key paradigms of coding, and they don't blend. Simple example: template programming in C++ is nothing like OO programming in C++. They are islands, and deservedly so. Most modern GP languages are OO, and they have stateful mutable class-based objects. Haskell and other FP languages have stateless immutable values. They don't blend. Either you pick just one, or you have islands. Shen has at least 3 islands.

• A tuple with named attributes is exactly what a Tailspin "structure" is, so creating a relation value is very similar to creating a list of structures.

Be careful: they look the same but a tuple in TTM is more like a map than a traditional struct. There is no order to the names.

• The idea of a "projection" extends to array indexing, albeit with different projection types for the array parts, and the same syntax for relations can be applied to structures embedded in multi-dimensional arrays. So, e.g., project onto the "foo" attribute of every fifth element of every column of a permutation of the rows.

The RA cannot in general do permutations, and there is no concept of indexing.

• All operations in Tailspin can produce a stream of zero or more values which is perfect for ungrouping, but could also make any projection produce more than one tuple, if desired.

Newer languages have built-in Maps and Sets, but they are really just a poor man's relations (tada!) so in Tailspin I want to provide more powerful operations, like the possibility to do a "join" between maps, for example. Since Tailspin has very strict rules about where mutable variables can exist, I'll probably still provide Map and Set processors (i.e. mutable objects), and a more general Relation/Table to enable insertion/deletion semantics and then do relational operations on immutable views.

When I have the relation syntax, I realize that a relation works very well as a source of basic facts for Datalog, so then I suppose I might be getting closer to integrating it with the relational selection syntax.

Yes, a relation is 'just' a set of tuples. No, a tuple is not quite like anything found in any other programming language: it's part struct, part map, part novel.

My view is that the best answer to the 'D' question set by TTM is to implement the features of TTM in an existing language. I can get close in C# but would need a compiler modification; Ant has a solution in Haskell (with a customised version of records), but maybe it could be done in Shen? I haven't looked.

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Y>}>)

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Z>}>), Container(Z, Y)

[$Container(X, 'shiny gold')] -> $::length

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Y>}>) Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Z>}>), Container(Z, Y) [$Container(X, 'shiny gold')] -> $::length

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Y>}>)
Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Z>}>), Container(Z, Y)

[$Container(X, 'shiny gold')] -> $::length

as a tentative datalogish solution to part 1 of the day 7 problem I posted earlier. This still looks and feels rather foreign. I may get used to it.

Sorry, needs more explanation before it makes sense.

Quote from tobega on January 15, 2021, 9:13 am

• A tuple with named attributes is exactly what a Tailspin "structure" is, so creating a relation value is very similar to creating a list of structures.

Be careful: they look the same but a tuple in TTM is more like a map than a traditional struct. There is no order to the names.

Right, there can certainly be dragons here. In Tailspin a structure is also a map from keys to values. More concerning is that the instinctive interpretation of a structure would always be a "has-A"-like relationship between the attributes, regardless of which you pick as the subject of the statement, so that would be like an "and" between attributes, which may conflict with the predicate.

• The idea of a "projection" extends to array indexing, albeit with different projection types for the array parts, and the same syntax for relations can be applied to structures embedded in multi-dimensional arrays. So, e.g., project onto the "foo" attribute of every fifth element of every column of a permutation of the rows.

The RA cannot in general do permutations, and there is no concept of indexing.

Certainly, the example was to show how the same/similar concept and syntax works the same/similarly in a non-RA context.

• All operations in Tailspin can produce a stream of zero or more values which is perfect for ungrouping, but could also make any projection produce more than one tuple, if desired.

Newer languages have built-in Maps and Sets, but they are really just a poor man's relations (tada!) so in Tailspin I want to provide more powerful operations, like the possibility to do a "join" between maps, for example. Since Tailspin has very strict rules about where mutable variables can exist, I'll probably still provide Map and Set processors (i.e. mutable objects), and a more general Relation/Table to enable insertion/deletion semantics and then do relational operations on immutable views.

When I have the relation syntax, I realize that a relation works very well as a source of basic facts for Datalog, so then I suppose I might be getting closer to integrating it with the relational selection syntax.

Yes, a relation is 'just' a set of tuples. No, a tuple is not quite like anything found in any other programming language: it's part struct, part map, part novel.

My view is that the best answer to the 'D' question set by TTM is to implement the features of TTM in an existing language. I can get close in C# but would need a compiler modification; Ant has a solution in Haskell (with a customised version of records), but maybe it could be done in Shen? I haven't looked.

I am fairly certain that it can be done in Shen, or indeed any Lisp, because Lisp gives you access to the Read part of the REPL. If you want to go that route, I think your work might be greatly appreciated and heavily used if you chose to do it in Julia. Since you already have the heavy work of the ERA done, it's "only" implementation "details" left ;-).

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Y>}>)

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Z>}>), Container(Z, Y)

[$Container(X, 'shiny gold')] -> $::length

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Y>}>) Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Z>}>), Container(Z, Y) [$Container(X, 'shiny gold')] -> $::length

Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Y>}>)
Container(X, Y) :- $bagrules(<{container: <=X>, contained: <=Z>}>), Container(Z, Y)

[$Container(X, 'shiny gold')] -> $::length

as a tentative datalogish solution to part 1 of the day 7 problem I posted earlier. This still looks and feels rather foreign. I may get used to it.

Sorry, needs more explanation before it makes sense.

Certainly, it is by no means obvious.

The basic relation is bagrules over {container:, contained:, amount:} which states that a container has directly inside it amount of the contained.

Then we set up the datalog rule that we can say that X is a Container of Y either it directly contains it, or it directly contains Z that is a Container of Y.

Last we ask for all pairs (X, 'shiny gold') that satisfy the Container rule, capture them in a list and take the length of the list to find the requested answer. In Tailspin, the inspiration from XSLT is that we don't say in words what we create, but draw a picture, so '[' and ']' create a list containing what the stream producer between them produces.

The syntax $bagrules(<{container: <=X>, contained: <=Y>}>) is how to access the value named bagrules, the () were previously for array indexing but now for general projection-like things. In this case we do a selection on the relation value called bagrules (not yet implemented). The thing within angles <> is how I in Tailspin "draw a picture" of a condition, so a tuple/structure, by {}, containing an attribute "container" that is equal to X and an attribute "contained" that is equal to Y.

Here again we have a happy coincidence that the selection syntax is exactly like a condition in a "when"-statement, and another serendipity that the same syntax could also be applied for selection/filtering on lists/arrays (not implemented there either, yet, but I thought about it long ago)

The thing I want to make more Tailspinny is then how to specify the datalog rules and how to specify free variables. On reflection it does come quite close to the "draw a picture" ideal.