The VLDB Journal