ESA's Global Astrometric Interferometer for Astrophysics (GAIA) holds the p
romise of mapping out the detailed phase space structure of the Galactic ha
lo by providing unprecedented annual proper motion and parallax of 1-10 mu
as astrometric accuracy (Gilmore et al. 1998). Unlike NASA's Space Interfer
ometry Mission (SIM), which will achieve similar accuracies but is a pointe
d instrument, GAIA will be able to construct a global catalogue of the halo
. Here we study proper motions of giant branch stars in a tidal debris torn
from a small satellite system in the halo. We follow the evolution of a co
ld stream on a polar orbit between 8-50 kpc in a variety of histories of th
e Galactic potential, and observe the bright (V < 18mag) members of the deb
ris tail with GAIA accuracy. We simulate effects due to the growing or flip
ping of the Galactic disk over the past 3 Gyrs or the perturbation from a m
assive accreted lump such as the progenitor of the Magellanic Clouds. Our s
imulations suggest that the results of Johnston, Zhao, Spergel & Hernquist
(1999) and Helmi, Zhao & de Zeeuw (1999) for static Galactic potentials are
likely to be largely generalizable to realistic time-dependent potentials:
a tidal debris remains cold in spite of evolution and non-axial symmetry o
f the potential. GAIA proper motion measurements of debris stars might be u
sed to probe both Galactic structure and Galactic history. We also study se
veral other factors influencing our ability to identify streams, including
accuracy of radial velocity and parallax data from GAIA, and contamination
from random field stars. We conclude that nearby, cold streams could be det
ected with GAIA if these cousins of the Sagittarius stream exist.