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,748 | Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing | 2022 | PODS | 4.4520434e-05 |
| 8,749 | Document Spanners — A Brief Overview of Concepts, Results, and Recent Developments | 2022 | PODS | 4.4520434e-05 |
| 11,242 | Autonomously Computable Information Extraction | 2023 | VLDB | 4.1905499e-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 |
|---|---|---|---|---|
| 164 | Optimizing the Performance of a Relational Algebra Database Interface | 1975 | SIGMOD | 0.0003965847 |
| 289 | Declarative Information Extraction Using Datalog with Embedded Extraction Predicates | 2007 | VLDB | 0.00028865317 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,747 | Combined Approximations for Uniform Operational Consistent Query Answering | 2024 | PODS | 4.2856385e-05 |
| 6,732 | Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis | 2023 | PODS | 4.9435849e-05 |
| 2,345 | Rewriting of Regular Expressions and Regular Path Queries | 1999 | PODS | 8.9933611e-05 |
| 7,161 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD | 4.8086254e-05 |
| 12,673 | String Operations in Query Languages | 2001 | PODS | 4.1905499e-05 |
| 1,489 | On the Decidability of Query Containment under Constraints | 1998 | PODS | 0.00011687823 |
| 6,094 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD | 5.2099705e-05 |
| 432 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023349408 |
| 8,963 | An Effective Syntax for Bounded Relational Queries | 2016 | SIGMOD | 4.4165156e-05 |
| 912 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.00015374685 |