Indiana University Bloomington

School of Informatics and Computing

Technical Report TR606:
An Algebra for Triadic Relations

Ed Robertson
(Jan 2005), 24 pages plus cover
[An earlier version of this paper appears as "Triadic Relations: an Algebra for the Semantic Web" in the "Proceedings of 2nd International Workshop on Semantic Web and Databases," SWDB 2004, to be published by Springer Verlag.]
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: