The simplest kind of structured object is the semantic net originally developed in the early 1960s to represent the meaning of English words. They are important both historically, and in introducing the basic ideas of class hierarchies and inheritance.
A semantic net is really just a graph, where the nodes in the graph represent concepts, and the arcs represent binary relationships between concepts. The most important relations between concepts are subclass relations between classes and subclasses, and instance relations between particular objects and their parent class. However, any other relations are allowed, such as has-part, colour etc. So, to represent some knowledge about animals (as AI people so often do) we might have the following network:
This network represents the fact that mammals and reptiles are animals, that mammals have heads, an elephant is a large grey mammal, Clyde and Nellie are both elephants, and that Nellie likes apples. The subclass relations define a class hierarchy (in this case very simple).
The subclass and instance relations may be used to derive new information which is not explicitly represented. We should be able to conclude that Clyde and Nellie both have a head, and are large and grey. They inherit information from their parent classes. Semantic networks normally allow efficient inheritance-based inferences using special purpose algorithms.
Semamtic nets are fine at representing relationships between two objects - but what if we want to represent a relation between three or more objects? Say we want to represent the fact that ``John gives Mary the book'' This might be represented in logic as gives(john, mary, book2) where book2 represnts the particular book we are talking about. However, in semantic networks we have to view the fact as representing a set of binary relationships between a ``giving'' event and some objects:
When semantic networks became popular in the 1970s there was much discussion about what the nodes and relations really meant. People were using them in subtly different ways, which led to much confusion. For example, a node such as elephant might be used to represent the class of all elephants or just a typical elephant. Saying that an elephant has_part head could mean that an every elephant has some particular head, that there exists some elephant that has a head, or (more reasonably in this case) that they all have some object belonging to the class head. Depending on what interpretation you choose for your nodes and links, different inferences are valid. For example, if it's just a typical elephant, then Clyde may have properties different from general elephant properties (such as being pink and not grey).
The simplest way to interpret the class nodes is as denoting sets of objects. So, an elephant node denotes the set of all elephants. Nodes such as Clyde and Nellie denote individuals. So the instance relationship can be defined in terms of set membership (Nellie is a member of the set of all elephants), while the subclass relation can be defined in terms of a subset relation - the set of all elephants is a subset of the set of all mammals. Saying that elephants are grey means (in the simple model) that every individual in the set of elephants is grey (so Clyde can't be pink). If we interpret networks in this way we have the advantage of a clear, simple semantics, but the disadvantage of a certain lack of flexibility - maybe Clyde is pink!
In the debate about semantic nets, people were also
concerned about their representational adequacy
(ie, what sort of facts they were capable of representing).
Things that are easy to represent in logic (such
as ``every dog in town has bitten the constable'') are hard to represent
in nets (at least, in a way that has a
clear and well-defined interpretation).
Techniques were developed to allow such things
to be represented, which involved partitionining
the net into sections, and having introducing a special
relationship. These techniques didn't really
catch on, so we won't go into them here, but can be
found in many AI textbooks.
To summarise, nets allow us to simply represent knowledge about an object that can be expressed as binary relations. Subclass and instance relations allow us to use inheritance to infer new facts/relations from the explicitly represented one. However, early nets didn't have a very clear semantics (ie, it wasnt clear what the nodes and links really meant). It was difficult to use nets in a fully consistent and meaningful manner, and still use them to represent what you wanted to represent. Techniques evolved to get round this, but they are quite complex, and seem to partly remove the attractive simplicitly of the initial idea.