NDLI: Definable relations and first-order query languages over strings

Content Provider	ACM Digital Library
Author	Benedikt, Michael Libkin, Leonid Schwentick, Thomas Segoufin, Luc
Copyright Year	2003
Abstract	We study analogs of classical relational calculus in the context of strings. We start by studying string logics. Taking a classical model-theoretic approach, we fix a set of string operations and look at the resulting collection of definable relations. These form an algebra---a class of $\textit{n}-ary$ relations for every $\textit{n},$ closed under projection and Boolean operations. We show that by choosing the string vocabulary carefully, we get string logics that have desirable properties: computable evaluation and normal forms. We identify five distinct models and study the differences in their model-theory and complexity of evaluation. We identify a subset of these models that have additional attractive properties, such as finite VC dimension and quantifier elimination.Once you have a logic, the addition of free predicate symbols gives you a string query language. The resulting languages have attractive closure properties from a database point of view: while SQL does not allow the full composition of string pattern-matching expressions with relational operators, these logics yield compositional query languages that can capture common string-matching queries while remaining tractable. For each of the logics studied in the first part of the article, we study properties of the corresponding query languages. We give bounds on the data complexity of queries, extend the normal form results from logics to queries, and show that the languages have corresponding algebras expressing safe queries.
Starting Page	694
Ending Page	751
Page Count	58
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/876638.876642
Journal	Journal of the ACM (JACM)
Volume Number	50
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-09-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Strings Expressive power First-order definability Quantifier elimination Query languages
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

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

Relational expressive power of constraint query languages

Definable relations and first-order query languages over strings.

Definable Relations and First-Order Query Languages over Strings (1994)

Real-Time Definable Languages

Operations Which Preserve Definability in Languages

New results on quantifier elimination over real closed fields and applications to constraint databases

Relational queries over interpreted structures

On the combinatorial and algebraic complexity of quantifier elimination

Existential second-order logic over strings

Definable relations and first-order query languages over strings

Similar Documents

Relational expressive power of constraint query languages

Definable relations and first-order query languages over strings.

Definable Relations and First-Order Query Languages over Strings (1994)

Real-Time Definable Languages

Operations Which Preserve Definability in Languages

New results on quantifier elimination over real closed fields and applications to constraint databases

Relational queries over interpreted structures

On the combinatorial and algebraic complexity of quantifier elimination

Existential second-order logic over strings

Definable relations and first-order query languages over strings