School of Informatics and Computing

Technical Report TR606:
An Algebra for Triadic Relations

Abstract:

This paper introduces and develops an algebra over triadic relations, that is, relations whose contents are only triples. In essence, the algebra is a variation of relational algebra, defined over relations with exactly three attributes and closed for the same set of relations.

Ternary relations are important because they provide the minimal, and thus most uniform, way to encode semantics wherein metadata may be treated uniformly with regular data; this fact has been recognized in the choice of triples to formalize the ``Semantic Web''. Indeed, algebraic definitions corresponding to certain of these formalisms will be shown as examples.

An important aspect of this algebra is an encoding of triples, implementing a kind of reification. The algebra is shown to be equivalent, over non-reified values, to a restriction of Datalog and hence to a fragment of first order logic. Furthermore, the algebra requires only two operators if certain fixed infinitary constants (similar to Tarski's identity) are present. In this case, all structure is represented only in the data, that is, in encodings represented by these infinitary constants.

Available as:

• PDF (243 KBytes)
• Compressed PostScript (233 KBytes)
• PostScript (via FTP download)

There is help available if you want further information about the available file formats and software to display and print these files.