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: 1042
Venue: PODS
Year: 1995
Pagerank: 6.1408026e-05
Overall Rank: 5,635 | 61.34%
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
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
1,204	A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding	2003	SIGMOD	0.00011664562

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
571	From Structured Documents to Novel Query Facilities	1994	SIGMOD	0.0001632382
1,001	Querying and Updating the File	1993	VLDB	0.00012714843
1,289	Mind Your Grammar: a New Approach to Modelling Text	1987	VLDB	0.00011314
2,574	The Rufus System: Information Organization for Semi-Structured Data	1993	VLDB	8.3995947e-05
2,588	Optimizing Queries on Files	1994	SIGMOD	8.3742403e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
2	3,742	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB
3	3,728	Querying Structured Text in an XML Database	2003	SIGMOD
4	1,564	Conjunctive Queries over Trees	2004	PODS
5	2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS
6	12,711	An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments	2006	VLDB
7	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
8	1,528	Joining Extractions of Regular Expressions	2018	PODS
9	6,150	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD
10	6,318	Query Automata (extended abstract)	1999	PODS