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)

Paper ID: 1793
Venue: PODS
Year: 2019
Pagerank: 6.3571407e-05
Overall Rank: 5,123 | 64.86%
DOI: 10.1145/3294052.3319699

Incoming Non-self Citations Over Time

Authors

1. Liat Peterfreund (Technion)
2. Dominik D. Freydenberger (Loughborough University)
3. Benny Kimelfeld (Technion)
4. Markus Kröll (Vienna University of Technology)

BibTeX Citation

@inproceedings{peterfreund_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Complexity Bounds for Relational Algebra over Document Spanners}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319699},
        doi = {10.1145/3294052.3319699},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Peterfreund, Liat and Freydenberger, Dominik D. and Kimelfeld, Benny and Kröll, Markus},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,922	Query Evaluation Over SLP-Represented Document Databases With Complex Document Editing	2022	PODS	5.3483178e-05
8,923	Document Spanners — A Brief Overview of Concepts, Results, and Recent Developments	2022	PODS	5.3483178e-05
11,440	Autonomously Computable Information Extraction	2023	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
319	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB	0.00021377065
519	Optimizing the Performance of a Relational Algebra Database Interface	1975	SIGMOD	0.00017144967
1,528	Joining Extractions of Regular Expressions	2018	PODS	0.00010486718
2,348	Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity	2018	PODS	8.7135317e-05
2,619	Constant Delay Algorithms for Regular Document Spanners	2018	PODS	8.336529e-05
4,097	Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates	2018	PODS	6.9038261e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD
2	12,857	String Operations in Query Languages	2001	PODS
3	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
4	6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
5	2,348	Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity	2018	PODS
6	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
7	9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD
8	2,619	Constant Delay Algorithms for Regular Document Spanners	2018	PODS
9	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
10	1,528	Joining Extractions of Regular Expressions	2018	PODS