This page is in the process of being written and so you might want to wait until it is simplified before reading it.

We need SetBasedNamespaces because of the LimitsOfHierarchies.

Namespaces are sets

When you say, "page AB is a SubPage of page A", you are saying that page AB is in the NameSpace which is defined by page A. Intuitively, you think of page A as "owning" page AB.

In a SetBasedNamespace, just think of each page being associated with a set of other pages which it "owns". That is, if page AB was a SubPage of page A, then the set of pages "owned" by A includes AB.

Now, if you want AB to be a SubPage of A and also a SubPage of B, just put AB in both sets; the set of pages owned by A, and the set of pages owned by B.

You might want to make up an imaginary page called "root", which "owns" all of the top-level pages.

A flat namespace can be thought of as an extreme special case of a SetBasedNamespace, in which all of the pages are owned by "root".

A PlanetMath:tree based namespace can be thought of as a special case of a SetBasedNamespace, in which each page can only have one "owner".

Example and symbols

If pages A and B and C and D are toplevel, and AB and C were both in A's namespace, and AB was also in B's namespace, and D was also in C's namespace, then we might say

A's namespace = {AB, C}
B's namespace = {AB}
C's namespace = {C}
"root" namespace = {A,B,C}

The idea of SetBasedNamespace gets more fun if we separate out the idea of "namespaces" from the idea of pages. That is, instead of saying, "page A owns page AB", we say, "NameSpace A owns page B". What about page A? We say, "NameSpace root owns page A".

Now we can write the structure of the entire thing using sets-within-sets:

{A, B, C, 
 {AB, C, {D}}, 
 {C, {D}}

In words, I said, "the root namespace contains pages A, B, and C, and three namespaces. The first namespace contains pages AB and C, and a tertiary namespace which contains page D. The second namespace inside "root" contains page AB. The third namespace instead "root" contains page C, and a namespace which contains page D."

Fancy math words and their implications here


If you don't know what a "relation" is, it's something which may or may not be true between objects; for instance, DarthVader? is BayleShanks's father (not true; "father(DarthVader?,BayleShanks) = false"), UnitedStates? is BayleShanks's home (true; "home(UnitedStates?,BayleShanks) = true"). <= ("less than or equal to") is another example of a relation.


A PlanetMath:poset is a "partially ordered set". That means that every poset consists of two things: a PlanetMath:set of objects, and a relation on those objects which acts like <= (less than or equal to). For something to be a poset basically means that the relation is of a certain type (a "partial order").

The idea of "page AB being under page A in the hierarchy" is a relation between page AB and page A; even better, it's a relation that "acts like" <= in the way that we want. We could even write <= as a shortcut for "being under"; we could write AB <= A. (technical note: because we want the relation to act like "less than or equal", we would also say that "A <= A").

In the case of a wiki with SubPages, you can think of it as a poset with the relation being the one in the last paragraph. In a SetBasedNamespace, you can think of "ownership" as being the relation.

So, saying something is a poset is just saying that it is a hierarchy of some sort, although it may be a hierarchy where some nodes have "multiple parents".

Note that in both the cases we have talked about, there is only one relation. It is conceivable that a single wiki could have multiple relations at once. For example, I may be my grandfather's descendent, but I could also be his boss. The same elements may be related in multiple hierarchial ways.


A PlanetMath:semilattice is a poset in which you can take any two elements and say, "what do you get if you combine these two?". For example, if you had a wiki page "Rdf" for talking about RDF, and you had a wiki called "Wikis" for talking about wikis, you might ask, "is there a page for talking about RDF in the context of wikis?". If the wiki NameSpace were a semilattice, then by definition the answer to any such question would have to be, "yes, there is such a page!". Because, the definition of a semilattice is that, if pages A and B exist, then the combination page AB must exist.

Maybe it would be clearer to think about this in terms of the concept "AND". If a wiki's NameSpace is a semilattice with respect to "AND", and there is a page "Rdf", and a page "Wiki", then by definition, that wiki is forced to contain a page "RdfANDWiki?".

Incidentally, a more useful semi-lattice is a lower semi-lattice, where the overlap between any two concepts must be a meaningful concept (or empty). For example, the overlap between windows and Venice might be Venetian glassblowing and Italian windows. The semi-lattice just described is an upper semi-lattice, and is as useful as a bull in the overlap between windows, Venice, and shops.

See TreeVsSemiLattice for a little diagram.


I don't think lattices are needed for this discussion, but you might be wondering what they are since you saw the word "semilattice". To understand this, you really should learn about posets and semilattices formally, in terms of symbols like <=. The upshot for specific example in the last section, though, is that in a 'lattice' you would also be guaranteed to have pages like "RdfORWiki?".

Contributors: BayleShanks


PeriPeri implements a form of SetBasedNamespaces in conjunction with ContextualLinking?. See PeriPeri, FacetWiki.


Chris, do you think I've chosen an appropriate formalization of the idea? Is this what you had in mind by a "set-based namespace"?

One thing that bugs me is that the "namespaces" that we are talking about are always associated with a page (i.e. SubPages), so writing sets-within-sets doesn't capture all of the information. But, I think that for your FacetWiki purposes at least, you don't want sets-within-sets anyhow; that is what you mean by "set-based, not hierarchial", right?

-- BayleShanks

It would be interesting to see a semilattice SetBasedNamespace wiki without ContextualLinking?; one where, for example, you could ask for a page "Rdf+Wikis" or for a page "CategoryBiology:Tree" (and in which the page CategoryBiology:Tree could be the same page as CategoryEcology:Tree). Especially one with multiple relation types, i.e. RdfForWikis (although that is slightly different, I suppose). I suppose PeriPeri does this if the user always specifies their page completely.

The reason is that I feel that it is the ContextualLinking? which is the most confusing part of FacetWiki.

If you give up ContextualLinking?, you don't have to use the shatter algorithm, and you don't have nearly as much to explain to users. You can just say that it is like a normal wiki, except that you can say "Rdf+Wiki" instead of RdfForWikis, and that a page Tree can be a SubPage of both CategoryBiology? and CategoryEcology? at once.

If you are on page JohnsProject and you want to go to JohnsProject/ProjectLog, you could just write /ProjectLog. And, if you want to go to just "ProjectLog", you just say ProjectLog. So you could still save time and have cleaner links in this case without giving up explicit context. -- BayleShanks

I'm not sure that after your sets-within-sets suggestion for a namespace, you can ever call anything confusing. Ever again. The word "hypocrisy" is stretched to its utmost extreme even to apply, poor thing. Let's set that aside for now, however.

Pretending set name-spaces are just sub-pages with a single level of hierarchy automatic aliasing doesn't cover the full power of the system, even without contextual linking. Set-based namespaces allows you to have:

The directory equivalent might be:

It might be:

The closest equivalent is actually:

If I'm in the root directory, I can link to 1 just using JohnsProject/ProjectLog. Equally, I can link to 3 using RichardAdams/ProjectLog.

If I'm in JohnJones' directory, I can link to 1 with JohnsProject/ProjectLog, to 2 with KarmaProject/ProjectLog, and I can still link to 3 with RichardAdams/ProjectLog - or KarmaProject/RichardAdams/ProjectLog, or RichardAdams/KarmaProject/ProjectLog.

From the original, all this is still quite clear. To get to a page, you need only provide a minimal set of name-spaces that the page is in that differentiate it from other pages of the same name.

I may get on to explaining why ContextualLinking? is simple someday :) -- ChrisPurcell

I'm not sure that after your sets-within-sets suggestion for a namespace, you can ever call anything confusing. Ever again. The word "hypocrisy" is stretched to its utmost extreme even to apply, poor thing. Let's set that aside for now, however.

ha ha! :) Yeah, I felt some of my above text might be a bit over-the-top, but I thought I'd get some feedback before deciding what to cut. Here's another go at me understanding what you mean:

So, each page has an associated set of other pages (i.e., for the page (1) in your example, which is called ProjectLog, the associated set is {JohnsProject,JohnJones}.

If there is only one page named ProjectLog in the wiki, you can just link to "ProjectLog". However, if (2) and (3) also exist, then you can link to it with JohnsProject:ProjectLog (or, you could use JohnsProject+JohnJones:ProjectLog if you want to).

Is this what you mean? So, the "set" in SetBasedNamespace is referring to a set of other pages associated with each page. Practically, each of those other pages is a namespace, and by associating ProjectLog with {JohnsProject,JohnJones}, you are saying it is "in" the namespaces JohnsProject and JohnJones.

To go "in the other direction" (from parent to child), you could say that ProjectLog (1) is in the set of pages that is the JohnsProject namespace, and also in the set of pages that is the JohnJones namespace. (2) is also in the set of pages that is the JohnJones namespace, so the JohnJones namespace contains 2 pages named "ProjectLog", while the namespace JohnsProject contains only 1.

So, you can link to JohnsProject/ProjectLog without ambiguity, but you can't do JohnJones/ProjectLog. If you made a link like KarmaProject+JohnJones:ProjectLog to reach (2), the interpretation is that you take the intersection of the set of pages in KarmaProject and in JohnJones, after which you end up with only 1 object named ProjectLog.

You can think of the namespaces that a page is in as a list of binary properties; for instance, ProjectLog (2) has properties "KarmaProject" and "JohnJones". The link KarmaProject+JohnJones:ProjectLog is equivalent to a query: "give me all the pages which are named ProjectLog, and which have the KarmaProject and JohnJones properties".

Is this on-target?

-- BayleShanks


Now, imagine we have a page called KarmaTheory?/KarmaProject/KarmaMeasure, describing how karma is measured in the KarmaProject. If I link to JohnJones/ProjectLog or RichardAdams/ProjectLog from this page, I still want to use the KarmaProject namespace.

The PeriPeri:ShatterAlgorithm is a set-theoretic algorithm that determine which page to link to given the current namespace ("directory"). The crucial thing is that it does what you'd expect in all the cases you would find unambiguous. Its behaviour in ambiguous cases is simple to predict once you know the rule it works from.

Interestingly, this behaviour involves semi-lattice theory, though this was not my intent when I first designed the algorithm. I may discuss this later if it's useful for this page. -- ChrisPurcell

I've put my own essay on this topic at PeriPeri:LatticeSpace; I'd really appreciate re-factoring, comments, or whatever. Ideally, I'd like a well-discussed introduction given background in traditional directory structures, etc. Right now, I mostly just have a simple building-up of why PeriPeri does it better than anything else. Help me!! -- cp

I think the most important thing to do with these lines of thought is to make them more concrete. That will not only make it accessible to outsiders, but it will also make sure, every step of the way, that the theory is in step with reality.

We can construct plain talk descriptions of the things we are talking about here, without any problems, and a whole lot more clarity.

For example, we don't have to talk about semi-lattices in order to say, "If you combine two ideas, there's a third idea." Or, "If you take the idea behind two pages, you can combine it into a third page."

I think we should start with the title of the page: "SetBasedNamespace." If this is an important idea, surely we can say what it is, and why it is important.

Let's start with some of the first paragraphs here:

When you say, "page AB is a SubPage of page A", you are saying that page AB is in the NameSpace which is defined by page A. Intuitively, you think of page A as "owning" page AB.

What we want to say is:

Some wiki have been made in a way that let's you put a page beneath another page. For example, if you have a page called "ComplexSystems," you might put a page "CarEngine," or "Program," or "LivingOrganism" beneath it.

In such situations, we'd say that CarEngine lives in the "namespace" of the page ComplexSystems. We might even intuitively think of the page ComplexSystems as "owning" the page "CarEngine."

The second paragraph says:

In a SetBasedNamespace, just think of each page being associated with a set of other pages which it "owns". That is, if page AB was a SubPage of page A, then the set of pages "owned" by A includes AB.

So, this is weird, because we get to the concept of the "SetBasedNamespace," finally. What's it mean? We still don't know. "Just think of each page being associated with a set of other pages which it "owns." How is that any different than the systems we've just described?

Shouldn't we say, "Wiki that are organized like that have what we call a "SetBasedNamespace.""..? But if that were the case, we should say so at the beiginning.

"THat is, if page AB was a SubPage of page A, then the set of pages "owned" by A includes AB." That is what was just immediately explained before, the only difference is that we're implying that that's what we mean by a SetBasedNamespace.

But I'm not sure, because that's what we would have said otherwise, and by starting with "In a SetBasedNamespace," if feels like there is a hidden "but" right before it.

"When you say a page is a subpage of another page...."

"In a SetBasedNamespace,..."

It sounds like there's a "But," hidden right before the SetBasedNamespace. It's terribly confusing.

I still do not know if the first paragraph describes a SetBasedNamespace, or if it is in contrast to a SetBasedNamespace.

Now, if you want AB to be a SubPage of A and also a SubPage of B, just put AB in both sets; the set of pages owned by A, and the set of pages owned by B.

Is this part of the idea of a SetBasedNamespace?

If so, let's just say so from the beginning. Here's a total rewrite:

Traditional wiki have what we call a "flat" namespace. There are a lot of pages, and every page has a name, and just one name. You could line up all the pages in a row, sorted by just their name, hence they are called "flat." You couldn't put some pages above or below one another, if all you paid attention to was their name."

More recently, wiki have what we call a "hierarchical," or "tree based" namespace. Let's suppose you had a page named "SoftwareDevelopment," for developers to talk about developing a computer program. And then you had another page named "UserRequests," so that people who use the program can talk about what freatures they'd like to see in the next version. If you have a "hierarchical" namespace, you could put a new page, say "DoesMyLaundryForMe," and put it under the "UserRequests" page. And then, perhaps you have two thoughts for that page. You could put, under DoesMyLaundryForMe, the pages: "SeperatesWhitesFromBlacks," and "ChecksPocketsFirst."

But there are problems with this system. Perhaps the people working under SoftwareDevelopment have something to contribute, from a developer's angle, to "ChecksPocketsFirst," or they may need to frequently reference the page. The developers don't want to have to write "UserRequests:DoesMyLaundryForMe:ChecksPocketsFirst; They want to just write "ChecksPocketsFirst," even though they are working on some page like "SoftwareDevleopment:RoboticArmAttachment."

(Just now, in writing, I realized that this is the angle to write from. I don't have time immediately- I need to get off the computer- but at this point in writing, I'd probably start over to go at the whole thing from the angle of convenience in writing.)

In a SetBasedNamespace, a page doesn't have to be beneath only one page. You can pull any page beneath any other page, and it's okay with the system.

That, right there, if I am understanding right, may be the key idea to the whole thing.

So, if I were here longer, I would rewrite from the top, saying "Okay, this is about having quick access to pages," and then say "In a SetBased? namespace, a page can be the child of any other page. You're not restricted to just one, like in a tree."

If that is indeed the idea. If we're talking about the organization of conceptual knowledge, that's another thing. Page name access methods and organization of knowledge are two totally different things.

Right now, just reading it, you can't tell what is going on. It's just theory on theory on theory, for what looks to be the joy of theory.

-- LionKimbro

PS Sorry for saying you two were smoking crack. If you knew me in person, I think you'd understand. Absolutely nothing negative about your character implied or intended. :)

I agree, I get lost in the top half of this page. You're on your own with that, unless Bayle comes back to this page. As to the bits that do make sense to you, re-factor away - I'm no use there, either, having been a mathematician continuously for four years (and now a compsci). -- cp

Well,... Did I get it right?

I'd like to refactor it; I just need to make sure I've got the idea right.

Is it accurate to say that in a set based namespace, a page can be the child of any number of pages, just as long as one of it's decendants aren't one of it's ancestors?

I'm not sure I have correctly interpreted the SetBasedNamespace idea.

-- LionKimbro

Are you talking about Bayle's "SetBasedNamespace", or mine? If mine, then no. A page can be in any namespace, but not every page has its own namespace.

The "convenience in writing" angle is a very good one. There's no need for a namespace in Wikis otherwise! We could just use very long names. -- cp

Lion, I agree, it's very much a page in progress, and very confusing. I intend to refactor it. Thank you for your suggestions, they are much clearer than I could have thought to write it.

I wrote this page because ChrisPurcell kept using the term SetBasedNamespaces?, and I wasn't sure exactly what he meant by it. So, I thought of a couple of ideas that the words "set based namespaces" brought to mind for me, in order to ask him which one he meant (and also, just to play around with symbolic formalizations of namespaces). So, one reason it's so hard to understand is that I didn't know what I meant by the "set based namespaces" when I wrote the page.

-- BayleShanks


Define external redirect: SetBased RdfANDWiki DarthVader CategoryBiology SetBasedNamespaces UnitedStates RdfORWiki CategoryEcology KarmaTheory ContextualLinking

EditNearLinks: RdfForWikis PeriPeri FacetWiki SubPage