query on the predicate array format

Good questions.
The $terms array contains almost-ready-to-save $term objects in the stucture used internally by Drupal.

$terms = array(
  '822' => (Object) (
      'tid' => 822,
      'vid' => 2,
      'name' => "Design",
      'description' => ""
      "weight" => 0,
  )
)

(tid may not be set, that's not your job, and the array key can be anything also)

As you'll see, that doesn't normally define relationships. That's what the predicate list is for.
An intermediate stage in the parsing is to convert all relationships and attributes out of the source documents and turn it into a set of data statements.

Eg in the RDF example,

  <rdfs:Class rdf:ID="term-262">
    <rdfs:label>New Brunswick</rdfs:label>
    <rdfs:comment>The Canadian province of New Brunswick.</rdfs:comment>
    <rdfs:isDefinedBy rdf:resource="#vocabulary-3" />
    <owl:equivalentClass>NB</owl:equivalentClass>
    <rdfs:subClassOf rdf:resource="#term-208">Canada</rdfs:subClassOf>
  </rdfs:Class>

is interpreted as

'term-262- array(
  'name' = 'New Brunswick',
  'description' => "The Canadian province of New Brunswick.",
  'predicates' => array(
    'equivalentClass' => 'NB'
    'subClassOf' => 'Canada'
  )

"predicates" contains all unknown extra bits of info in a nicely tagged bag. (Actually it contains recognised info as well)

This is in turn then translated into statements of relationships
this is what taxonomy_xml_canonicize_predicates() does

'predicates' => array (
  TAXONOMY_XML_PARENT => array ('Canada')
  TAXONOMY_XML_SYNONYM => array ('NB')
)

(see taxonomy_xml_relationship_synonyms() at the end of taxonomy_xml.module for a full list of current relationship-statement-synonyms extracted from real-world taxonomy schema dialects - maybe you now have a few more to add)

A little later taxonomy_xml_set_term_relations(), sting-matching is performed to hook the string 'Canada' with term-id '17' or whatever.

We eventually get the full term object with arrays:

$term->parent = array(17)
$term->relations = array();
$term->synonyms = "NB",

And THEN things can be saved.

There are a few other stages in the middle (like how it handles referencing terms that have not yet been defined) but that's probably OK.

Using the predicates step in the middle CAN sorta be skipped - if you want to do everything by hand and do all your own relinking etc and just set $term->parent yourself. The abstract way of using predicates is there so that all the format inc files can re-use the library routines to massage data that is the same shape.

For your job, I'd advise that:
For large data sets, I found it neccessary to retain the external key/GUID in my imported data. For completeness, for later syncronizing, and for references internally during import. This is not supported in core Drupal so we had to use taxonomy_enhancer.module to add a few more values to our term object. This will probably be beneficial to you anyway. With big sets, and complex taxonomies, string-matching is no longer reliable.
If you use taxonomy_enhancer, and add a field called 'id' - then saving a value in $term->id during your parse phase, it will be retained and also used as a lookup key during the relinking phase