NDLI: Extracting minimum-weight tree patterns from a schema with neighborhood constraints

Please wait, while we are loading the content...

A personal perspective on keyword search over data graphs

A theory of pricing private data

Fast learning of restricted regular expressions and DTDs

Structural tractability of counting of solutions to conjunctive queries

Walk logic as a framework for path query languages on graph databases

Algebraic structures for capturing the provenance of SPARQL queries

Schema mappings and data exchange for graph databases

Using the crowd for top-k and group-by queries

On optimal differentially private mechanisms for count-range queries

The DNA query language DNAQL

Which DTDs are streaming bounded repairable?

Recursive queries on trees and data trees

Querying graph databases with XPath

A propagation model for provenance views of public/private workflows

Containment of pattern-based queries over data trees

Certain and possible XPath answers

Optimal error of query sets under the differentially-private matrix mechanism

Enumerating with constant delay the answers to a query

XML compression via DAGs

On optimum left-to-right strategies for active context-free games

Definability problems for graph query languages

Annotations are relative

Access patterns and integrity constraints revisited

Extracting minimum-weight tree patterns from a schema with neighborhood constraints

Private decayed predicate sums on streams

Extracting minimum-weight tree patterns from a schema with neighborhood constraints

Content Provider	ACM Digital Library
Author	Kimelfeld, Benny Sagiv, Yehoshua
Abstract	The task of formulating queries is greatly facilitated when they can be generated automatically from some given data values, schema concepts or both (e.g., names of particular entities and XML tags). This automation is the basis of various database applications, such as keyword search and interactive query formulation. Usually, automatic query generation is realized by finding a set of small tree patterns that contain some given labels. More formally, the computational problem at hand is to find top-k patterns, that is, k minimum-weight tree patterns that contain a given bag of labels, conform to the schema, and are non-redundant. A plethora of systems and research papers include a component that deals with this problem. This paper presents an algorithm for this problem, with complexity guarantees, that allows nontrivial schema constraints and, hence, avoids generating patterns that cannot be instantiated. Specifically, this paper shows that for schemas with certain types of neighborhood constraints, the problem is fixed-parameter tractable (FPT), the parameter being the size of the given bag of labels. As machinery, an adaptation of Lawler-Murty's procedure is developed. This adaptation reduces a top-k problem, over an infinite space of solutions, to a prefix-constrained optimization problem. It is shown how to cast the problem of top-k patterns in this adaptation. A solution is developed for the corresponding prefix-constrained optimization problem, and it uses an algorithm for finding a (single) minimum-weight tree pattern. This algorithm generalizes an earlier work by handling leaf constraints (i.e., which labels may, must or should not be leaves). It all boils down to a reduction showing that, under a language for neighborhood constraints, finding top-k patterns is FPT if a certain variant of exact cover is FPT.
Starting Page	249
Ending Page	260
Page Count	12
File Format	PDF
ISBN	9781450315982
DOI	10.1145/2448496.2448526
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-03-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Minimal tree patterns Graph search Query extraction
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in