Answering Queries Using Templates With Binding Patterns (Extended Abstract)

Summary: Addresses query answering against sources that only support limited query templates with binding patterns, by asking whether a global conjunctive query can be expressed using those templates under their input/output binding constraints. Provides a nondeterministic polynomial-time decision procedure for conjunctive queries and extends the approach to handle arithmetic comparisons in queries and templates. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1058
Venue: PODS
Year: 1995
Pagerank: 0.00022138018
Overall Rank: 298 | 97.96%
DOI: 10.1145/212433.220199

Incoming Non-self Citations Over Time

Authors

1. Anand Rajaraman (Stanford University)
2. Yehoshua Sagiv (Hebrew University; Stanford University)
3. Jeffrey D. Ullman (Stanford University)

BibTeX Citation

@inproceedings{rajaraman_pods95,
        address = {New York, NY, USA},
        series = {{PODS} '95},
        title = {{Answering Queries Using Templates With Binding Patterns (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/212433.220199},
        doi = {10.1145/212433.220199},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Rajaraman, Anand and Sagiv, Yehoshua and Ullman, Jeffrey D.},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 44 of 44 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00032192665
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
515	Answering Recursive Queries Using Views	1997	PODS	0.00017177428
851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013611183
913	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00013253821
917	Data Integration: The Teenage Years	2006	VLDB	0.00013224381
960	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012945163
1,031	Answering Queries Using Limited External Query Processors	1996	PODS	0.0001253927
1,106	WSQ/DSQ: A Practical Approach for Combined Querying of Databases and the Web*	2000	SIGMOD	0.00012151041
1,554	Google’s Deep-Web Crawl	2008	VLDB	0.00010372108
1,787	Adapting Materialized Views after Redefinitions	1995	SIGMOD	9.7681572e-05
1,991	Views and Queries: Determinacy and Rewriting	2005	PODS	9.344653e-05
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.9856333e-05
2,733	Processing First-Order Queries under Limited Access Patterns	2004	PODS	8.1927747e-05
2,884	Mind Your Vocabulary: Query Mapping Across Heterogeneous Information Sources	1999	SIGMOD	7.9976626e-05
3,039	Query Containment for Data Integration Systems	2000	PODS	7.8265533e-05
3,563	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	7.3076984e-05
3,635	Changing the Face of Database Cloud Services with Personalized Service Level Agreements	2015	CIDR	7.2343405e-05
3,801	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	7.1130194e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
4,542	Capability Based Mediation in TSIMMIS	1998	SIGMOD	6.6395511e-05
4,968	Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue	2019	SIGMOD	6.4206525e-05
5,302	Active Knowledge: Dynamically Enriching RDF Knowledge Bases by Web Services	2010	SIGMOD	6.2745499e-05
6,278	Constraint Satisfaction and Database Theory: a Tutorial	2000	PODS	5.9287393e-05
6,501	Representing and Querying XML with Incomplete Information	2001	PODS	5.8604724e-05
6,536	Interactive Query Formulation over Web Service-Accessed Sources	2006	SIGMOD	5.8486657e-05
6,904	Light-weight Domain-based Form Assistant: Querying Web Databases On the Fly	2005	VLDB	5.7425557e-05
7,428	Invisible Glue: Scalable Self-Tuning Multi-Stores	2015	CIDR	5.6205394e-05
7,671	1,000 Tables Under the From	2009	VLDB	5.5708452e-05
9,043	A Layered Architecture for Querying Dynamic Web Content	1999	SIGMOD	5.3253843e-05
9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	5.3251649e-05
10,221	Differentially Oblivious Multi-way Join	2026	SIGMOD	5.093636e-05
11,928	Data Citation: Giving Credit Where Credit is Due	2018	SIGMOD	5.093636e-05
12,029	Bounded Query Rewriting Using Views	2016	PODS	5.093636e-05
12,351	Querying Schemas With Access Restrictions	2012	VLDB	5.093636e-05
12,364	Determining Relevance of Accesses at Runtime	2011	PODS	5.093636e-05
12,520	Kosmix: High-Performance Topic Exploration using the Deep Web	2009	VLDB	5.093636e-05
12,530	ANGIE: Active Knowledge for Interactive Exploration	2009	VLDB	5.093636e-05
12,577	Optimization of Multi-Domain Queries on the Web	2008	VLDB	5.093636e-05
12,888	Approximate Query Translation Across Heterogeneous Information Sources	2000	VLDB	5.093636e-05

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
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
166	Query Transformation for PSJ-queries	1987	VLDB	0.00027676268
677	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00015065909
853	Queries Independent of Updates	1993	VLDB	0.00013587101
1,489	Constraint Checking with Partial Information	1994	PODS	0.00010612225

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
2	7,830	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS
3	2,947	Querying with Access Patterns and Integrity Constraints	2015	VLDB
4	4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS
5	9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
6	9,994	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS
7	3,039	Query Containment for Data Integration Systems	2000	PODS
8	3,563	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB
9	1,031	Answering Queries Using Limited External Query Processors	1996	PODS
10	4,393	Bounded Conjunctive Queries	2014	VLDB