The structure of each relation is defined by its schema, which specifies the attributes associated with tuples in that relation. A qddb relation is a set of tuples. Each tuple is a set of attribute values. Attributes are either simple or expandable. Simple attributes contain at most one value per tuple. An expandable attribute may have multiple values of the same tuple. We display these ideas in Figure 1.
In this example, attributes marked with ``*'' are expandable, that is, they may be given multiple values. A student may have multiple addresses; each address may have multiple phone numbers. Each student is expected to have taken multiple courses. Each occurrence of an expandable attribute is called an instance of that attribute. This example also shows that attributes may have sub-attributes. The Address attribute contains sub-attributes for such items as street address, city, and zip code, and Street itself has sub-attributes for number, road, and apartment number.
Tuples need not contain values for all defined attributes. For example, we might leave off the Country attribute for addresses in the same country as the school, or the MiddleName attribute for students with no middle name. No storage is occupied by attributes that have no value.
The most fundamental query supported by qddb returns all tuples containing a given key (independent of the attribute in which it is found). More complex queries are also supported, such as Boolean combinations, attribute-specific queries, and queries based on numeric or other properties of attributes.
The Schema file specifies the names and order of a relation's attributes. It can be constructed with any ordinary text editor. Once the relation has been populated, the schema should be changed only by (1) adding new attributes at the end, (2) adding subattributes at the end of an attribute, or (3) using a program in the qddb suite that converts relations from one schema to another by translating the entire relation into presentation format by the first schema and then translating it back to storage format by the second one. We discuss these forms shortly.
The BNF grammar in Figure 2 defines the format of a schema file. Items in single quotes are terminals of the grammar. White space in the file is used as a separator and is otherwise ignored. Brackets indicate optional items; if the brackets are followed by ``+'', the item must appear one or more times; if they are followed by ``*'', the item may appear zero or more times.
We have already seen a sample schema file in Figure 1. The alias and verbosename keywords may be used by programs that present the relation to the user, but they have no impact on the contents of the relation files. The hashsize keyword, if present, determines the number of hash buckets used during stabilization. The other options are discussed in subsequent sections.
Tuples in the relation are also stored in Ascii and may be entered by an ordinary text editor. The storage format is readable with some effort, but users typically deal with the presentation format of the data. The qddb package includes routines to convert between presentation and storage format.
Each non-empty attribute in the tuple is presented as an attribute name followed by its value. Expandable attributes are presented once for each instance. The BNF grammar for the presentation format of tuples is shown in Figure 3.
UniversityID
Name (
FirstName
MiddleName
LastName
)
Address (
Street (
Number
Road
Apartment
)
City
State
Zip
Country
Phone*
EMail
)*
Course (
Number
Semester
Year
Grade
Credits
)*
Figure 1: A sample schema for student records
Schema ::= [ Options ] [ Record ]+\\
Options ::= [ HashSize ] [ CacheSize ] [ CachedHashing ] [ ReducedID ]
HashSize ::= 'hashsize' '=' Integer
CacheSize ::= 'cachesize' '=' Integer
CachedHashing ::= 'Use' 'Cached' 'Hashing'
ReducedID ::= 'Use' 'Reduced' 'Attribute' 'Identifiers'
Record ::= [ IRecord ]+
IRecord ::= ID [ '(' Record ')' ]* [ '*' ]
ID ::= String [ 'alias' String ]* [ 'verbosename' CString ]
String ::= [a-zA-Z][a-zA-Z0-9]*
CString ::= '"' [ AnyPrintableASCIICharacter ]* '"'
Integer ::= [0-9]+
AnyPrintableASCIICharacter ::=
[A-Za-z0-9!@#$%^&*()+-=|\,./<>?~`{}[] _]
Figure 2: BNF for the format of a Schema file
FullTuple ::= '\$NUMBER\$' '=' '"' [0-9]+ '"' ';' Tuple
Tuple ::= [ Record ]*
Record ::= [ IRecord ]+
IRecord ::= ID | String [ '(' Record ')' ]+
ID ::= String [ '=' CString ]
String ::= [a-zA-Z]+[a-zA-Z0-9]*
CString ::= '"' [ AnyPrintableASCIICharacter ]* '"'
AnyPrintableASCIICharacter ::=
[A-Za-z0-9!@#$%^&*()+-=|\,./<>?~`{}[] _]
Figure 3: BNF grammar for the presentation format of tuples
Figure 4 shows the presentation format of a tuple conforming to the
schema in Figure 1.
$NUMBER$ = "0";
Name (
FirstName = "Joe"
LastName = "Student"
)
Address (
Street (
Number = "456"
Road = "Somewhere Lane"
)
City = "Little Town"
State = "AZ"
ZipCode = "67890-1234"
)
Address (
Street (
Number = "123"
Road = "Zimbob Lane"
Apartment = "3A"
)
City = "Lexington"
State = "KY"
ZipCode = "12345-1234"
)
Figure 4: An example of a tuple in presentation format