Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners.
Arnab BhattacharyyaElena GrigorescuMadhav JhaKyomin JungSofya RaskhodnikovaDavid P. WoodruffPublished in: SIAM J. Discret. Math. (2012)
Keyphrases
- transitive closure
- lower bound
- expressive power
- upper bound
- constraint databases
- recursive queries
- query language
- directed acyclic graph
- query evaluation
- spatial databases
- first order logic
- relational algebra
- objective function
- np hard
- optimal solution
- binary relations
- natural language
- data structure
- main memory
- vc dimension
- image sequences
- database