Algebras for Querying Text Regions (Extended Abstract)

Summary: Defines a set-at-a-time region algebra for text substrings that combines pattern searches with hierarchical (nesting/ordering) queries and connects its expressiveness to the monadic first-order theory of binary trees. Shows optimization is Co-NP-hard in general (polynomial for a key fragment), identifies expressiveness gaps for some nesting/ordering properties, and proposes extensions to trade off added power against optimization complexity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hbf68650f9593ec90
Venue: PODS
Year: 1995
Pagerank: 6.0035367e-05
Overall Rank: 5,763 | 61.26%
DOI: 10.1145/212433.212437

Incoming Non-self Citations Over Time

Authors

1. Mariano P. Consens (University of Waterloo)
2. Tova Milo (Tel Aviv University; University of Toronto)

BibTeX Citation

@inproceedings{consens_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Algebras for Querying Text Regions (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/212433.212437},
        doi = {10.1145/212433.212437},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Consens, Mariano P. and Milo, Tova},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
1,234	A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding	2003	SIGMOD	0.00011405864

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
582	From Structured Documents to Novel Query Facilities	1994	SIGMOD	0.00015982468
1,021	Querying and Updating the File	1993	VLDB	0.0001243944
1,312	Mind Your Grammar: a New Approach to Modelling Text	1987	VLDB	0.0001106293
2,622	The Rufus System: Information Organization for Semi-Structured Data	1993	VLDB	8.2118212e-05
2,637	Optimizing Queries on Files	1994	SIGMOD	8.1877616e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
2	3,829	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB
3	3,810	Querying Structured Text in an XML Database	2003	SIGMOD
4	1,599	Conjunctive Queries over Trees	2004	PODS
5	2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
6	13,001	An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments	2006	VLDB
7	4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
8	1,560	Joining Extractions of Regular Expressions	2018	PODS
9	6,273	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD
10	6,445	Query Automata (extended abstract)	1999	PODS