{'fraction_non_alphanumeric': 0.014414414414414415, 'fraction_numerical': 0.0, 'mean_word_length': 5.94375, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the space requirements of navigational relationship representations

One of the problems which confront designers, implementers, and users of database management systems is the very large amounts of space often required to store a database in a computer system. In general, that space is used for two purposes: to represent certain atomio units of data and to represent certain relationships among those atomic units. This paper investigates the second aspect of the problem, the storage requirements of relationship representations. The class of navigational representations is defined, and several relationship representation techniques commonly used in database management systems are shown to be navigational. Two additional techniques for constructing relationship representations are presented. The first produces more compact representations than the standard techniques by taking advantage of a property of relationships called companionship. The second technique, called the powerset representation, always achieves a worst-case lower bound on the size of navigational relationship representations.