NDLI: Logics with aggregate operators

Content Provider	IEEE Xplore Digital Library
Author	Hella, L. Libkin, L. Nurmonen, J. Limsoon Wong
Copyright Year	1999
Description	Author affiliation: Helsinki Univ., Finland (Hella, L.)
Abstract	We study adding aggregate operators, such as summing up elements of a column of a relation, to logics with counting mechanisms. The primary motivation comes from database applications, where aggregate operators are present in all real life query languages. Unlike other features of query languages, aggregates are not adequately captured by the existing logical formalisms. Consequently, all previous approaches to analyzing the expressive power of aggregation were only capable of producing partial results, depending on the allowed class of aggregate and arithmetic operations. We consider a powerful counting logic, and extend it with the set of all aggregate operators. We show that the resulting logic satisfies analogs of Hanf's and Gaifman's theorems, meaning that it can only express local properties. We consider a database query language that expresses all the standard aggregates found in commercial query languages, and show how it can be translated into the aggregate logic, thereby providing a number of expressivity bounds, that do not depend on a particular class of arithmetic functions, and that subsume all those previously known. We consider a restricted aggregate logic that gives us a tighter capture of database languages, end also use it to show that some questions on expressivity of aggregation cannot be answered without resolving some deep problems in complexity theory.
Starting Page	35
Ending Page	44
File Size	374420
Page Count	10
File Format	PDF
ISBN	0769501583
ISSN	10436871
DOI	10.1109/LICS.1999.782583
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1999-07-05
Publisher Place	Italy
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Logic Aggregates Database languages Arithmetic Mathematics Computer science Spatial databases Complexity theory Application software Relational databases
Content Type	Text
Resource Type	Article
Subject	Mathematics 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

MLPQ: a linear constraint database system with aggregate operators

On first-order topological queries

On the forms of locality over finite models

Expressive equivalence of least and inflationary fixed-point logic

The Quest for a Logic Capturing PTIME

How Would You Like to Aggregate Your Temporal Data?

An efficient park service management package

Adapting Logics

Generalized logical operators for temporal languages

Logics with aggregate operators

Similar Documents

MLPQ: a linear constraint database system with aggregate operators

On first-order topological queries

On the forms of locality over finite models

Expressive equivalence of least and inflationary fixed-point logic

The Quest for a Logic Capturing PTIME

How Would You Like to Aggregate Your Temporal Data?

An efficient park service management package

Adapting Logics

Generalized logical operators for temporal languages

Logics with aggregate operators