Complexity Bounds for Relational Algebra over Document Spanners
Summary: Schemaless spanner semantics and adding difference both introduce computational hardness: natural join becomes intractable under schemaless semantics, and difference is hard under both semantics. Proposes syntactic restrictions that preserve expressiveness yet enable polynomial-delay evaluation via a novel ad-hoc compilation into an automaton that merges query and document (instead of static compilation), also accommodating black-box extractors. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,752 | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing | 2022 | PODS | 4.456315e-05 |
| 8,753 | Document Spanners — A Brief Overview of Concepts, Results, and Recent Developments | 2022 | PODS | 4.456315e-05 |
| 11,240 | Autonomously Computable Information Extraction | 2023 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 163 | Optimizing the Performance of a Relational Algebra Database Interface | 1975 | SIGMOD | 0.00039689347 |
| 287 | Declarative Information Extraction Using Datalog with Embedded Extraction Predicates | 2007 | VLDB | 0.00028971272 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,748 | Combined Approximations for Uniform Operational Consistent Query Answering | 2024 | PODS | 4.2897489e-05 |
| 6,728 | Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis | 2023 | PODS | 4.9483326e-05 |
| 2,342 | Rewriting of Regular Expressions and Regular Path Queries | 1999 | PODS | 9.0015589e-05 |
| 7,162 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD | 4.8132423e-05 |
| 12,664 | String Operations in Query Languages | 2001 | PODS | 4.1945683e-05 |
| 1,490 | On the Decidability of Query Containment under Constraints | 1998 | PODS | 0.00011699154 |
| 6,090 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD | 5.2148332e-05 |
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
| 8,961 | An Effective Syntax for Bounded Relational Queries | 2016 | SIGMOD | 4.4206115e-05 |
| 915 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.0001538509 |