Least expensive cover your terrace with potted plants
You could also go in for under deck insulation and false ceiling.
Today many vendors are pushing heat reflective coatings which "They Claim" can be used for traffic (walk). I had personaly done a test on one such material but it did not live upto its claim of heat relection nor usabilty.
Other options would inclde rippinig open you existing roof covering (read expensive) most probably Mud phaska and brick tiles, and introducing a material that would increase the time lag required for heat to travel inside.
The materials can be
1. Inverted shallow pots (air is a good insulator)
2. 50 mm Thermocole
3. 25 MM PUF (Roffmatte etc.)
4. Vermaculite (dont remeber the specs off hand).
Plus many otherwater proofing heat reflective memberaness.
On top of this you will require a layer of screed, waterproofing and then a top surface as you may want for the roof (brick tiles, kota stone, marbles or even china mosaic (also reflects heat).