Recovering logical space from a tablespace I have a tablespace called DATA, and it is setup with auto-extend as false. This tablespace has two datafiles and is set up so it takes up 350&nbsp;GB of physical space.

A week ago I queried user_tablespaces and dba_data_files and noticed it had 20% of available logical space. I then procedeed with a cleanup and removed many records from tables in this tablespace. We were expecting to see a big increase in available space. Unfortunately when I queried the views I noticed the available space was now 20.5%. 

Could this be due to data fragmentation? Can we "defrag" the tablespace somehow and recover the lost space? Or do we need to recreate the tablespace from scratch?
When you delete records there is nothing that automatically compacts the segment, therefore you will need to do a segment shrink to reclaim the space.  Here is excerpt from the 11.2 Administrator's Guide on Reclaiming Wasted Space:


  Over time, updates and deletes on objects within a tablespace can
  create pockets of empty space that individually are not large enough
  to be reused for new data. This type of empty space is referred to as
  fragmented free space.
  
  Objects with fragmented free space can result in much wasted space,
  and can impact database performance. The preferred way to defragment
  and reclaim this space is to perform an online segment shrink. This
  process consolidates fragmented free space below the high water mark
  and compacts the segment. After compaction, the high water mark is
  moved, resulting in new free space above the high water mark. That
  space above the high water mark is then deallocated. The segment
  remains available for queries and DML during most of the operation,
  and no extra disk space need be allocated.


Further down on the same page you can read this:


  Segment shrink is an online, in-place operation. DML operations and
  queries can be issued during the data movement phase of segment
  shrink. Concurrent DML operations are blocked for a short time at the
  end of the shrink operation, when the space is deallocated. Indexes
  are maintained during the shrink operation and remain usable after the
  operation is complete. Segment shrink does not require extra disk
  space to be allocated.
  
  Segment shrink reclaims unused space both above and below the high
  water mark. In contrast, space deallocation reclaims unused space only
  above the high water mark. In shrink operations, by default, the
  database compacts the segment, adjusts the high water mark, and
  releases the reclaimed space.


The page includes much more information on the issue including examples.

The "Segment Space and the High Water Mark" section from the Concepts Guide might also be useful.